Weg (Graphentheorie)

Ein Graph, der einen Weg mit den Knoten B, C, F sowie die Kantenfolge D,{D,E},E,{E,B},B,{B,A},A,{A,E},E,{E,F},F enthält

In der Graphentheorie wird eine Folge von Knoten, in welcher jeweils zwei aufeinanderfolgende Knoten durch eine Kante verbunden sind, als Weg (manchmal auch als Pfad) bezeichnet. Eine Folge von Kanten, in welcher jeweils zwei aufeinanderfolgende Kanten einen gemeinsamen Knoten haben, wird als Kantenzug (manchmal auch als Kantenfolge) bezeichnet.

Definitionen

Weg

Ein nichtleerer Graph $W$ mit der Knotenmenge $\{x_{1},x_{2},\dotsc ,x_{n}\}$ und der Kantenmenge $\{\{x_{1},x_{2}\},\{x_{2},x_{3}\},\dotsc ,\{x_{n-1},x_{n}\}\}$ mit $2\leq n$ heißt Weg, wenn die Knoten $x_{i}$ mit $1\leq i\leq n$ paarweise verschieden sind. Auch ein Graph mit einer Knotenmenge $\{x_{1}\}$ (d. h. mit einem Knoten) und einer leeren Kantenmenge wird meistens als Weg (der Länge 0) bezeichnet.

Oft wird, vor allem im Falle von schlichten Graphen, ein Weg der Einfachheit halber durch die Folge seiner benachbarten Knoten $x_{1},x_{2},\dotsc ,x_{n}$ angegeben. Hierbei gilt es, zu beachten, dass auch die gespiegelte Folge $x_{n},x_{n-1},\dotsc ,x_{1}$ diesen Weg darstellt. Nach dieser Definition besitzen Wege keine ausgezeichnete Richtung.

Die Knoten $x_{1}$ und $x_{n}$ nennt man die Endknoten des Weges, wobei $x_{1}$ als Anfangsknoten und $x_{n}$ als Endeknoten bezeichnet wird. Knoten, die keine Endknoten sind, nennt man auch innere Knoten. Durch die Anordnung der Knoten eines Weges in Form einer Folge können auch seine Kanten eindeutig als Folge $e_{1}=\{x_{1},x_{2}\},e_{2}=\{x_{2},x_{3}\},\dotsc ,e_{n-1}=\{x_{n-1},x_{n}\}$ angeordnet werden.

Im sprachlichen Gebrauch sagt man oft, ein Graph enthalte einen Weg oder eine Folge $x_{1},x_{2},\dotsc ,x_{n}$ von benachbarten Knoten eines Graphes sei ein Weg des Graphen. Das soll bedeuten, dass dieser Weg ein Teilgraph des Graphen ist.

Je nach Kontext kann man den Begriff Weg anpassen. Bei gerichteten Graphen müssen zum Beispiel alle aufeinanderfolgenden Knoten $x_{i}$ und $x_{i+1}$ durch eine gerichtete Kante $(x_{i},x_{i+1})$ verbunden sein, sodass der Weg auch eine Richtung angibt.

Der Begriff des Weges wird in der Literatur nicht einheitlich verwendet. Die angegebene Definition folgt im Wesentlichen den Büchern von Diestel und Lovász. Die Beschreibung eines Weges über die Folge der benachbarten Knoten erfolgt bei Aigner und Kőnig. Gelegentlich wird auch der Begriff Pfad für einen Weg verwendet (Steger), wohl deshalb, weil in der englischsprachigen Literatur Weg als path, teilweise aber auch als simple path bezeichnet wird.

Kantenzug

