Diskussion:Gerichteter Graph

Ohne Titel

bezeichnet man in der Graphentheorie einen Graph, der gerichtete Kanten enthalten kann.

Ist es nicht eher so, dass ein gerichteter Graph aussschliesslich gerichtete Kanten enthaelt? --zeno 14:35, 5. Mär 2004 (CET)

Das ist Ansichtssache und daher obige Formulierung allgemeingültiger. Zwei gerichtete Kanten mit unterschiedlicher Orientierung, die die selben Knoten verbinden, fasst man auch zu einer ungerichteten Kante zusammen. --Coma 14:48, 5. Mär 2004 (CET)

Eigentlich gibt es (mathematisch) keine eigene Klasse für ungerichteten Graphen. Ein Graph, als grafische Darstellung einer Relation, ist ungerichtet, wenn zu jeder Kante eine Gegenkante existiert bzw. eine Relation R gleich ihrer Transponierten R^T ist - die Relation also symmetrisch ist, oder?. Ford Prefect 00:20, 14. Jun 2004 (CET)

ungerichte Graphen werden aber gewöhnlich nicht über Relationen definiert, sondern die Kantenmenge ist eine Teilmenge aller zweielementigen Teilmengen aller Knoten. Insofern gibt es sehr wohl eine eigene Klasse für ungerichtete Graphen. Gerichtete Graphen stellen nur eine Verallgemeinerung dar, die aber häufig garnicht gebraucht wird. --Coma 13:58, 14. Jun 2004 (CEST)

Ein Graph welcher nur aus einem einzigen Knoten besteht ist ein gerichteter Graph. Wenn man sich zum Beispiel die definition von Bäumen ansieht (<== spezialfall gerichteter Graphen) so sind diese immer noch Bäume auch wenn sie nur aus einem Knoten bestehen. Würde man verlangen, daß ein gerichteter Graph mindestens eine Kante enthält würde man viele Situationen deutlich verkomplizieren (z.B die initialisierung von Bäumen)--Horratio 20:01, 3. Feb 2006 (CET)

Was soll die Bemerkung? Abgesehen davon, dass sie nicht ganz korrekt ist. Natürlich ist ein (isolierter) Knoten ein gerichteter Graph. Er ist gleichzeitig aber auch Ungerichtet! Im übrigen gibt es auch ungerichtete Bäume! Wer verlangt, dass ein gerichteter Graph mindestens eine Kante enthält? Wenns so im Artikel steht, gehört das nat. genauer formuliert. :-) --Koethnig 22:13, 3. Feb 2006 (CET)

Ok, es stand tatsächlich so im Artikel, ich habs korrigiert. Ist jetzt natürlich nicht mehr so Oma-Tauglich... --Koethnig 22:16, 3. Feb 2006 (CET)

Definition

Ich habe gerade eine alternative Definition in "Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 1. Auflage. Teubner Verlag, Wiesbaden 2005, ISBN 3-519-00526-3, S. 7. " gefunden:

"Ein gerichteter Graph (kurz Graph) ist ein Quadrupel <maht>G = (V, R, \alpha, \omega)</math> mit folgenden Eigenschaften: (i) V ist eine nichtleere Menge, die Eckenmenge des Graphen. (ii) R ist eine Menge, die Pfeilmenge des Graphen. (iii) Es gilt $V\cap R=\emptyset$ (iv) $\alpha :R\rightarrow V$ und $\omega :R\rightarrow V$ sind Abbildungen ($\alpha (r)$ ist die Anfangsecke, $\omega (r)$ die Endecke des Pfeils r)."

Das ist allerdings das erste mal, dass ich in einem Buch von "Ecken" anstelle von "Knoten" lese. Auch die Definition als Quadrupel ist mir neu. Ich habe bisher immer von Tupeln gelesen. Kann jemand eine Quelle nennen, die auch von Tupeln spricht? --Martin Thoma 12:12, 14. Jul. 2012 (CEST)

Verwirrende Formulierung

Es heißt im Artikel "Um die Orientierung eines einfachen ungerichteten Graphen zu erhalten, muss jeder Kante eine Richtung zugewiesen werden. Jeder auf diese Art konstruierte gerichtete Graph wird orientierter Graph genannt.".

