Gerichteter vs. ungerichteter Graph
Ein Graph ist eine mathematische Struktur, die aus einer Reihe von Scheitelpunkten und Kanten besteht. Ein Graph stellt eine Menge von Objekten dar (dargestellt durch Scheitelpunkte), die durch einige Verbindungen (dargestellt durch Kanten) verbunden sind. Unter Verwendung mathematischer Notationen kann ein Graph durch G dargestellt werden, wobei G=(V, E) und V die Menge der Scheitelpunkte und E die Menge der Kanten ist. In einem ungerichteten Graphen ist den Kanten, die die Scheitelpunkte verbinden, keine Richtung zugeordnet. In einem gerichteten Graphen ist den Kanten, die die Scheitelpunkte verbinden, eine Richtung zugeordnet.
Ungerichteter Graph
Wie bereits erwähnt, ist ein ungerichteter Graph ein Graph, bei dem es keine Richtung in den Kanten gibt, die die Scheitelpunkte im Graphen verbinden. Abbildung 1 zeigt einen ungerichteten Graphen mit einem Satz von Scheitelpunkten V={V1, V2, V3}. Der Satz von Kanten im obigen Diagramm kann als V={(V1, V2), (V2, V3), (V1, V3)} geschrieben werden. Es kann auch angemerkt werden, dass nichts dagegen spricht, den Satz von Kanten als V={(V2, V1), (V3, V2), (V3, V1)} zu schreiben, da die Kanten keine Richtung haben. Daher sind Kanten in einem ungerichteten Graphen keine geordneten Paare. Dies ist das Hauptmerkmal eines ungerichteten Graphen. Ungerichtete Graphen können verwendet werden, um symmetrische Beziehungen zwischen Objekten darzustellen, die durch Scheitelpunkte dargestellt werden. Beispielsweise kann ein zweispuriges Straßennetz, das mehrere Städte verbindet, mit einem ungerichteten Graphen dargestellt werden. Die Städte können durch die Scheitelpunkte im Diagramm dargestellt werden und die Kanten stellen die zweispurigen Straßen dar, die die Städte verbinden.
Gerichteter Graph
Ein gerichteter Graph ist ein Graph, in dem die Kanten im Graphen, die die Scheitelpunkte verbinden, eine Richtung haben. Abbildung 2 zeigt einen gerichteten Graphen mit einem Satz von Scheitelpunkten V={V1, V2, V3}. Der Satz von Kanten im obigen Diagramm kann als V={(V1, V2), (V2, V3), (V1, V3)} geschrieben werden. Kanten in einem ungerichteten Graphen sind geordnete Paare. Formal kann die Kante e in einem gerichteten Graphen durch das geordnete Paar e=(x, y) dargestellt werden, wobei x der Scheitelpunkt ist, der als Ursprung, Quelle oder Anfangspunkt der Kante e bezeichnet wird, und der Scheitelpunkt y als Endpunkt bezeichnet wird, Endknoten oder Endpunkt. Beispielsweise kann ein Straßennetz, das mehrere Städte über Einbahnstraßen verbindet, mit einem ungerichteten Graphen dargestellt werden. Die Städte können durch die Scheitelpunkte im Diagramm dargestellt werden, und die gerichteten Kanten stellen die Straßen dar, die die Städte unter Berücksichtigung der Richtung verbinden, in der der Verkehr auf der Straße fließt.
Was ist der Unterschied zwischen gerichtetem Graph und ungerichtetem Graph?
In einem gerichteten Graphen ist eine Kante ein geordnetes Paar, wobei das geordnete Paar die Richtung der Kante darstellt, die die beiden Scheitelpunkte verbindet. Andererseits ist eine Kante in einem ungerichteten Graphen ein ungeordnetes Paar, da einer Kante keine Richtung zugeordnet ist. Ungerichtete Graphen können verwendet werden, um symmetrische Beziehungen zwischen Objekten darzustellen. In-Grad und Out-Grad jedes Knotens in einem ungerichteten Graphen sind gleich, aber dies gilt nicht für einen gerichteten Graphen. Wenn eine Matrix verwendet wird, um einen ungerichteten Graphen darzustellen, wird die Matrix immer zu einem symmetrischen Graphen, aber das gilt nicht für gerichtete Graphen. Ein ungerichteter Graph kann in einen gerichteten Graphen umgewandelt werden, indem jede Kante durch zwei gerichtete Kanten ersetzt wird, die in entgegengesetzte Richtungen gehen. Es ist jedoch nicht möglich, einen gerichteten Graphen in einen ungerichteten Graphen umzuwandeln.
