imported>Docosanus: + Link zu A. Steger

2025-09-29T10:07:37Z

+ Link zu A. Steger

Neue Seite

[[Datei:Path and walk.svg|mini|hochkant=1.2|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 (Mathematik)|Folge]] von [[Knoten (Graphentheorie)|Knoten]], in welcher jeweils zwei aufeinanderfolgende Knoten durch eine [[Kante (Graphentheorie)|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 (Graphentheorie)|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> mit <math>2 \leq n</math> heißt ''Weg'', wenn die Knoten <math>x_i</math> mit <math>1 \leq i \leq n</math> paarweise verschieden sind. Auch ein Graph mit einer Knotenmenge <math>\{x_1\}</math> (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 [[Schlichter Graph|schlichten Graphen]], ein Weg der Einfachheit halber durch die Folge seiner [[Nachbarschaft (Graphentheorie)#Definition|benachbarten]] 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 darstellt. 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, wobei <math>x_1</math> als ''Anfangsknoten'' und <math>x_n</math> 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 <math>e_1=\{x_1,x_2\},e_2=\{x_2,x_3\},\dotsc,e_{n-1}=\{x_{n-1},x_n\}</math> angeordnet werden.

Im sprachlichen Gebrauch sagt man oft, ein Graph enthalte einen Weg oder eine Folge <math>x_1,x_2,\dotsc, x_n</math> 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 [[Gerichteter Graph|gerichteten Graphen]] müssen zum Beispiel alle aufeinanderfolgenden Knoten <math>x_i</math> und <math>x_{i+1}</math> durch eine gerichtete Kante <math>(x_i,x_{i+1})</math> 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 [[Reinhard Diestel|Diestel]]<ref name="diestel">{{Cite book
| edition = 3., neu bearb. und erw
| publisher = Springer, Berlin
| isbn = 3-540-21391-0
| last = Diestel
| first = Reinhard
| title = Graphentheorie
| date = 2006
| url = http://diestel-graph-theory.com/german/index.html
| pages= 7ff |language=de
}}</ref> und [[László Lovász|Lovász]]<ref name="lovasz">{{Cite book
| publisher = Springer, Berlin
| isbn = 0-387-95584-4
| last1 = Lovász
| first1 = László
| last2 = Pelikán
| first2= Jósef
| last3= Vesztergombi
| first3= Katalin
| title = Diskrete Mathematik
| pages = 163ff
| date = 2003 |language=de
}}</ref>.
Die Beschreibung eines Weges über die Folge der benachbarten Knoten erfolgt bei [[Martin Aigner|Aigner]]<ref name="aigner">{{Cite book
| edition = 6., korr
| publisher = Vieweg
| title = Diskrete Mathematik
| isbn = 3-8348-0084-8
| last = Aigner
| first = Martin
| date = 2006 |language=de
}}</ref> und [[Dénes Kőnig|Kőnig]]<ref name="könig">{{cite book|first=Dénes |last=Kőnig |title=Theorie der endlichen und unendlichen Graphen |publisher=Akademische Verlagsgesellschaft |location=Leipzig |year=1936 }}</ref>.
Gelegentlich wird auch der Begriff '''Pfad''' für einen Weg verwendet ([[Angelika Steger|Steger]])<ref name="steger">{{Cite book
| edition = 2
| publisher = Springer, Berlin
| isbn = 978-3-540-46660-4
| last1 = Steger
| first1 = Angelika
| title = Diskrete Strukturen
| volume = 1: Kombinatorik, Graphentheorie, Algebra
| pages = 61
| date = 2007 |language=en
}}</ref>, 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 <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 Knoten <math>x_{i}</math> und <math>x_{i+1}</math> verbindet, einen ''Kantenzug'' des Graphen. Diese Definition ist sowohl für [[Graph (Graphentheorie)#Multigraph|Multigraphen]] als auch für [[Graph (Graphentheorie)#Hypergraph|Hypergraphen]] anwendbar. Für einfache Graphen kann man dagegen fordern, dass die Kanten <math>e_i</math> die Form <math>\{x_{i},x_{i+1}\}</math> haben müssen. Im Allgemeinen können sich Kanten und Knoten innerhalb eines Kantenzuges wiederholen. Wie bei einem Weg nennt man die Knoten <math>x_1</math> und <math>x_n</math> die ''Endknoten'' des Kantenzuges, wobei <math>x_1</math> als ''Anfangsknoten'' und <math>x_n</math> 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 <math>x_1</math> nach <math>x_n</math> die Existenz eines Weges mit den Endknoten <math>x_1</math> und <math>x_n</math>. 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 <math>e_1, e_2, \dotsc, e_{n-1}</math> 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.<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 (engl. ''trail'').<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 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.<ref name="RH-Ib">Rudolf Halin: ''Graphentheorie I.'' 1980, S. 19</ref> [[Horst Sachs]] dagegen nennt eine solche eine ''elementare Bahn''.<ref name="HS-I">Horst Sachs: ''Einführung in die Theorie der endlichen Graphen.'' 1971, S. 118–121</ref>

=== 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 (Graphentheorie)|Zyklus]]''' (eng. ''circuit''). Wenn die Endknoten die einzigen mehrfach in der Knotenfolge des Kantenzuges enthaltenen Knoten sind, heißt dieser Kantenzug '''[[Zyklus (Graphentheorie)|Kreis]]''' (engl. ''cycle''). Einen Kreis erhält man auch, indem die Endknoten eines Weges durch eine zusätzliche Kante verbunden werden.<ref name="diestel" />

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 '''[[Eulerkreisproblem|Eulerzug]]''' oder auch eine ''eulersche Linie''. Die Existenz solcher wurde von Euler im Zusammenhang mit der Lösung des [[Königsberger Brückenproblem]]s (1736) untersucht, welches als eines der Initialprobleme der Graphentheorie gilt.<ref name="könig-1">Kőnig, op. cit., S. 35</ref><ref name="RH-Ia">Rudolf Halin: ''Graphentheorie I.'' 1980, S. 18</ref>

=== ''A''-''B''-Weg, ''v''-''w''-Weg, ''a''-''B''-Fächer ===
Sind <math>A</math> und <math>B</math> [[Teilmenge]]n 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 [[Kantengewichteter Graph|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ürzester Weg|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ändiger Graph|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 ==
* {{Literatur
|Autor=[[Reinhard Diestel]]
|Titel=Graphentheorie
|Auflage=3., neu bearbeitete und erweiterte
|Verlag=Springer Verlag
|Ort=Berlin / Heidelberg / New York (und weitere)
|Datum=2006
|ISBN=978-3-540-21391-8}}
* {{Literatur
|Autor=Rudolf Halin
|Titel=Graphentheorie I
|Reihe=Erträge der Forschung
|BandReihe=138
|Verlag=Wissenschaftliche Buchgesellschaft
|Ort=Darmstadt
|Datum=1980
|ISBN=3-534-06767-3
|Online=[http://ams.math.uni-bielefeld.de/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&r=1&review_format=html&s4=Halin&s5=I&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq MR0586234]}}
* {{Literatur
|Autor=[[Dénes Kőnig]]
|Hrsg=[[Horst Sachs|H. Sachs]]
|Titel=Theorie der endlichen und unendlichen Graphen
|TitelErg=Mit einer Abhandlung von L. Euler
|Reihe=Teubner-Archiv zur Mathematik
|BandReihe=6
|Verlag=BSB B. G. Teubner Verlagsgesellschaft
|Ort=Leipzig
|Datum=1986
|ISBN=3-211-95830-4}}
* {{Literatur
|Autor=Horst Sachs
|Titel=Einführung in die Theorie der endlichen Graphen
|Verlag=Carl Hanser Verlag
|Ort=München
|Datum=1971
|ISBN=3-446-11463-7
|Online=[http://ams.math.uni-bielefeld.de/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Sachs&s5=Einf%C3%BChrung&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=2&mx-pid=345857 MR0345857]}}
* {{Literatur
|Autor=[[Klaus Wagner (Mathematiker)|Klaus Wagner]]
|Titel=Graphentheorie
|Reihe=BI-Hochschultaschenbücher
|BandReihe=248/248a
|Verlag=Bibliographisches Institut
|Ort=Mannheim (u. a.)
|Datum=1970
|ISBN=3-411-00248-4
|Online=[http://ams.math.uni-bielefeld.de/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Wagner&s5=Graphentheorie&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=4&mx-pid=282850 MR0282850]}}

== Einzelnachweise ==
<references />

[[Kategorie:Grundbegriff (Graphentheorie)]]

Weg (Graphentheorie) - Versionsgeschichte

imported>Docosanus: + Link zu A. Steger