Node, Vertex, Edge und Arc: Unterschiede einfach erklärt

Wer sich mit Graphentheorie, Netzwerken, Algorithmen oder Datenstrukturen beschäftigt, begegnet schnell den Begriffen Node, Vertex, Edge und Arc. Alle vier Begriffe beschreiben grundlegende Bestandteile eines Graphen. Allerdings werden sie je nach Fachgebiet, Lehrbuch und Softwarebibliothek unterschiedlich verwendet.

Eine häufig genannte Erklärung lautet:

• Ein gerichteter Graph besteht aus Nodes und Arcs.
• Ein ungerichteter Graph besteht aus Vertices und Edges.

Diese Einteilung ist zwar als grobe Merkhilfe verständlich, fachlich aber zu streng. Node und Vertex sind grundsätzlich Synonyme. Auch Edge wird sowohl für ungerichtete als auch für gerichtete Verbindungen verwendet. Der Begriff Arc bezeichnet dagegen häufig eine gerichtete Verbindung, ist aber ebenfalls nicht überall verbindlich definiert. Die Begriffe im schnellen Überblick

Die wichtigste Erkenntnis lautet daher:

Node und Vertex bezeichnen normalerweise dasselbe. Edge ist der allgemeine Begriff für eine Verbindung. Arc wird häufig speziell für eine gerichtete Verbindung verwendet.

Was ist ein Graph?

Ein Graph ist eine mathematische Struktur, mit der Beziehungen zwischen Objekten dargestellt werden. Er besteht aus einer Menge von Knoten und einer Menge von Verbindungen zwischen diesen Knoten.

Ein Graph wird häufig folgendermaßen definiert:

[
G=(V,E)
]

Dabei steht:

• (G) für den gesamten Graphen,
• (V) für die Menge der Knoten,
• (E) für die Menge der Kanten.

Das Zeichen (V) stammt vom englischen Wort Vertices, dem Plural von Vertex. Das Zeichen (E) stammt vom englischen Wort Edges.

Ein einfaches Beispiel lautet:

[
V={A,B,C}
]

[
E={{A,B},{B,C}}
]

Der Graph enthält drei Knoten. Eine Kante verbindet A mit B, eine weitere Kante verbindet B mit C.

Das National Institute of Standards and Technology definiert einen Graphen als eine Menge von Elementen, die durch Kanten miteinander verbunden sind. Diese Elemente können gleichermaßen als Vertices oder Nodes bezeichnet werden. Was ist ein Node?

Ein Node ist ein Knoten innerhalb eines Graphen, Netzwerks oder einer Datenstruktur. Er stellt ein Objekt, einen Zustand, einen Ort oder einen anderen modellierten Sachverhalt dar.

Abhängig vom Anwendungsgebiet kann ein Node beispielsweise Folgendes repräsentieren:

• eine Person in einem sozialen Netzwerk,
• eine Stadt in einem Verkehrsnetz,
• einen Computer in einem Datennetz,
• eine Webseite im World Wide Web,
• einen Arbeitsschritt in einem Produktionsprozess,
• einen Zustand in einem Zustandsautomaten,
• einen Datensatz in einer Graphdatenbank.

Der Begriff Node wird besonders häufig in der Informatik verwendet. Auch bei Bäumen, verketteten Listen, Netzwerken und Graphdatenbanken ist überwiegend von Nodes die Rede.

Nach der Definition des NIST ist ein Node eine Referenzeinheit innerhalb einer Datenstruktur. In Graphen und Bäumen wird ein Node auch als Vertex bezeichnet. Was ist ein Vertex?

Ein Vertex ist ebenfalls ein Knoten eines Graphen. Der Begriff wird vor allem in der mathematischen und theoretischen Graphentheorie verwendet.

Die Mehrzahl von Vertex lautet:

• Vertices als gebräuchliche mathematische Form,
• gelegentlich auch Vertexes.

