Fachrat Informatik - Forum

Quoted

Original von Currywurst mit Pommes
Bei gerichteten Graphen ist mir das klar. Aber bei ungerichteten - wie sieht das da aus ? Zählt da eine einfache Kante zwischen A und B schon als zyklus (ist ja schließlich "hin" und "zurück" ?). Oder wie ist das bei ungerichteten definiert ?

Zyklen sind nur für gerichtete Graphen definiert. siehe auch http://mathworld.wolfram.com/AcyclicDigraph.html
Schau dir noch mal die Definitionen aus der Vorlesung an. Es könnte sein, dass in der Vorlesung die Definitionen etwas anders sind. Das halte ich aber für sehr unwahrscheinlich!

Quoted

Ach ja, zählt ein einziger Knoten schon als Graph ?

Ja, tut er.

Manche Definitionen lassen sogar den Nullgraphen oder einen leeren Graphen zu

Nach welcher Definition denn? Also wenn ich an die letzten Jahre denke, habe ich immernoch das Gefühl, dass sich die Mathematiker in der Graphentheorie nie ganz einig sind bei ihren Definitionen! Interessant wird es eh erst ab Multigraphen.

Quoted

Original von Currywurst mit Pommes
Aber bei ungerichteten - wie sieht das da aus ? Zählt da eine einfache Kante zwischen A und B schon als zyklus (ist ja schließlich "hin" und "zurück" ?). Oder wie ist das bei ungerichteten definiert ?

(v1, v2, v1) ist sowohl Zyklus als auch ein Kreis, wenn man die Definitionen aus folgendem Wikipedia-Artikel nimmt.

Quoted

Wikipedia: Wege, Pfade, Zyklen und Kreise in Graphen

Ein Zyklus oder Kreis heißt trivial, wenn er weniger als drei Knoten enthält. Triviale Kreise oder Zyklen werden meist nicht betrachtet.

Quoted

Original von migu
Zyklen sind nur für gerichtete Graphen definiert. siehe auch http://mathworld.wolfram.com/AcyclicDigraph.html

migu, die von Dir zitierte Seite sagt aber nur "ein Graph ohne Zyklen ist ein gerichteter Graph", oder?

Quoted

Original von Currywurst mit Pommes
Ach ja, zählt ein einziger Knoten schon als Graph ?

Also mit der Definition G=(V,E), V ist (endlich) nichtleere Menge von Knoten, E ist Menge von zweielementigen Teilmengen von V wie sie im Buch zu Diskrete Strukturen steht, ist G=({v1},{}) ein Graph.

Also so wie ich mich an die Vorlesung Diskrete Strukturen von Erne errinnere liegt immer ein Zykel vor, wenn ein Graph 2-fach zusammenhängend ist.

D.h. immer wenn man in irgendeiner Weise 2 mindestens in einer Kante (durch den Aufbau von Graphen müssen es aber mindestens 2 sein) unterschiedliche Wege von einem Knoten kn zu einem knoten km finden kann enthält der Graph mindestens eine Zykel.

Danach ergibt sich für einen vollständig zyklischen Graphen, dass es mindestens 2 unterschiedliche Wege von jedem km zu jedem kn geben muss, wobei m ungleich n ist.

Zykel sind definintiv auch für ungerichtete Graphen definiert, ein Zykel ist bei zwei Knoten jedoch nicht Möglich, weil eine Kante für die Überprüfung des Zykels jeweils nur einmal benutzt werden darf, es sei denn, du erlaubst doppelte Kanten zwischen den einzelnen Knoten.

Ich kann zu dem Thema nur das Skript von der SS06 Vorlesung zu Diskreten Strukturen empfehlen, da es sich ausgiebig mit dem Thema Graphentheorie befasst.

<edit>
Hier ist auch der Link dazu:
http://service.ifam.uni-hannover.de:8600/bibliography.html
</edit>

Quoted

Original von neweb
Ich kann zu dem Thema nur das Skript von der SS06 Vorlesung zu Diskreten Strukturen empfehlen, da es sich ausgiebig mit dem Thema Graphentheorie befasst.

Da sich gerade in diesem Bereich wohl die Definitionen nicht immer einig sind, würde ich nur auf die Definition des Skriptes der entsprechenden Vorlesung pochen.

Wie genau ist denn Zyklus in der Vorlesung definiert?
Wenn es wirklich nur durch ein "hin und zurück" definiert ist, dann ist es doch ganz einfach so, dass ein ungerichteter Graph mit mind. zwei zusammenhängenden Knoten nicht zyklenfrei ist :]

Quoted

Original von metalhen

Quoted

Original von migu
Zyklen sind nur für gerichtete Graphen definiert. siehe auch http://mathworld.wolfram.com/AcyclicDigraph.html

migu, die von Dir zitierte Seite sagt aber nur "ein Graph ohne Zyklen ist ein gerichteter Graph", oder?

Nicht ganz: "Ein gerichteter Graph ohne gerichtete Zyklen heißt azyklischer Digraph." Deine Aussage würde einen nicht gerichteten Graphen ohne Zyklen automatisch zum gerichteten Graphen machen.
Du hast aber Recht damit, dass die Seite nicht das sagt, was ich behauptete, nämlich dass Zyklen nur für gerichtete Graphen definiert sind.

