Wege, Pfade, Zyklen und Kreise in Graphen

Wege, Pfade, Zyklen und Kreise in Graphen

Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem Übersichtsartikel zusammen dargestellt.

Inhaltsverzeichnis

Definitionen

Gerichtete und ungerichtete Wege

Sei G = (V,E) ein (gerichteter) (Multi-)Graph und W = (v_1, \ldots, v_n) eine Folge von Knoten aus V mit der Eigenschaft, dass für alle i aus \{ 1, \ldots, n - 1 \} gilt:

Das heißt, vi und vi + 1 sind durch eine Kante verbunden. Dann bezeichnet man W als ungerichteten Weg in G, falls G ungerichtet ist, und als gerichteten Weg in G, falls G gerichtet ist. Eine andere Bezeichnung für Weg ist Kantenfolge (vgl. Kantenzug). Den Knoten v1 nennt man Startknoten von W und den Knoten vn Endknoten von W. Einen besonderen Weg stellt der Eulersche Weg dar.

Pfade, Zyklen und Kreise

Einen Weg W bezeichnet man als

  • Pfad, falls alle Knoten in der Folge W voneinander verschieden sind, das heißt falls für alle i und j aus \{ 1, \ldots, n \} gilt, dass v_i \ne v_j, falls i \ne j.
  • Zyklus, falls Start- und Endknoten von W identisch sind, das heißt falls v1 = vn.
  • Kreis, falls nur Start- und Endknoten von W identisch sind, das heißt falls v1 = vn und v_1, \ldots, v_{n - 1} einen Pfad bilden, also für alle i und j aus \{ 1, \ldots, n - 1 \} gilt, dass v_i \ne v_j, falls i \ne j.

Bemerkung: Jeder Kreis, Zyklus oder Pfad in einem Graphen G ist also auch ein Weg und jeder Kreis ist auch ein Zyklus in G. Wege, Pfade, Zyklen und Kreise definiert man alternativ auch über Kantenzüge oder Teilgraphen. Gibt es einen Weg von Knoten u zu Knoten v in G, so heißt v von u aus erreichbar (Erreichbarkeitsproblem in Graphen).

In ungerichteten Wegen und Pfaden bezeichnet man den Startknoten meist ebenfalls als Endknoten. In Zyklen und Kreisen verwendet man die Bezeichnungen Startknoten und Endknoten meist nicht.

Graphen mit Zyklen heißen zyklisch. Graphen ohne Zyklen heißen azyklisch. Ein Zyklus oder Kreis heißt trivial, wenn er weniger als drei Knoten enthält. Triviale Kreise oder Zyklen werden meist nicht betrachtet. Ein Kreis, der genau drei Knoten enthält nennt man oft Dreieck. Einen Graphen ohne Dreieck nennt man dann dreiecksfrei.

A-B-Weg, v-w-Weg, a-B-Fächer

Sind A und B Teilmengen von V, so bezeichnet man einen Weg als A-B-Weg, falls der Startknoten in A und der Endknoten in B liegt. Statt von einem {v}-{w}-Weg spricht man auch von einem v-w-Weg. Eine Menge von a-B-Wegen nennt man einen a-B-Fächer, wenn die Wege paarweise nur den Knoten a gemeinsam haben.

Kreuzungsfrei, knotendisjunkt, kantendisjunkt

Zwei Wege W_1 = (v_{1, 1}, \ldots , v_{1, k}) und W_2 = (v_{2, 1}, \ldots, v_{2, l}) heißen kreuzungsfrei, knotendisjunkt oder einfach nur disjunkt, wenn es kein Paar (i,j) mit i aus \{ 2, \ldots, k - 1 \} und j aus \{ 2, \ldots, l - 1 \} gibt, für das v1,i = v2,j ist, sie also keine inneren Knoten gemeinsam haben. Eine Menge von Wegen nennt man kreuzungsfrei, knotendisjunkt oder disjunkt, wenn die Wege paarweise disjunkt sind.

Länge eines Weges (Zyklus, Kreises), Abstand

In Graphen ohne Gewichte auf den Kanten bezeichnet man mit n − 1 die Länge eines Weges (oder Pfades) und mit n die Länge eines Zyklus (oder Kreises) (v_1, \ldots, v_n). Anschaulich zählt man also die Anzahl zugehöriger Kanten.

In kantengewichteten Graphen bezeichnet man als Länge eines Weges die Summe der Kantengewichte aller zugehörigen Kanten.

Als einen kürzesten Weg von einem Knoten s zu einem Knoten t in einem Graphen bezeichnet man einen Weg von s nach t, dessen Länge minimal ist. Die Länge eines kürzesten Weges nennt man dann Abstand oder Distanz von s nach t. Falls kein Weg zwischen zwei Knoten existiert, so setzt man den Abstand auf unendlich.

Man beachte, dass in gerichteten Graphen der Abstand von der Richtung des Weges abhängt. Insbesondere kann es sein, dass nur in eine Richtung ein gerichteter Weg existiert.

Durchmesser und Taillenweite

Den größten Abstand zwischen zwei Knoten in einem Graphen G nennt man Durchmesser von G. Als Taillenweite eines Graphen bezeichnet man die Länge eines kürzesten nicht trivialen Kreises. Falls der Graph keinen Kreis besitzt, so setzt man die Taillenweite auf unendlich.

Distanzgraph

Der Distanzgraph zu einem Graphen G = (V,E) bezeichnet den vollständigen (das heißt je zwei Knoten sind durch eine Kante verbunden, ggf. in gerichteten Graphen in beide Richtungen, wobei es aber keine Schleifen gibt) kantengewichteten Graphen auf der Knotenmenge V, der jeder Kante als Kantengewicht den Abstand zwischen den beiden Knoten in G zuordnet.

Siehe auch

Literatur


Wikimedia Foundation.

См. также в других словарях:

  • Typen von Graphen in der Graphentheorie — Ein Graph besteht in der Graphentheorie anschaulich aus einer Menge von Punkten, zwischen denen Linien verlaufen. Die Punkte nennt man Knoten oder Ecken, die Linien nennt man meist Kanten, manchmal auch Bögen. Auf die Form der Knoten und Kanten… …   Deutsch Wikipedia

  • Färbung von Graphen — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Paarungen in Graphen — Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Algorithmus von Jarnik, Prim und Dijkstra — Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen. Der Algorithmus wurde 1930 von dem tschechischen Mathematiker Vojtěch Jarník entwickelt. 1957 wurde er …   Deutsch Wikipedia

  • Bipartite Graphen — bipartiter Graph allgemeiner: perfekter Graph k partiter Graph Beispiele: Vollständig bipartite Graphen Bäume …   Deutsch Wikipedia

  • Chordale Graphen — triangulierter Graph allgemeiner: perfekter Graph Schnittgraph Beispiele: Intervallgraphen Bäume Dreiecksgraphen In der Graphentheorie nennt man einen Graphen G trianguliert oder chordal, wenn er ei …   Deutsch Wikipedia

  • Triangulierte Graphen — triangulierter Graph allgemeiner: perfekter Graph Schnittgraph Beispiele: Intervallgraphen Bäume Dreiecksgraphen In der Graphentheorie nennt man einen Graphen G trianguliert oder chordal, wenn er ei …   Deutsch Wikipedia

  • Disjunkte Wege — Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem… …   Deutsch Wikipedia

  • Kantendisjunkte Wege — Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem… …   Deutsch Wikipedia

  • Knotendisjunkte Wege — Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem… …   Deutsch Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»