imported>Luckyprof: Link eingefügt

2026-03-06T09:56:09Z

Link eingefügt

Neue Seite

[[Datei:Directed.svg|mini|hochkant=0.75|Ein gerichteter Graph mit 3 Knoten und 4 gerichteten Kanten (Doppelpfeil entspricht zwei gegenläufigen Pfeilen)]]

Ein '''gerichteter [[Graph (Graphentheorie)|Graph]]''' oder '''Digraph''' (von englisch ''directed graph'') besteht aus
* einer [[Menge (Mathematik)|Menge]] <math>V</math> von [[Knoten (Graphentheorie)|Knoten]] ({{enS|vertex/vertices}}, oft auch ''Ecken'' genannt) und
* einer Menge [[Geordnetes Paar|geordneter Knotenpaare]] <math>E \subseteq V \times V</math> von [[Kante (Graphentheorie)|Kanten]].<ref name="Diestel2010">{{Literatur |Autor=[[Reinhard Diestel]] |Titel=Graphentheorie |Auflage=4. |Verlag=Springer |Ort=Berlin u. a. |Datum=2010 |ISBN=978-3-642-14911-5 |Seiten=28–30 |Sprache=en |JahrEA=1996 |Online=[https://diestel-graph-theory.com/basic.html 4. elektronische Ausgabe 2010]}}</ref>
Die Kanten <math>(v,w) \in E</math> eines gerichteten Graphen sind [[gerichtete Kante]]n ({{enS|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 [[Ungerichteter Graph|ungerichteten Graphen]] [[Ungeordnetes Paar|ungeordnete Knotenpaare]] <math>\{v,w\}</math>.
Gerichtete Graphen werden dazu benutzt, Objekte und die dazwischenliegenden Verbindungen, beispielsweise von [[Endlicher Automat|endlichen Automaten]], darzustellen.

== Grundbegriffe ==
Ein gerichteter Graph ohne [[Mehrfachkante]]n und [[Schleife (Graphentheorie)|Schleifen]] wird '''einfacher Digraph'''<ref>{{Literatur |Autor=Volker Turau |Titel=Algorithmische Graphentheorie |Auflage=3 |Verlag=Oldenbourg Wissenschaftsverlag |Ort=München |Datum=2009 |ISBN=978-3-486-59057-9 |Seiten=20–24}}</ref> (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 (Graphentheorie)|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 <math>G</math> heißt [[Symmetrischer Graph|symmetrisch]], falls <math>G</math> 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 eine ''Orientierung'' eines [[Einfacher Graph|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.<ref name="Diestel2010" /><ref>{{MathWorld|id=OrientedGraph|title=Oriented Graph}}</ref><ref>{{MathWorld|id=GraphOrientation|title=Graph Orientation}}</ref>

Ein ''gewichteter Digraph'' ist ein Digraph, dessen Kanten Gewichte zugeordnet werden, wodurch man einen [[Kantengewichteter Graph|kantengewichteten Graphen]] erhält. Ein Digraph mit gewichteten Kanten wird in der Graphentheorie als [[Netzwerk (Graphentheorie)|Netzwerk]] bezeichnet.<ref>{{Literatur |Autor=[[Reinhard Diestel]] |Titel=Graphentheorie |Auflage=4. |Verlag=Springer |Ort=Berlin u. a. |Datum=2010 |ISBN=978-3-642-14911-5 |Seiten=145–168 |Sprache=en |JahrEA=1996 |Online=[https://diestel-graph-theory.com/basic.html 4. elektronische Ausgabe 2010]}}</ref>

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

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

=== Zusammenhängende gerichtete Graphen ===
{{Hauptartikel|Zusammenhang (Graphentheorie)}}
Ein gerichteter Graph <math>G</math> heißt ''schwach zusammenhängend'' (oder nur ''zusammenhängend''),<ref>Bang-Jensen, Gutin: ''Digraphs: Theory, Algorithms and Applications,'' 2. Auflage, 2009, S. 20.</ref> 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''.

== Eingangs- und Ausgangsgrad ==
[[Datei:DirectedDegrees.svg|mini|Digraph mit Knotenbeschriftung (Eingangs- und Ausgangsgrad).]]
{{Hauptartikel|Grad (Graphentheorie)#Gerichtete Graphen|titel1=„Gerichtete Graphen“ im Artikel Grad (Graphentheorie)}}
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>|V|-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.<ref>{{Literatur |Autor=Bhavanari Satyanarayana, Kuncham Syam Prasad |Titel=Discrete Mathematics and Graph Theory |Verlag=PHI Learning Pvt. Ltd. |Datum=2009 |ISBN=978-81-203-3842-5 |Seiten=460}}</ref><ref>{{Literatur |Autor=Richard A. Brualdi |Titel=Combinatorial matrix classes |Sammelwerk=Encyclopedia of mathematics and its applications |Band=108 |Verlag=Cambridge University Press |Datum=2006 |ISBN=978-0-521-86565-4 |Seiten=51}}</ref>

== Darstellung von gerichteten Graphen ==
[[Datei:4node-digraph-embed.svg|mini|Der im Beispiel behandelte gerichtete Graph]]
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>\operatorname{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 gerichteten Graphen ==
[[Datei:Directed acyclic graph 2.svg|170px|mini|alt=|Einfach gerichteter azyklischer Graph]][[Datei:4-tournament.svg|mini|137px|[[Turniergraph]] mit 4 [[Knoten (Graphentheorie)|Knoten]]|alternativtext=]]
''Symmetrisch gerichtete Graphen'' sind gerichtete Graphen, bei denen alle [[Kante (Graphentheorie)|Kanten]] [[bidirektional]] sind, d. h. für jede Kante, die zum [[Graph (Graphentheorie)|Graphen]] gehört, gehört auch die entsprechende umgekehrte Kante dazu.

''Einfache gerichtete Graphen'' sind gerichtete Graphen ohne [[Schleife (Graphentheorie)|Schleifen]] und ohne Mehrfachkante.

''Vollständige gerichtete Graphen'' sind einfache gerichtete Graphen, bei denen jedes Knotenpaar durch ein symmetrisches Paar gerichteter Kanten verbunden ist. Dies entspricht einem ungerichteten [[Vollständiger Graph|vollständigen Graphen]], dessen Kanten durch Paare von gerichteten Kanten ersetzt werden. Daraus folgt, dass ein vollständiger gerichteter Graph symmetrisch ist.

''Orientierte Graphen'' sind gerichtete Graphen ohne bidirektionale Kanten. Daraus folgt, dass ein gerichteter Graph genau dann ein orientierter Graph ist, wenn er keinen 2-Zyklus hat.

''[[Turniergraph]]en'' sind orientierte Graphen, die durch Auswahl einer Richtung für jede Kante in ungerichteten vollständigen Graphen erhalten werden.

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

''Gewichtete gerichtete Graphen'' oder ''gerichtete Netzwerke'' sind einfache gerichtete Graphen mit Gewichten, die ihren [[Kante (Graphentheorie)|Kanten]] zugewiesen sind, ähnlich wie gewichtete Graphen, die auch als ungerichtete Netzwerke oder gewichtete Netzwerke bezeichnet werden.

''[[Flussnetzwerk]]e'' sind gewichtete gerichtete Graphen mit zwei speziellen [[Knoten (Graphentheorie)|Knoten]], der ''[[Quelle (Graphentheorie)|Quelle]]'' und der ''[[Grad (Graphentheorie)|Senke]]''.

''[[Kontrollflussgraph]]en'' sind gerichtete Graphen, die in der [[Informatik]] zur Darstellung der [[Pfad (Graphentheorie)|Pfade]] verwendet werden, die während der Ausführung eines [[Computerprogramm]]s durchlaufen werden können.

''[[Signalflussgraph]]en'' sind gewichtete gerichtete Graphen, in denen [[Knoten (Graphentheorie)|Knoten]] [[Systemvariable]]n darstellen und [[Kante (Graphentheorie)|Kanten]] funktionale Verbindungen zwischen Knotenpaaren darstellen.

''[[Zustandsübergangsdiagramm]]e'' sind gerichtete [[Multigraph]]en, die [[Endlicher Automat|endliche Automaten]] darstellen.

''[[Kommutatives Diagramm|Kommutative Diagramme]]'' sind gerichtete Graphen, die in der [[Kategorientheorie]] verwendet werden, wobei die [[Knoten (Graphentheorie)|Knoten]] mathematische Objekte und die [[Kante (Graphentheorie)|Kanten]] mathematische [[Funktion (Mathematik)|Funktionen]] darstellen, mit der Eigenschaft, dass alle gerichteten [[Pfad (Graphentheorie)|Pfade]] mit demselben Start- und Endknoten durch [[Komposition (Mathematik)|Komposition]] zum gleichen Ergebnis führen.

== Kombinatorik ==
Die Anzahl der [[Einfacher Graph|einfachen]] gerichteten Graphen mit <math>n</math> [[Knoten (Graphentheorie)|Knoten]] steigt rasant mit der Anzahl der Knoten und ist gleich <math>4^{\tfrac{n \cdot (n - 1)}{2}}</math>. Sie steigt also [[Exponentieller Verlauf|exponentiell]] zur Anzahl <math>\tfrac{n \cdot (n - 1)}{2}</math> der [[Kante (Graphentheorie)|Kanten]] des [[Vollständiger Graph|vollständigen Graphen]] <math>K_n</math>. Wenn die Knoten nicht nummeriert sind, [[Isomorphie von Graphen|isomorphe Graphen]] also nicht mitgezählt werden, ist diese Anzahl etwa [[Proportionalität|proportional]] zu <math>\tfrac{1}{n!} \cdot 4^{\tfrac{n \cdot (n - 1)}{2}}</math>, weil für die meisten [[Isomorphieklasse]]n alle <math>n!</math> Graphen, die sich durch [[Permutation]] der nummerierten Knoten ergeben, verschieden sind. Die folgende [[Tabelle]] zeigt die mit Hilfe eines [[Computer]]s bestimmten Anzahlen für <math>n \leq 8</math>:<ref>{{OEIS|A000088}}</ref><ref>{{OEIS|A003085}}</ref><ref>{{OEIS|A035512}}</ref>
{| class="wikitable" style="text-align:right"
! colspan="4"|Anzahl der gerichteten Graphen ohne nummerierte Knoten
|-
!n
!alle
!zusammenhängend
!stark zusammenhängend
|-
!1
|1
|1
|1
|-
!2
|3
|2
|1
|-
!3
|16
|13
|5
|-
!4
|218
|199
|83
|-
!5
|9608
|9364
|5048
|-
!6
|1540944
|1530843
|1047008
|-
!7
|882033440
|880471142
|705422362
|-
!8
|1793359192848
|1792473955306
|1580348371788
|}

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C++]] zeigt die Implementierung eines gerichteten Graphen mit [[Adjazenzliste]]n. Der gerichtete Graph wird als [[Klasse (Objektorientierung)|Klasse]] ''DirectedGraph'' deklariert. Bei der Ausführung des Programms wird die [[Methode (Programmierung)|Methode]] ''main'' verwendet.<ref>Software Testing Help: [https://www.softwaretestinghelp.com/graph-implementation-cpp/ Graph Implementation In C++ Using Adjacency List]</ref>
<syntaxhighlight lang="cpp">
#include <iostream>

using namespace std;

// Deklariert den Datentyp für die Knoten des Graphen
struct Node
{
int index;
string value;
Node* next;
};

// Deklariert den Datentyp für die Kanten des Graphen
struct Edge
{
int startIndex;
int endIndex;
};

// Deklariert die Klasse für den gerichteten Graphen
class DirectedGraph
{
public:
Node** headNode;

// Diese Methode fügt einen neuen Knoten in die Adjazenzliste des Graphen ein und gibt ihn als Rückgabewert zurück
Node* insertNewNode(int index, string value, Node* node)
{
Node* newNode = new Node; // Erzeugt einen neuen Knoten vom Typ Node
newNode->index = index; // Setzt den Index
newNode->value = value; // Setzt den Wert
newNode->next = node; // Setzt einen Zeiger auf den Nachfolger
return newNode;
}

// Konstruktor, der den gerichteten Graphen mit den gegebenen Knoten und Kanten erzeugt
DirectedGraph(Node nodes[], Edge edges[], int numberOfEdges, int numberOfNodes)
{
headNode = new Node*[numberOfNodes](); // Initialisiert ein Array von Zeigern für die Knoten
for (int i = 0; i < numberOfEdges; i++) // for-Schleife, die alle Kanten des Graphen durchläuft
{
int startIndex = edges[i].startIndex; // Index des Startknotens der Kante
int endIndex = edges[i].endIndex; // Index des Endknotens der Kante
string value = nodes[endIndex].value; // Wert des Endknotens der Kante
Node* newNode = insertNewNode(endIndex, value, headNode[startIndex]); // Aufruf der Methode insertNewNode, um einen neuen Knoten einzufügen
headNode[startIndex] = newNode; // Setzt den Zeiger auf den neuen Knoten
}
}
};

// Gibt alle benachbarten Knoten von node auf der Konsole aus
void writeAdjacencyList(Node* node, int i)
{
cout << "Knoten " << (i + 1) << ": ";
while (node != nullptr)
{
cout << "(" << node->index << ", " << node->value << ") ";
node = node->next;
}
cout << endl;
}

// Hauptmethode, die das Programm ausführt
int main()
{
// Deklariert und initialisiert Arrays für die Knoten und Kanten
Node nodes[] = { {0,"A"},{1,"B"},{2,"C"},{3,"D"},{4,"E"} };
Edge edges[] = { {0,1},{0,2},{1,4},{2,3},{3,1},{4,3} };
int numberOfNodes = sizeof(nodes) / sizeof(nodes[0]); // Ermittelt die Anzahl der Knoten
int numberOfEdges = sizeof(edges) / sizeof(edges[0]); // Ermittelt die Anzahl der Kanten
DirectedGraph directedGraph(nodes, edges, numberOfEdges, numberOfNodes); // Erzeugt den gerichteten Graphen mit den gegebenen Knoten und Kanten
for (int i = 0; i < numberOfNodes; i++) // for-Schleife, die alle Knoten des Graphen durchläuft
{
Node* headNode = directedGraph.headNode[i];
writeAdjacencyList(headNode, i); // Gibt die Adjazenzliste für den Knoten headNode aus
}
}
</syntaxhighlight>

== Siehe auch ==
* [[Kautz-Graph]]

== Literatur ==
* {{Literatur
|Autor=Jørgen Bang-Jensen, Gregory Gutin
|Titel=Digraphs: Theory, Algorithms and Applications
|Verlag=Springer
|Datum=2000
|ISBN=1-85233-268-9
|Sprache=en
|Online=[https://www.cs.rhul.ac.uk/books/dbook/ rhul.ac.uk]}}
* {{Literatur
|Autor=John Adrian Bondy, U. S. R. Murty
|Titel=Graph Theory with Applications
|Verlag=North-Holland
|Datum=1976
|ISBN=0-444-19451-7}}
* {{Literatur
|Autor=Reinhard Diestel
|Titel=Graph Theory
|Auflage=3.
|Verlag=Springer
|Datum=2005
|ISBN=3-540-26182-6
|Online=https://diestel-graph-theory.com/index.html}}
* {{Literatur
|Autor=Frank Harary, Robert Z. Norman, [[Dorwin Cartwright]]
|Titel=Structural Models: An Introduction to the Theory of Directed Graphs
|Verlag=Wiley
|Ort=New York
|Datum=1965
|Sprache=en}}

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4156815-1}}
[[Kategorie:Gerichteter Graph| ]]

Gerichteter Graph - Versionsgeschichte

imported>Luckyprof: Link eingefügt