Inhaltlich besteht zwischen einem Node und einem Vertex normalerweise kein Unterschied. Beide Begriffe bezeichnen ein Element der Knotenmenge (V).

Das NIST beschreibt einen Vertex ausdrücklich als ein Element eines Graphen, das auch als Node bezeichnet werden kann. it gilt:

[
\text{Node} \approx \text{Vertex}
]

Die Wahl des Begriffs hängt primär von der jeweiligen Fachsprache ab:

• In der Mathematik ist Vertex üblicher.
• In der Informatik ist Node häufig gebräuchlicher.
• In Softwarebibliotheken können beide Begriffe vorkommen.
• Innerhalb eines Dokuments sollte eine einheitliche Terminologie verwendet werden.

Gibt es einen Unterschied zwischen Node und Vertex?

In der allgemeinen Graphentheorie gibt es keinen inhaltlichen Unterschied zwischen Node und Vertex.

Beide Begriffe können sowohl bei gerichteten als auch bei ungerichteten Graphen verwendet werden. Es ist daher nicht korrekt, Nodes ausschließlich gerichteten Graphen und Vertices ausschließlich ungerichteten Graphen zuzuordnen.

Auch die verbreitete Python-Bibliothek NetworkX beschreibt einen Graphen als eine Menge von „nodes“, wobei sie „vertices“ ausdrücklich als gleichbedeutenden Begriff nennt. Für gerichtete Graphen verwendet NetworkX weiterhin den Begriff Node. Unterschied liegt somit eher im Sprachgebrauch:

In der Computergrafik besitzt Vertex zudem eine speziellere Bedeutung: Ein Vertex ist dort häufig ein geometrischer Punkt eines dreidimensionalen Modells. Diese Verwendung darf nicht mit der allgemeinen Bedeutung eines Knotens in einem Netzwerk verwechselt werden.

Was ist eine Edge?

Eine Edge ist eine Kante oder Verbindung zwischen zwei Knoten eines Graphen.

Bei einem ungerichteten Graphen verbindet eine Edge zwei Knoten ohne festgelegte Richtung. Die Verbindung kann gedanklich in beide Richtungen genutzt werden.

Eine ungerichtete Kante zwischen den Knoten (A) und (B) kann als ungeordnetes Paar geschrieben werden:

[
{A,B}
]

Daraus folgt:

[
{A,B}={B,A}
]

Die Reihenfolge der Knoten spielt bei einer ungerichteten Kante keine Rolle.

Beispiele für ungerichtete Kanten sind:

• eine gegenseitige Freundschaft,
• eine Straße, die in beide Richtungen befahren werden kann,
• eine physische Kabelverbindung,
• eine direkte Verbindung zwischen zwei Geräten,
• eine Kooperation zwischen zwei Unternehmen.

Der Begriff Edge wird jedoch nicht ausschließlich für ungerichtete Graphen verwendet. Auch bei gerichteten Graphen sprechen zahlreiche Lehrbücher und Softwarebibliotheken von directed edges, also gerichteten Kanten. Das NIST definiert eine Edge allgemein als Verbindung zwischen zwei Vertices und erläutert ausdrücklich auch ihre Verwendung in gerichteten Graphen. Was ist ein Arc?

Ein Arc bezeichnet in vielen Fachgebieten eine gerichtete Verbindung zwischen zwei Knoten.

Eine gerichtete Verbindung von (A) nach (B) wird als geordnetes Paar dargestellt:

[
(A,B)
]

Hierbei gilt im Allgemeinen:

[
(A,B)\neq(B,A)
]

Der erste Knoten ist der Ausgangsknoten, der zweite Knoten der Zielknoten.

Für die beiden Enden einer gerichteten Verbindung werden verschiedene Bezeichnungen verwendet:

Ein Arc von A nach B bedeutet nicht automatisch, dass auch eine Verbindung von B nach A besteht.

Typische Beispiele sind:

