gerichtete und ungerichtete Graphen

Wambolo
Computerversteher
Computerversteher
Beiträge: 381
Registriert: 18. Okt 2007 11:36

gerichtete und ungerichtete Graphen

Beitrag von Wambolo »

...gibt es im ungerichteten Graphen eine Unterscheidung zwischen einem einfachen Zyklus und einem Zyklus. Wenn ich das jetzt richtig verstanden habe, dann müssen die Knoten des Pfads, der den Zyklus beschreibt, abgesehen vom Start- und Zielknoten (die ja gleich sein müssen) paarweise verschieden sein. Das würde bedeuten, dass ich innerhalb eines Zyklus, im ungerichteten Graphen (wieder abgesehen vom Start- und Zielknoten) nie zwei identische Knoten durchlaufe.

Also dürfte es sozusagen nur einfache Zyklen geben, ist das richtig?
Interpreter/Parser reported on Nov 12, 2008 8:30:04 PM:
Number too big (102 > 42).

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

Re: gerichtete und ungerichtete Graphen

Beitrag von mantra »

Also dürfte es sozusagen nur einfache Zyklen geben, ist das richtig?
Nein.
Wambolo hat geschrieben:Wenn ich das jetzt richtig verstanden habe, dann müssen die Knoten des Pfads, der den Zyklus beschreibt, abgesehen vom Start- und Zielknoten (die ja gleich sein müssen) paarweise verschieden sein.
Guck nochmal nach, welche Bedingungen für Zyklen gelten müssen.

Wambolo
Computerversteher
Computerversteher
Beiträge: 381
Registriert: 18. Okt 2007 11:36

Re: gerichtete und ungerichtete Graphen

Beitrag von Wambolo »

aus Algorithmen - Eine Einführung:

"In einem ungerichteten Graphen bildet ein Pfad (vo, v1, ... , vk) einen (einfachen) Zyklus, falls k>=3 und v0=vk gilt, und falls v1, v2, ..., vk paarweise verschieden sind. ..." (S. 1084 dritter Absatz)

Leider verstehe ich nicht wie ich das anders interpretieren soll.
Interpreter/Parser reported on Nov 12, 2008 8:30:04 PM:
Number too big (102 > 42).

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

Re: gerichtete und ungerichtete Graphen

Beitrag von mantra »

Oha.

In den Folien zur Vorlesung bezieht sich die Definition von Zyklen nur auf gerichtete Graphen. Kommt daher deine Frage für ungerichtete Graphen?
Ich nehme stark an, dass du die Definition aus der Vorlesung auch auf ungerichtete Graphen erweitern kannst und die Definition aus dem Buch etwas zu kompakt ist und das gleiche meint: In Nicht-einfachen Zyklen können Knoten mehrfach enthalten sein.

Wambolo
Computerversteher
Computerversteher
Beiträge: 381
Registriert: 18. Okt 2007 11:36

Re: gerichtete und ungerichtete Graphen

Beitrag von Wambolo »

Ja, meine Frage bezieht sich nur auf ungerichtete Graphen.

Danke auf jeden Fall schon mal für die Antwort.
Interpreter/Parser reported on Nov 12, 2008 8:30:04 PM:
Number too big (102 > 42).

michael2k5
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 117
Registriert: 2. Dez 2005 19:22
Wohnort: Darmstadt-Eberstadt
Kontaktdaten:

Re: gerichtete und ungerichtete Graphen

Beitrag von michael2k5 »

wo wir hier gerade beim thema gerichtete und ungerichtete graphen sind.

beim gerichtetn graph komme ich mit einer schlinge von knoten a zu knoten a.
schlingen sind ja beim ungerichteten nicht erlaubt. komm ich trotzdem von knoten a zu knoten a, oder geht das nicht?

Benutzeravatar
Demmi
Kernelcompilierer
Kernelcompilierer
Beiträge: 423
Registriert: 1. Okt 2007 12:56
Wohnort: Darmstadt

Re: gerichtete und ungerichtete Graphen

Beitrag von Demmi »

michael2k5 hat geschrieben:komm ich trotzdem von knoten a zu knoten a, oder geht das nicht?
Soweit ich das verstanden hab, sind beim ungerichteten Graph keine direkten Wegen A->A erlaubt.
Wenn man jedoch schon bei A ist, kann man auch "im nächsten Schritt" noch auf A sein, wenn man sich einfach nicht weiterbewegt. Blöd ausgedrückt, kommt aber drauf an was man konkret vorhat...
Ne andere Möglichkeit von A nach A zu kommen wäre noch ein Zyklus über mindestens 2 verschiedene Zwischenknoten.
z.B.: A->B->C->A
Saying that Java is nice because it works on all Plattforms is like saying that anal sex is nice because it works on all genders.

michael2k5
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 117
Registriert: 2. Dez 2005 19:22
Wohnort: Darmstadt-Eberstadt
Kontaktdaten:

Re: gerichtete und ungerichtete Graphen

Beitrag von michael2k5 »

um im ungerichteten graphen von a nach a zu kommen reicht auch ein weiterer knoten b.
a -> b
b -> a

das geht ja immer. das ist klar. brauchst also laut def nichtmal ein zyklus.
vielleicht sollte ich meine frage auch etwas präziser stellen. stimmt.
ich frage mich, ob es bei einem ungerichteten graphen mit dem knoten a zb den pfad
<a,a,a,a,a,a> gehen könnte.

wenn beim gerichteten graph eine schlinge von a nach a vorhanden ist, könnte ich diesen pfad sicherlich gehen.

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: gerichtete und ungerichtete Graphen

Beitrag von s!mon »

Es gibt keine Schlingen in ungerichteten Graphen (die Diskussion hatten wir auch schon mal in nem Thread)

A->B->A wäre in einem ungerichteten Graphen kein Pfad, weil ein Pfad kanteneinfach ist. Natürlich könnte man den weg aber gehen..

michael2k5
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 117
Registriert: 2. Dez 2005 19:22
Wohnort: Darmstadt-Eberstadt
Kontaktdaten:

Re: gerichtete und ungerichtete Graphen

Beitrag von michael2k5 »

wer hat gesagt, dass ein pfad kanteneinfach sein muss?
laut pfaddefinition im CLRS muss ein pfad nicht kanteneinfach sein.

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: gerichtete und ungerichtete Graphen

Beitrag von s!mon »


Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: gerichtete und ungerichtete Graphen

Beitrag von oren78 »

s!mon hat geschrieben:Es gibt keine Schlingen in ungerichteten Graphen...
blödsinn junge !! :-)

schau her bevor du solche aussagen machst: http://halvani.de/GDI2_SS2007_Uebungen.pdf
auf der Seite: 5 Aufgabe: G 2.1 Graphen...
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Stumpf.Alex
Nerd
Nerd
Beiträge: 643
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Re: gerichtete und ungerichtete Graphen

Beitrag von Stumpf.Alex »

oren78 hat geschrieben:
s!mon hat geschrieben:Es gibt keine Schlingen in ungerichteten Graphen...
blödsinn junge !! :-)

schau her bevor du solche aussagen machst: http://halvani.de/GDI2_SS2007_Uebungen.pdf
auf der Seite: 5 Aufgabe: G 2.1 Graphen...
Beschäftige dich mal lieber mit dem Material aus diesem Semester. :wink:


Auch hier nochmal:

Quellen für Definitionen:
- Buchmannskript: "6 Graphen"
- "Algortihmen - eine Einführung": S. 1082, letzter Absatz in der deutschen Version

Hier nochmal der entsprechender Auszug aus dem Buchmannskript, dass ungerichtete Graphen keine Schlingen enthalten dürfen:
Dateianhänge
Definition, dass ungerichtete Graphen keine Schlingen enthalten dürfen
Definition, dass ungerichtete Graphen keine Schlingen enthalten dürfen
graph.JPG (46.82 KiB) 886 mal betrachtet

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: gerichtete und ungerichtete Graphen

Beitrag von oren78 »

Stumpf.Alex hat geschrieben:Beschäftige dich mal lieber mit dem Material aus diesem Semester...
das hat nix mit unterlagen aus diesen oder vorherigen semestern zu tun, das sind mathematische gesetze, die man nicht einfach mal so nach lust und laune ändern kann, da man sich auf sie stützen muss um irgendwelche aussagen zu machen...

es kann schließlich nicht angehen das der eine blau sagt und der andere gelb...

übrigens das was unser prof mitschreibt STAMMT 1:1 aus dem buch, deswegen steht so zu sagen eine aussage gegen die andere und nicht zwei aussagen gegen eine...

schade das der veranstalter sich hier nicht einmischt und grundlegende und vor allem FEST FUNDIERTE definitionen weder hier noch in den folien niederschreibt :-(
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Stumpf.Alex
Nerd
Nerd
Beiträge: 643
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Re: gerichtete und ungerichtete Graphen

Beitrag von Stumpf.Alex »

oren78 hat geschrieben:übrigens das was unser prof mitschreibt STAMMT 1:1 aus dem buch, deswegen steht so zu sagen eine aussage gegen die andere und nicht zwei aussagen gegen eine...
Wie meinste das? Beide Aussagen (Buch und Buchmannskript) sagen doch das gleiche....keine Schlingen in ungerichteten Graphen. Für mich hat Buchmann das so festgelegt und darauf kann man sich dann in der Klausur berufen. Fertig!

In fGdI 1 hatten wir auch das Problem, dass jeder Prof leicht unterschiedliche Definitionen nimmt. Daher gilt, immer nach dem aktuellen Professor richten.

Antworten

Zurück zu „Archiv“