Gerichteter Graph - LinkFang.de





Gerichteter Graph


Ein gerichteter Graph oder Digraph (von englisch directed graph) besteht aus

Die Kanten [math](v,w) \in E[/math] eines gerichteten Graphen sind gerichtete Kanten (engl. directed edge/edges, manchmal auch Bögen). Diese werden häufig als Pfeile dargestellt und können nur in einer Richtung durchlaufen werden. Im Gegensatz dazu sind die Kanten eines ungerichteten Graphen ungeordnete Knotenpaare [math]\{v,w\}[/math]. Gerichtete Graphen werden dazu benutzt Objekte und die dazwischenliegenden Verbindungen, beispielsweise von endlichen Automaten, darzustellen.

Grundbegriffe

Ein gerichteter Graph ohne Mehrfachkanten und Schleifen wird einfacher Digraph[2] (auch schlichter Digraph) genannt.

Man sagt, dass eine gerichtete Kante [math]e = (x, y)[/math] von [math]x[/math] nach [math]y[/math] geht. Dabei ist [math]x[/math] der Fuß (oder Startknoten) und [math]y[/math] der Kopf (oder Endknoten) von [math]e[/math]. Weiterhin gilt [math]y[/math] als der direkte Nachfolger von [math]x[/math] und [math]x[/math] als der direkte Vorgänger von [math]y[/math]. Falls in einem Graphen von [math]x[/math] nach [math]y[/math] ein Pfad führt, gilt [math]y[/math] als ein Nachfolger von [math]x[/math] und [math]x[/math] als ein Vorgänger von [math]y[/math]. Die Kante [math](y, x)[/math] heißt umgedrehte oder invertierte Kante von [math](x, y)[/math].

Ein gerichteter Graph G heißt symmetrisch, falls G zu jeder Kante auch die entsprechende invertierte Kante enthält. Ein ungerichteter Graph lässt sich einfach in einen symmetrischen gerichteten Graphen umwandeln, indem man jede Kante [math]\{x, y\}[/math] durch die zwei gerichteten Kanten [math](x, y)[/math] und [math](y, x)[/math] ersetzt.

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. Ein einfach gerichteter Graph darf, im Gegensatz zum orientierten Graphen, zwischen zwei Knoten Kanten in beide Richtungen enthalten.[1][3][4]

Ein gewichteter Digraph ist ein Digraph, dessen Kanten Gewichte zugeordnet werden, wodurch man einen kantengewichteten Graphen erhält. Ein Digraph mit gewichteten Kanten wird in der Graphentheorie als Netzwerk bezeichnet.[5]

Die Adjazenzmatrix eines Digraphen (mit Schleifen und Mehrfachkanten) ist eine ganzzahlige Matrix, deren Zeilen und Spalten den Knoten des Digraphen entsprechen. Ein Eintrag [math]a_{ij}[/math] außerhalb der Hauptdiagonalen gibt die Anzahl der Kanten vom Knoten i zum Knoten j an, und der Eintrag der Hauptdiagonalen [math]a_{ii}[/math] entspricht der Anzahl der Schleifen im Knoten i. Die Adjazenzmatrix eines Digraphen ist bis auf Vertauschung von Zeilen und Spalten eindeutig.

Ein Digraph lässt sich auch durch eine Inzidenzmatrix repräsentieren.

Eingangs- und Ausgangsgrad

Die Anzahl der direkten Vorgänger eines Knotens wird Eingangsgrad (auch Innengrad) und die Anzahl der direkten Nachfolger Ausgangsgrad (oder Außengrad) genannt.

Der Eingangsgrad eines Knotens [math]v[/math] in einem Graphen [math]G[/math] wird mit [math]d_G^-(v)[/math] und der Außengrad mit [math]d_G^+(v)[/math] bezeichnet. Ein Knoten mit [math]d_G^-(v)=0[/math] wird Quelle und ein Knoten mit [math]d_G^+(v)=0[/math] wird Senke genannt. Eine Senke heißt universelle Senke, falls sie eingehende Kanten von jedem anderen Knoten hat, falls also ihr Eingangsgrad gleich [math]\mid V\mid-1[/math] ist.

Für gerichtete Graphen ist die Summe aller Eingangsgrade gleich der Summe aller Ausgangsgrade, und beide gleich der Summe der gerichteten Kanten:

[math]\sum_{v \in V} d_G^+(v) = \sum_{v \in V} d_G^-(v) = |E|\, .[/math]

Falls für alle Knoten [math]v \in V[/math] die Gleichung [math]d_G^+(v) = d_G^-(v)[/math] gilt, wird der Graph balancierter Digraph genannt.[6][7]