• eine Einbahnstraße,
• eine Überweisung von einem Konto zu einem anderen,
• ein Link von einer Webseite zu einer anderen,
• ein Materialfluss innerhalb einer Produktion,
• eine Abhängigkeit zwischen Arbeitsschritten,
• ein Übergang in einem Zustandsdiagramm.

Der Begriff Arc wird häufig in der Netzwerkoptimierung, bei Flussproblemen und bei gerichteten Graphen eingesetzt. Das NIST führt Arc allerdings auch als alternative Bezeichnung für Edge an. Damit ist Arc zwar häufig spezifischer, aber nicht in allen Quellen eindeutig von Edge abgegrenzt. Unterschied zwischen Edge und Arc

Zwischen Edge und Arc besteht eine stärkere sprachliche Tendenz als zwischen Node und Vertex:

• Edge ist der allgemeine Begriff für eine Kante.
• Arc bezeichnet häufig eine gerichtete Kante.

Eine universell verbindliche Regel existiert jedoch nicht.

In manchen Lehrbüchern wird streng unterschieden:

• Edge für eine ungerichtete Verbindung,
• Arc für eine gerichtete Verbindung.

Andere Quellen verwenden Edge sowohl für gerichtete als auch für ungerichtete Verbindungen. In diesem Fall wird durch Zusätze unterschieden:

• undirected edge,
• directed edge.

Beide Schreibweisen sind fachlich zulässig. Entscheidend ist, dass die verwendete Definition am Anfang eines Textes oder Modells eindeutig festgelegt wird.

Eine sinnvolle Konvention lautet:

Diese Konvention verbessert die Verständlichkeit, stellt aber keine zwingende allgemeine Regel dar.

Gerichtete und ungerichtete Graphen

Der wesentliche Unterschied liegt nicht zwischen Node und Vertex, sondern zwischen gerichteten und ungerichteten Verbindungen.

Ungerichteter Graph

Bei einem ungerichteten Graphen besitzen die Kanten keine Orientierung.

Formal besteht ein ungerichteter Graph aus einer Knotenmenge (V) und einer Kantenmenge (E). Jede Kante ist ein ungeordnetes Paar von Knoten. spiel:

[
E={{A,B},{B,C}}
]

A ist mit B verbunden und B mit C. Die Verbindungen gelten jeweils in beide Richtungen.

Gerichteter Graph

Bei einem gerichteten Graphen besitzen die Kanten eine festgelegte Orientierung.

Jede gerichtete Kante ist ein geordnetes Paar:

[
(A,B)
]

Der Graph erlaubt eine Bewegung oder Beziehung von A nach B. Eine Rückrichtung besteht nur, wenn zusätzlich die Kante ((B,A)) vorhanden ist.

Das NIST definiert einen gerichteten Graphen als einen Graphen, dessen Kanten geordnete Paare von Vertices sind. gerichteter Graph kann folgendermaßen geschrieben werden:

[
G=(V,E)
]

Alternativ wird häufig die Bezeichnung (A) für die Menge der Arcs verwendet:

[
G=(V,A)
]

Beide Notationen sind möglich, sofern die verwendeten Symbole eindeutig definiert werden.

Beispiel eines ungerichteten Graphen

Ein soziales Netzwerk soll drei Personen darstellen:

[
V={\text{Anna},\text{Ben},\text{Clara}}
]

Anna ist mit Ben befreundet. Ben ist mit Clara befreundet.

[
E={{\text{Anna},\text{Ben}},{\text{Ben},\text{Clara}}}
]

Da eine Freundschaft in diesem Modell gegenseitig ist, werden ungerichtete Edges verwendet.

Die Personen können sowohl als Nodes als auch als Vertices bezeichnet werden.

Beispiel eines gerichteten Graphen

Ein Bestellprozess besteht aus drei Schritten:

[
V={\text{Bestellung},\text{Prüfung},\text{Versand}}
]

Die möglichen Übergänge lauten:

[
A={(\text{Bestellung},\text{Prüfung}),(\text{Prüfung},\text{Versand})}
]