In einem (ungerichteten) Graphen nennt man eine Folge $x_{1},e_{1},x_{2},e_{2},\dotsc ,e_{n-1},x_{n}$, in der sich Knoten und Kanten des Graphen abwechseln und für die gilt, dass für $i=1,\dotsc ,n-1$ die Kante $e_{i}$ die Knoten $x_{i}$ und $x_{i+1}$ verbindet, einen Kantenzug des Graphen. Diese Definition ist sowohl für Multigraphen als auch für Hypergraphen anwendbar. Für einfache Graphen kann man dagegen fordern, dass die Kanten $e_{i}$ die Form $\{x_{i},x_{i+1}\}$ haben müssen. Im Allgemeinen können sich Kanten und Knoten innerhalb eines Kantenzuges wiederholen. Wie bei einem Weg nennt man die Knoten $x_{1}$ und $x_{n}$ die Endknoten des Kantenzuges, wobei $x_{1}$ als Anfangsknoten und $x_{n}$ als Endeknoten bezeichnet wird, und die Knoten, die keine Endknoten sind, innere Knoten.

Jeder Weg bildet auch einen Kantenzug, indem seine Knoten- und Kantenfolgen alternierend zusammengefügt werden. Umgekehrt impliziert ein Kantenzug von $x_{1}$ nach $x_{n}$ die Existenz eines Weges mit den Endknoten $x_{1}$ und $x_{n}$. Diesen Weg enthält man, indem Zyklen im Kantenzug sukzessive eliminiert werden. Für einen Kantenzug oder sogar Weg in einem Multigraphen bzw. Hypergraphen reicht es nicht aus, die Knoten des Kantenzuges/Weges anzugeben (es kann mehr als eine Kante zwischen zwei Knoten geben bzw. zwei Knoten können jeweils mit weiteren Knoten durch verschiedene Hyperkanten verbunden sein). In diesem Fall ist ein Weg auch nur durch den entsprechenden Kantenzug eindeutig festgelegt. Umgekehrt ist in jedem Multigraphen (jedoch nicht in jedem Hypergraphen!) ein Kantenzug bereits durch seine Kantenfolge $e_{1},e_{2},\dotsc ,e_{n-1}$ eindeutig definiert (zwei benachbarte Kanten haben genau einen gemeinsamen Knoten).

Auch der Begriff des Kantenzuges wird in der Fachliteratur nicht einheitlich verwendet. Die hier angegebene Definition orientiert sich an den Büchern von Diestel und Lovász u. a. Aigner und Kőnig sprechen in ihren Büchern hingegen von Kantenfolgen. Kőnig benutzt den Begriff Kantenzug, um deutlich zu machen, dass sich keine Kanten wiederholen (engl. trail). Mitunter wird auch der Begriff Weg für Kantenzug benutzt (Steger). Auch in der englischsprachigen Literatur wird der Begriff nicht einheitlich benutzt, er wird jedoch meistens mit walk bezeichnet, mitunter aber auch als path.

Bei Rudolf Halin wird für gerichtete Graphen eine Kantenfolge (im hiesigen Sinne), bei der kein Knoten und keine Kante mehr als einmal auftreten, auch als Kantenzug oder kürzer als Bahn bezeichnet. Horst Sachs dagegen nennt eine solche eine elementare Bahn.

Zyklus, Kreis, Eulerzug

→ Hauptartikel: Zyklus (Graphentheorie)

→ Hauptartikel: Eulerkreisproblem

Kantenzüge, bei denen die Endknoten identisch sind (d. h. der erste und der letzte Knoten übereinstimmen), heißen geschlossen. Einen geschlossenen Kantenzug, in dem keine Kante mehrfach vorkommt, nennt man Zyklus (eng. circuit). Wenn die Endknoten die einzigen mehrfach in der Knotenfolge des Kantenzuges enthaltenen Knoten sind, heißt dieser Kantenzug Kreis (engl. cycle). Einen Kreis erhält man auch, indem die Endknoten eines Weges durch eine zusätzliche Kante verbunden werden.