Zusammenhang von Digraphen

Ein gerichteter Graph [math]G[/math] heißt schwach zusammenhängend (oder nur zusammenhängend),[8] falls der unterliegende Graph von [math]G[/math], den man mittels Ersetzung aller gerichteter Kanten durch ungerichtete erhält, ein zusammenhängender Graph ist. Ein gerichteter Graph heißt stark zusammenhängend oder stark, wenn je zwei seiner Knoten gegenseitig erreichbar sind. Ein maximaler stark zusammenhängender Untergraph von [math]G[/math] ist eine starke Komponente.

Darstellung von gerichteten Graphen

Außer der naiven Darstellung eines gerichteten Graphen durch Angabe der Knoten- und Kantenmenge gibt es noch weitere Darstellungsmöglichkeiten, das sogenannte Kanten bzw Knotenfeld.

Kantenfeld

Ein Kantenfeld ist eine Darstellungsart für gerichtete Graphen nach folgendem Schema:

[math]|V|, |E|, E_1,\ldots, E_{|E|}[/math],

wobei [math]|V|[/math] die Anzahl der Knoten, [math]|E|[/math] die Anzahl der Kanten und [math] E_1, \ldots, E_{|E|}[/math] die Kanten mit [math] E_i = (v, w) \in E [/math] sind.

Knotenfeld

Ein Knotenfeld ist eine Darstellungsart für gerichtete Graphen mit folgendem Aufbau:

[math]|V|, |E|, \text{ag}(V_1), \text{Ziel}_1, \ldots, \text{Ziel}_{\text{ag}(V_1)}, \ldots, \text{ag}(V_{|V|}), \text{Ziel}_1, \ldots, \text{Ziel}_{\text{ag}(V_{|V|})}[/math],

wobei [math]|V|[/math] die Anzahl der Knoten, [math]|E|[/math] die Anzahl der Kanten und [math]ag(V)[/math] der Ausgangsgrad des Knotens [math]V[/math] sind.

Beispiel

Betrachtet man als Beispiel den rechts stehenden gerichteten Graph, so ist das Kantenfeld [math] 4,6,(1,2),(1,4),(2,4),(3,1),(3,2),(4,3)[/math] und das Knotenfeld [math]4,6,\mathbf{2},2,4,\mathbf{1},4,\mathbf{2},1,2,\mathbf{1},3[/math]. Die fett gedruckten Zahlen geben den Ausgangsgrad an.

Klassen von Digraphen

Ein gerichteter azyklischer Graph oder azyklischer Digraph ist ein gerichteter Graph, der keinen gerichteten Kreis enthält. Spezialfälle gerichteter azyklischer Graphen sind Mehrfachbäume (je zwei gerichtete Pfade des Graphen, die vom selben Startknoten ausgehen, dürfen sich nicht im selben Endknoten treffen), orientierte Bäume oder Polybäume (Orientierung eines ungerichteten azyklischen Graphen) und Wurzelbäume (orientierte Bäume, bei denen alle Kanten des unterliegenden ungerichteten Baumes vom Wurzelknoten wegführen).

Ein Turniergraph ist eine Orientierung des vollständigen Graphen [math]K_n[/math].

Spezielle gerichtete Graphen

Literatur

Einzelnachweise

  1. 1,0 1,1 Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin u. a. 2010, ISBN 978-3-642-14911-5, S. 28–30 (4. elektronische Ausgabe 2010 (englisch) Erstausgabe: 1996).
  2. Volker Turau: Algorithmische Graphentheorie. 3. Auflage. Oldenbourg Wissenschaftsverlag, München 2009, ISBN 978-3-486-59057-9, S. 20–24.
  3. Eric W. Weisstein: Oriented Graph . In: MathWorld (englisch).
  4. Eric W. Weisstein: Graph Orientation . In: MathWorld (englisch).
  5. Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin u. a. 2010, ISBN 978-3-642-14911-5, S. 145–168 (4. elektronische Ausgabe 2010 (englisch) Erstausgabe: 1996).
  6. Bhavanari Satyanarayana, Kuncham Syam Prasad: Discrete Mathematics and Graph Theory. PHI Learning Pvt. Ltd., ISBN 978-81-203-3842-5, S. 460.
  7. Richard A. Brualdi: Combinatorial matrix classes. In: Encyclopedia of mathematics and its applications. Band 108. Cambridge University Press, 2006, ISBN 978-0-521-86565-4, S. 51.
  8. Bang-Jensen, Gutin: Digraphs: Theory, Algorithms and Applications, 2. Auflage, 2009, S. 20.

Kategorien: Gerichteter Graph

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Gerichteter Graph (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.