Das ist so zwar korrrekt, da ein orientierter Graph ein gerichteter Graph ist (d.h. ein Spezialfall), allerdings zur Veranschaulichung des orientierten Graphen vorraus zu setzen, dass man aus einem ungerichteten Graphen einen orientierten Graphen "erhalten" möchte ist doch etwas umständlich formuliert und tut nichts zur Sache.

Vielleicht kann man es einfacher definieren / formulieren: Enthält ein gerichteter Graph ausschließlich gerichtete Kanten einer Richtung (d.h. keine symetrischen Kanten, oder formal: für alle (x k,x i)∈E gilt (x i,x k)∉E), heißt der Graph orientierter Graph. Damit ist jeder orientierte Graph gleichzeitig ein gerichteter Graphen und ein Spezialfall des orientierten Graphen.

--Dawjdh (Diskussion) 15:41, 11. Sep. 2012 (CEST)

Ich finde die im Artikel verwendete Definition anschaulicher. Sie verdeutlicht, wieso so ein Digraph orientiert genannt wird. Außerdem ist die Definition so in Lehrbüchern zu finden. Zudem fehlt bei deinem Vorschlag, dass ein orientierter Graph einfach ist (also keine parallelen Kanten enthält) und du schreibst: "Damit ist jeder orientierte Graph [...] ein Spezialfall des orientierten Graphen." Das ist doch trivial oder was soll damit gemeint sein?--Stan227 (Diskussion) 03:13, 14. Jan. 2015 (CET)

Fehlende Verständlichkeit

Als Sozialwissenschaftler kam ich über einen Link von "Stammbaum" (Genealogie) hierhin… und verstehe so gut wie kein Wort :-(

Sorry, aber es fehlt grundlegende Didaktik, vor allem 1–2 Sätze mit einleitenden Erläuterungen für Laien (Wikipedia:Allgemeinverständlichkeit). --Chiananda (Diskussion) 13:35, 19. Nov. 2013 (CET)

sollte jetzt zumindest ein wenig verständlicher sein Poipo (Diskussion) 22:02, 3. Feb. 2015 (CET)

Bildbeschriftung

Im Bild zum ersten Absatz heißt es: "Ein gerichteter Graph mit 3 Knoten und 4 gerichteten Kanten". Ich sehe aber nur drei Punkte und drei Pfeile. Wo sind denn die 4 Kanten? --217.92.62.21 15:01, 15. Jan. 2019 (CET)

Bildbeschriftung ist korrigiert. --Uncopy (Diskussion) 09:23, 13. Jun. 2019 (CEST)

Der Doppelpfeil steht für zwei gerichtete Kanten, man würde eigentlich zwei gegenläufige Pfeile einzeichnen.--Sinuhe20 (Diskussion) 12:05, 13. Jun. 2019 (CEST)

Ah, alles klar. Nach den Pfeilspitzen hatte ich gar nicht geschaut. Vielleicht sollte man die Beschriftung erweitern? Beispiel: Der Doppelpfeil fasst zwei gegenläufige Pfeile zusammen. --Uncopy (Diskussion) 12:57, 13. Jun. 2019 (CEST)

Klingt jetzt aber sehr umständlich. Man muss nur den Unterschied zwischen „Kante“ und „gerichteter Kante“ kennen.--Sinuhe20 (Diskussion) 13:28, 13. Jun. 2019 (CEST)

Ich habe den Hinweis mal untergebracht, vielleicht wäre es im Text besser aufgehoben, vielleicht wäre auch eingangs ein völlig unmissverständliches Bild gut und ein eigener Abschnitt zur Darstellung könnte die Pfeilvarianten erklären? Ich möchte darauf hinaus, dass der Artikel beim ersten Lesen niemanden ins Stolpern bringt. Wer bereits weiß worauf es ankommt, übersieht die Problemzonen. BTW: m.E. werden im Intro ungerichtete Graphen zu detailliert erklärt, um sie geht es hier schließlich nicht. --Uncopy (Diskussion) 14:13, 13. Jun. 2019 (CEST)