Weg (Graphentheorie)

In der Graphentheorie bezeichnet Weg, Pfad, Kantenzug oder Kantenfolge eine Folge von Knoten, in welcher jeweils zwei aufeinander folgende Knoten durch eine Kante verbunden sind.

Definitionen

Weg

Ein nicht-leerer Graph <math>W</math>, mit der Knotenmenge <math>\{x_1,x_2,\dotsc , x_n\}</math> und der Kantenmenge <math>\{\{x_1,x_2\},\{x_2,x_3\},\dotsc,\{x_{n-1},x_n\}\}</math>, heißt Weg, wenn die Knoten <math>x_i</math> paarweise verschieden sind. Oft wird ein Weg der Einfachheit halber durch die Folge seiner Knoten <math>x_1,x_2,\dotsc, x_n</math> angegeben. Hierbei gilt es, zu beachten, dass auch die gespiegelte Folge <math>x_n,x_{n-1},\dotsc, x_1</math> diesen Weg benennt. Nach dieser Definition besitzen Wege keine ausgezeichnete Richtung. Die Knoten <math>x_1</math> und <math>x_n</math> nennt man die Endknoten des Weges. Knoten, die keine Endknoten sind, nennt man auch innere Knoten.

Im sprachlichen Gebrauch wird oft der Ausdruck verwendet, ein Graph enthält einen Weg <math>W</math>. Damit bezieht man sich darauf, dass der Weg <math>W</math> ein Teilgraph des Graphen ist. Je nach Kontext kann man den Begriff Weg anpassen, zum Beispiel für gerichtete Graphen. Hier müssen alle aufeinander folgenden Knoten <math>x_i</math> und <math>x_{i+1}</math> durch eine gerichtete Kante <math>(x_i,x_{i+1})</math> verbunden sein. In diesem Falle gibt ein Weg immer auch eine Richtung an.

Der Begriff des Weges wird in der Literatur nicht einheitlich verwendet. Die angegebene Definition folgt den Büchern von Diestel und Lovász u. a.<ref name="diestel"> Reinhard Diestel: <cite>Graphentheorie.</cite>, 3., neu bearb. und erw. Ausgabe, Springer, Berlin, 2006, ISBN 3-540-21391-0, S. 7ff.</ref><ref name="lovasz">László Lovász, Jósef Pelikán, Katalin Vesztergombi Diskrete Mathematik. Springer, Berlin, 2003, ISBN 0-387-95584-4, S. 163ff.</ref> Mitunter wird ein Weg auch direkt über die Folge von inzidenten paarweise-verschiedenen Knoten angegeben (siehe Aigner und Kőnig).<ref name="aigner">Martin Aigner: Diskrete Mathematik, 6., korrigierte Auflage, Vieweg, 2006, ISBN 3-8348-0084-8.</ref> <ref name="könig"> Dénes Kőnig: Theorie der endlichen und unendlichen Graphen. Akademische Verlagsgesellschaft, Leipzig 1936. </ref> In diesem Fall besitzt der Weg eine implizierte Richtung von <math>x_1</math> nach <math>x_n</math>. Gelegentlich wird auch der Begriff Pfad für einen Weg verwendet (Steger)<ref name="steger"> Angelika Steger Diskrete Strukturen, 2. Auflage, Band 1: Kombinatorik, Graphentheorie, Algebra, Springer, Berlin, 2007, ISBN 978-3-540-46660-4, S. 61. </ref>, wohl deshalb, weil in der englischsprachigen Literatur Weg als path, teilweise aber auch als simple path bezeichnet wird.

Ein Weg, bei dem der Start- mit dem Endknoten identisch ist, und dies der einzige wiederholte Knoten in der Knotenfolge ist, heißt Zyklus oder Kreis.

Kantenzug und Kantenfolge