Ein besonderes Interesse gilt solchen geschlossenen Kantenzügen, in denen jede Kante des Graphen genau einmal auftritt. Einen solchen Kantenzug bzw. Zyklus nennt man nach Leonhard Euler eulersch oder einfach einen Eulerzug oder auch eine eulersche Linie. Die Existenz solcher wurde von Euler im Zusammenhang mit der Lösung des Königsberger Brückenproblems (1736) untersucht, welches als eines der Initialprobleme der Graphentheorie gilt.

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

Sind $A$ und $B$ Teilmengen von der Knotenmenge $V$ eines Graphen, so bezeichnet man einen Weg als $A$-$B$-Weg, falls einer seiner Endknoten in $A$ und der andere 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} gemeinsam haben.

Disjunkte Wege

Zwei Wege Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W_1 =v_1, \dotsc, v_k} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W_2 = u_1, \dotsc, u_l} in einem Graphen heißen kreuzungsfrei, knotendisjunkt oder einfach nur disjunkt, wenn es kein Paar Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (i, j)} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{ 2, \dotsc, k - 1 \}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{ 2, \dotsc, l - 1 \}} gibt, für das Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_i = u_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.

Eine Menge disjunkter Wege in einem Graphen mit der Eigenschaft, dass jeder Knoten des Graphen auf einem dieser Wege liegt, heißt Wegüberdeckung des Graphen.

Länge und Abstand

In Graphen ohne Gewichte auf den Kanten bezeichnet man mit der Länge eines Weges oder Kantenzuges die Anzahl seiner Kanten. In kantengewichteten Graphen bezeichnet man als Länge eines Weges die Summe der Kantengewichte aller zugehörigen Kanten. Die Länge des längsten Weges in einem Graphen nennt man Umfang des Graphen.

Als einen kürzesten Weg von einem Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} zu einem Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} in einem Graphen bezeichnet man einen Weg von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} , dessen Länge minimal ist. Die Länge eines kürzesten Weges nennt man dann Abstand oder Distanz von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} . Die Exzentrizität eines Knotens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} ist der maximale Abstand zu allen anderen Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} des Graphen. Der Rand eines Graphens ist die Menge der Knoten mit maximaler Exzentrizität. 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.

Den größten Abstand zwischen zwei Knoten in einem Graphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} nennt man den Durchmesser Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D(G)} des Graphen. Der Durchmesser ist damit das Maximum aller Exzentrizitäten der Knoten in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} . Der Radius Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R(G)} eines Graphen ist das Minimum der Exzentrizitäten seiner Knoten. Für alle Graphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R(G)\le D(G)\le 2 \cdot R(G)} .

Die Knoten, deren Exzentrizität dem Radius entsprechen, bilden das Zentrum des Graphen.

Distanzgraph

Der Distanzgraph zu einem Graphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V} , der jeder Kante als Kantengewicht den Abstand zwischen den beiden Knoten in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} zuordnet.

Literatur

• Reinhard Diestel: Graphentheorie. 3., neu bearbeitete und erweiterte Auflage. Springer Verlag, Berlin / Heidelberg / New York (und weitere) 2006, ISBN 978-3-540-21391-8. 
• Rudolf Halin: Graphentheorie I (= Erträge der Forschung. Band 138). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3 (MR0586234). 
• Dénes Kőnig: Theorie der endlichen und unendlichen Graphen. Mit einer Abhandlung von L. Euler. Hrsg.: H. Sachs (= Teubner-Archiv zur Mathematik. Band 6). BSB B. G. Teubner Verlagsgesellschaft, Leipzig 1986, ISBN 3-211-95830-4. 
• Horst Sachs: Einführung in die Theorie der endlichen Graphen. Carl Hanser Verlag, München 1971, ISBN 3-446-11463-7 (MR0345857). 
• Klaus Wagner: Graphentheorie (= BI-Hochschultaschenbücher. 248/248a). Bibliographisches Institut, Mannheim (u. a.) 1970, ISBN 3-411-00248-4 (MR0282850).