Quoted

Original von Currywurst mit Pommes
Leider finde ich im Skript bei der Definition ungerichteter Graphen nur eine Aussage wie "Die Begriffe Pfad, Zyklus sowie Erreichbarkeit übertragen sich entsprechend" .

Das hilft mir leider nicht weiter, da es ja nicht wirklich aussagt, wie ein "hin-zurück" gedeutet werden soll. Ist ein "hin-zurück" bei gerichteten Graphen ein zyklus, so wären alle ungerichteten ja niemals zyklus-frei (bei min. einer kante).

Glücklicherweise tragen viele Begriffe aus der Graphentheorie ihre Namen wegen der hinter ihnen stehenden intuitiven Konzepte. Da Zyklen den Begriff des Kreises erfassen, finde ich es bei ungerichteten Graphen unangebracht, bei jeder ungerichteten Kante von einem Zyklus zu sprechen. Ein Zyklus in ungerichteten Graphen sollte daher eine Folge (ein Pfad) paarweise verschiedener Kanten sein, so daß der Start- und Endknoten identisch ist. Dies ist dann auch eine direkte Übertragung des Begriffs Zyklus für gerichtete Graphen (ersetze "Kante" durch "gerichtete Kante").

Einheitliche Definitionen sind in der Mathematik ohnehin nur in wenigen Teilbereichen zu finden. Häufig weichen Begriffe in ihren Definitionen sowieso nur in Randfällen voneinander ab. Auf die Definitionen kommt es also nicht so sehr an, vielmehr auf die darauf aufbauenden Sätze.

Quoted

Original von Joachim

Quoted

Original von Currywurst mit Pommes
Leider finde ich im Skript bei der Definition ungerichteter Graphen nur eine Aussage wie "Die Begriffe Pfad, Zyklus sowie Erreichbarkeit übertragen sich entsprechend" .

Das hilft mir leider nicht weiter, da es ja nicht wirklich aussagt, wie ein "hin-zurück" gedeutet werden soll. Ist ein "hin-zurück" bei gerichteten Graphen ein zyklus, so wären alle ungerichteten ja niemals zyklus-frei (bei min. einer kante).

Glücklicherweise tragen viele Begriffe aus der Graphentheorie ihre Namen wegen der hinter ihnen stehenden intuitiven Konzepte. Da Zyklen den Begriff des Kreises erfassen, finde ich es bei ungerichteten Graphen unangebracht, bei jeder ungerichteten Kante von einem Zyklus zu sprechen.

Wie schon gesagt: Ein Graph besitzt mindestens einen Zykel, wenn du auf zwei "nicht identischen" Pfaden von einem Punkt zu einem anderen kommst. Um das zu ergänzen: Es soll natürlich bei keinem der Pfade eine Kante doppelt besucht werden.

Es geht ja um die Zykelfreiheit, nicht darum, ob der ganze Graph einen Zycel darstellt. Wer im Skript mal nach der Definition eines Baumes sucht, wird feststellen, dass es eine Liste mit equivalenten Eigenschaften gibt. Dort sollte stehen, dass ein Baum:
"maximal azyclisch"
ist.

Also Taucht dieser Begriff u.a. bei ungerichteten Bäumen auf. Dies schließt ein, dass eine Kante auf einem Pfad immer nur maximal ein mal benutzt werden darf.

Ähnliches sollte sich in den Kapiteln zu Euler- und Hamilton-Kreisen finden.

Aus der Graphentheorie her ist somit die Definition ziemlich eindeutig. Ansonsten würde die Definition auch keinen Sinn machen.

<edit>
Man könnte auch sagen, dass ein Graph G mindestens einen Zykel besitzt, wenn es mindestens einen Graphen G' Teilmenge von G gibt, der mindestens 2-fach zusammenhängend ist.
</edit>

neweb hat es schon recht klar zusammengefasst, und genau so steht es auch im Skript:

Ein Zyklus bzw. Kreis ist ein Pfad, also eine Folge von Kanten, die
1. einfach ist, also keine Kante doppelt benutzt und
2. geschlossen ist, also mit dem Knoten endet, an dem sie begann.

Für ungerichtete Graphen folgt sofort, dass ein Zyklus mindestens zwei Kanten, und damit drei Kanten (weil wir ja nicht von Multigraphen sprechen) umfassen muss. Ich gebe zu, dass diese Info im Skript Erwähnung finden könnte.

Ansonsten finde ich Joachims Hinweis wertvoll: Verlasst Euch im zweifel auf Euren gesunden Menschenverstand! In der Anwendung später habt Ihr es auch mit unzureichenden Dokumentationen und lückenhaften Spezifikationen zu tun.

P.S.: Zur zweiten Frage habe ich schon eine Antwort im E-Learning-Netz gepostet:

Quoted

Wie dort steht soll der Graph so orientiert werden, dass jede Kante in alphabetischer Ordnung verläuft. Es geht also um gerichtete Graphen: Enthält der Graph G eine Kante e={z,y}, so wird sie zu der gerichteten Kante e=(y,z).

Niklas Peinecke