In einem Graphen nennt man eine Folge <math>x_1,e_1,x_2,e_2,\dotsc,e_{n-1},x_n</math>, in der sich Knoten und Kanten des Graphen abwechseln und für die gilt, dass für <math>i=1,\dotsc, n-1</math> die Kante <math>e_i</math> die Form <math>\{x_{i},x_{i+1}\}</math> hat, einen Kantenzug des Graphen. Im Gegensatz zu Wegen besitzen Kantenzüge eine implizierte Orientierung von <math>x_1</math> zu <math>x_n</math>. Des Weiteren können sich Kanten und Knoten innerhalb eines Kantenzuges wiederholen. Ein Kantenzug von <math>x_1</math> nach <math>x_n</math> impliziert die Existenz eines Pfades mit den Endknoten <math>x_1</math> und <math>x_n</math>. Kantenzüge bei denen der erste und der letzte Knoten übereinstimmen heißen geschlossen.

Ein besonderes Interesse gilt geschlossenen Kantenzügen, in welchen alle Kanten genau einmal enthalten sind. Solche Kantenzüge nennt man eulersch (manchmal auch Eulerzug), ihre Existenz wurde bereits von Leonhard Euler im Zusammenhang mit dem Königsberger Brückenproblem untersucht, welches als eines der ersten Probleme auf dem Gebiet der Graphentheorie gilt.

Auch der Begriff Kantenzug wird in der Literatur nicht einheitlich verwendet. Die hier angegebene Definition orientiert sich an den Büchern von Diestel und Lovász u.a.<ref name="diestel"/><ref name="lovasz"/> Aigner und Kőnig sprechen in ihren Büchern hingegen von Kantenfolgen.<ref name="aigner"/><ref name="könig"/> Kőnig benutzt den Begriff Kantenzug, um deutlich zu machen, dass sich keine Kanten wiederholen.<ref name="könig"/> Mitunter wird auch der Begriff Weg für Kantenzug benutzt (Steger).<ref name="steger"/> Auch in der englischsprachigen Literatur wird der Begriff nicht einheitlich benutzt, er wird gelegentlich mit walk bezeichnet, mitunter aber auch als path bezeichnet.

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

Sind <math>A</math> und <math>B</math> Teilmengen von der Knotenmenge <math>V</math> eines Graphen, so bezeichnet man einen Weg als <math>A</math>-<math>B</math>-Weg, falls einer seiner Endknoten in <math>A</math> und der andere in <math>B</math> liegt. Statt von einem <math>\{v\}</math>-<math>\{w\}</math>-Weg spricht man auch von einem <math>v</math>-<math>w</math>-Weg. Eine Menge von <math>a</math>-<math>B</math>-Wegen nennt man einen <math>a</math>-<math>B</math>-Fächer, wenn die Wege paarweise nur den Knoten <math>a</math> gemeinsam haben.

Disjunkte Wege

Zwei Wege <math>W_1 =v_1, \dotsc, v_k</math> und <math>W_2 = u_1, \dotsc, u_l</math> in einem Graphen heißen kreuzungsfrei, knotendisjunkt oder einfach nur disjunkt, wenn es kein Paar <math>(i, j)</math> mit <math>i</math> aus <math>\{ 2, \dotsc, k - 1 \}</math> und <math>j</math> aus <math>\{ 2, \dotsc, l - 1 \}</math> gibt, für das <math>v_i = u_j</math> 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 <math>s</math> zu einem Knoten <math>t</math> in einem Graphen bezeichnet man einen Weg von <math>s</math> nach <math>t</math>, dessen Länge minimal ist. Die Länge eines kürzesten Weges nennt man dann Abstand oder Distanz von <math>s</math> nach <math>t</math>. Die Exzentrizität eines Knotens <math>s</math> ist der maximale Abstand zu allen anderen Knoten <math>t</math> 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 <math>G</math> nennt man den Durchmesser <math>D(G)</math> des Graphen. Der Durchmesser ist damit das Maximum aller Exzentrizitäten der Knoten in <math>G</math>. Der Radius <math>R(G)</math> eines Graphen ist das Minimum der Exzentrizitäten seiner Knoten. Für alle Graphen <math>G</math> gilt

<math>R(G)\le D(G)\le 2 \cdot R(G)</math>.

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

Distanzgraph

Der Distanzgraph zu einem Graphen <math>G = (V, E)</math> 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 <math>V</math>, der jeder Kante als Kantengewicht den Abstand zwischen den beiden Knoten in <math>G</math> zuordnet.

Literatur

• R. Diestel: Graphentheorie. 3. Auflage. Springer, Heidelberg 2005. ISBN 3-540-67656-2

Einzelnachweise

<references />