Der Prozess läuft in einer bestimmten Richtung. Von der Bestellung führt ein Arc zur Prüfung und von der Prüfung ein weiterer Arc zum Versand.

Eine direkte Rückkehr vom Versand zur Prüfung ist nicht vorgesehen. Dafür müsste ein zusätzlicher Arc definiert werden.

Gewichtete Kanten und Arcs

Kanten können zusätzliche Werte besitzen. Ein solcher Graph wird als gewichteter Graph bezeichnet.

Das Gewicht kann beispielsweise folgende Größen darstellen:

• Entfernung,
• Fahrzeit,
• Kosten,
• Kapazität,
• Energieverbrauch,
• Risiko,
• Wahrscheinlichkeit,
• Datenmenge.

Bei einem Straßennetz kann eine Edge zwischen Graz und Wien beispielsweise mit der Fahrstrecke gewichtet werden.

[
w(\text{Graz},\text{Wien})=200
]

In einem gerichteten Transportnetz kann ein Arc zusätzlich eine maximale Kapazität besitzen:

[
c(A,B)=500
]

Das bedeutet, dass höchstens 500 Einheiten von A nach B transportiert werden können.

Gewichtete Verbindungen können sowohl gerichtet als auch ungerichtet sein. Ein gewichteter gerichteter Graph besitzt dementsprechend Gewichte auf seinen gerichteten Edges beziehungsweise Arcs. Weitere wichtige Begriffe der Graphentheorie

Adjazenz

Zwei Knoten sind adjazent oder benachbart, wenn sie durch eine Kante miteinander verbunden sind.

Grad eines Knotens

Der Grad eines Knotens gibt bei einem ungerichteten Graphen an, wie viele Kanten mit diesem Knoten verbunden sind.

Eingangsgrad

Der Eingangsgrad oder In-Degree gibt an, wie viele gerichtete Kanten in einen Knoten hineinführen.

Ausgangsgrad

Der Ausgangsgrad oder Out-Degree gibt an, wie viele gerichtete Kanten einen Knoten verlassen.

Pfad

Ein Pfad ist eine Folge von Knoten und Kanten, über die ein Zielknoten von einem Ausgangsknoten erreicht werden kann.

Schleife

Eine Schleife oder ein Self-Loop ist eine Kante, deren Start- und Zielknoten identisch sind:

[
(A,A)
]

Parallelkanten

Parallelkanten sind mehrere Verbindungen zwischen denselben Knoten. Ein Graph, der solche Kanten erlaubt, wird als Multigraph bezeichnet.

Häufige Fehler bei Node, Vertex, Edge und Arc

Fehler 1: Node nur für gerichtete Graphen verwenden

Nodes können sowohl in gerichteten als auch in ungerichteten Graphen vorkommen. Die Richtung betrifft die Kante, nicht die Bezeichnung des Knotens.

Fehler 2: Vertex nur für ungerichtete Graphen verwenden

Auch gerichtete Graphen bestehen aus Vertices. Das NIST definiert einen gerichteten Graphen ausdrücklich über geordnete Paare von Vertices. Fehler 3: Edge ausschließlich als ungerichtete Kante verstehen

Edge wird häufig als Oberbegriff verwendet. Auch NetworkX bezeichnet die gerichteten Verbindungen eines DiGraph als Edges. Fehler 4: Arc als zwingende Bezeichnung ansehen

Arc wird häufig für gerichtete Kanten verwendet. Andere Quellen verwenden stattdessen directed edge. Beide Varianten sind üblich.

Fehler 5: Begriffe innerhalb eines Modells wechseln

Wer in einer Dokumentation zunächst von Vertices und anschließend ohne Erklärung von Nodes spricht, erzeugt unnötige Unsicherheit. Eine einmal gewählte Terminologie sollte durchgehend verwendet werden.

Welche Begriffe sollte man verwenden?

Für mathematische Texte bietet sich folgende Terminologie an:

• Vertex beziehungsweise Vertices,
• Edge beziehungsweise Edges,
• directed edge oder Arc bei gerichteten Kanten.

Für Informatik- und Programmiertexte ist häufig folgende Variante verständlicher:

• Node beziehungsweise Nodes,
• Edge beziehungsweise Edges,
• directed edge bei gerichteten Verbindungen.

In Netzwerkflussmodellen ist diese Schreibweise besonders eindeutig:

• Node für den Knoten,
• Edge für eine ungerichtete Verbindung,
• Arc für eine gerichtete Verbindung.

Entscheidend ist nicht die Auswahl einer vermeintlich einzig richtigen Bezeichnung. Entscheidend ist eine klare Definition und die konsequente Verwendung innerhalb des gesamten Modells.

Häufige Fragen

Sind Node und Vertex dasselbe?

Ja. In der Graphentheorie bezeichnen Node und Vertex grundsätzlich einen Knoten. Vertex wird häufiger in der Mathematik verwendet, Node häufiger in der Informatik.

Ist eine Edge immer ungerichtet?

Nein. Edge kann sowohl eine ungerichtete als auch eine gerichtete Kante bezeichnen. Bei einer gerichteten Kante wird häufig von einer directed edge gesprochen.

Ist ein Arc immer gerichtet?

Arc wird überwiegend für gerichtete Kanten verwendet. Einige Quellen nutzen Arc jedoch allgemeiner als Synonym für Edge. Die genaue Bedeutung muss daher aus dem jeweiligen Kontext hervorgehen.

Kann ein gerichteter Graph Vertices besitzen?

Ja. Gerichtete und ungerichtete Graphen können gleichermaßen aus Vertices beziehungsweise Nodes bestehen.

Warum wird manchmal (G=(V,A)) statt (G=(V,E)) geschrieben?

Bei gerichteten Graphen wird gelegentlich (A) für die Menge der Arcs verwendet. Andere Quellen behalten auch bei gerichteten Graphen das Symbol (E) für Edges bei.

Welche Bezeichnung ist für eine wissenschaftliche Arbeit richtig?

In mathematischen Arbeiten sind Vertex und Edge besonders verbreitet. Bei gerichteten Graphen können directed edge oder Arc verwendet werden. Die Begriffe müssen am Anfang eindeutig definiert und anschließend konsistent eingesetzt werden.

Fazit

Node und Vertex sind im Kontext der Graphentheorie grundsätzlich Synonyme. Beide Begriffe bezeichnen einen Knoten und können unabhängig davon verwendet werden, ob ein Graph gerichtet oder ungerichtet ist.

Edge ist der allgemeine englische Begriff für eine Kante oder Verbindung. Er wird sowohl bei ungerichteten als auch bei gerichteten Graphen verwendet. Arc bezeichnet häufig speziell eine gerichtete Kante, ist jedoch keine universell vorgeschriebene Bezeichnung.

Die fachlich präziseste Zusammenfassung lautet daher:

• Node und Vertex bedeuten Knoten.
• Edge bedeutet Kante oder Verbindung.
• Arc bedeutet meist gerichtete Kante.
• Die Richtung eines Graphen wird durch seine Verbindungen bestimmt, nicht durch die Bezeichnung seiner Knoten.

Hinweis: Alle Angaben wurden sorgfältig und nach bestem Wissen recherchiert. Für Richtigkeit, Vollständigkeit und Aktualität wird keine Gewähr übernommen. Termine, Preise, Leistungen, Teilnahmebedingungen, Öffnungszeiten, Verfügbarkeiten, gesetzliche Regelungen und sonstige Rahmenbedingungen können sich jederzeit kurzfristig ändern. Dieser Beitrag stellt keine individuelle Rechts-, Finanz-, Steuer-, Gesundheits- oder sonstige Fachberatung dar. Änderungen sind jederzeit möglich; maßgeblich sind die aktuellen Angaben des jeweiligen Anbieters oder Veranstalters. Eine Haftung wird ausgeschlossen.