Diskussion:Weg (Graphentheorie)

Begrifflichkeiten

Ich wollte hier mal Anregen, wenn es schon Differenzen was die Begriffe wie Pfad, Weg, etc gibt, diese Vielleicht gegenüber stellen je nach Quelle aus der sie Stammen zu ordnen. Oder sich auf eine Quelle zu einigen. Ich kenne z.B. die Notation von Diestel. Allerdings bezieht er sich ja auf ungerichtete Graphen, die keine mutigraphen sind. Wobei er eigentlich auch nur den Weg und den Kantenzug einführt. Der Begriff Pfad wird von ihm nicht verwendet. Hingegen wird der Begriff Pfad so weit ich weiß (zumindest in der Algorithmischen Geometrie) nur für gerichtete Graphen verwendet. Vielleicht sollten wir hier einmal Sammeln:

Begriff	Diestel (2010), ungerichtet, non multi
Weg	Nicht leerer Graph $P=(V,E)$ mit $V=\{x_{0},x_{1},\ldots ,x_{k}\}$ $\;E=\{x_{0}x_{1},\ldots ,x_{k-1}x_{k}\}$ wobei Ecken paarweise verschieden.
Kreis	Ist $P=(V,E)$ (mit $V$ und $E$ wie unter Weg definiert), so ist $P(V,E\cup x_{k}x_{0})$ ein Kreis
Kantenzug	Folge $v_{0}e_{0}v_{1}e_{1}\ldots e_{k-1}v_{k}$, mit $e_{i}=\{v_{i},v_{i+1}\}$. Ist $v_{0}=v_{1}$ so ist der Kantenzug geschlossen. Insbesondere ist also ein Kantenzug in den alle Ecken paarweise verschieden sind ein Weg.

--Landarzar 14:32, 22. Feb. 2012 (CET)

Habe mal das "Nicht leerer Graph P..." ergänzt.

Und finde die Idee gut, die Sachen nach Quellen hier erst einmal ordentlich gegenüberzustellen (um dann evtl. später nicht nachweisbare, andere Definitionen zu löschen). --Tddt (Diskussion) 05:25, 6. Jun. 2012 (CEST)

[zu speziell und komplex]

[Überschrift nachgetragen Lückenlos^wecken! 20:03, 12. Jul. 2009 (CEST)]

Ich halte es nicht für sinnvoll, so spezielle und so komplizierte Beispiele anzugeben. Naja, ich bin ja selbst schuld, aber ich hab leider keine Zeit die jetzt selbst zu machen... ---Coma 10:46, 13. Mär 2003 (CET)

---

[Plural von Zykel]

[Überschrift nachgetragen Lückenlos^wecken! 20:03, 12. Jul. 2009 (CEST)]

Ist Zykel eine Fachbegriff? Normalerweise ist der Singular von Zyklen Zyklus, oder? -- fristu

In meinem Skript steht Zykel. Eventuell ist das falsch aus dem englischen übersetzt? Ich überlege auch grad, ob es Zyklus oder Zykel heißt und vor allem wie die Mehrzahl gebildet wird. Wir könnten uns auch auf Zyklus einigen, dass steht wenigstens im Duden und bezeichnet auch das richtige... Vermutlich muß sowieso einiges verschoben werden... --Coma

In einem anderen Skript (vom selben Lehrstuhl) steht auch "Zykel" mit der Mehrzahlbilung "Zykel", im Akkusativ Plural wird "Zykeln" verwendet. Das Buch von Distel verwendet Zyklus, meint aber etwas anderes. Werd mal noch etwas weiter nachforschen. --Coma

Ich hab jetzt trotzdem Zykel in Zyklus geändert. --Coma

Voriges spielte sich von November 2002 bis März 2003 ab -- Lückenlos^wecken! 15:32, 13. Jul. 2009 (CEST)

Im Pfad sind alle Knoten verschieden voneinander?

Laut dem Skript meines Professors besitzt ein Pfad die Eigenschaft, dass Knoten auch mehrfach vorkommen können.

Das nennt man dan Weg! Aber manchmal wird da nicht so genau unterschieden. --Coma 19:36, 13. Nov 2004 (CET)

Das kommt sogar sehr oft durcheinander. Offenbar konnten die Gelehrten sich da nicht einigen :-) Stern !? 00:47, 4. Feb 2005 (CET)

Naja... so einfach ist es nicht. Es gibt viele Fälle, wo eine Unterscheidung nicht notwendig ist, und dann spricht man lieber vom Pfad als vom Weg, auch wenn es formal ein Weg sein kann. Für diese Anwendungen definiert man dann Pfad so wie Weg hier. Formal korrekt und auf der sicheren Seite sind wir mit der Darstellung hier. --Coma 08:51, 4. Feb 2005 (CET)

Ich habe gerade je einen Blick in Diestels "Graphentheorie", Königs "Theorie der endlichen und unendlichen Graphen" und Aigners "Diskrete Mathematik" geworfen. Die drei (oder zumindest die ersten beiden) dürften im deutschsprachigen Raum die Standardwerke zur Graphentheorie sein. Bei allen dreien dürfen in einem Weg Knoten nicht mehrfach vorkommen (entspr. engl "path"). Wenn Knoten mehrfach vorkommen dürfen wird dort von einem Kantenzug (entspr engl. "walk") gesprochen (wobei König beim Kantenzug verlangt, daß die Kanten verschieden sind und sonst von einer Kantenfolge spricht). Daher wäre ich dafür, hier in der Wikipedia, den in diesen deutschen Standardwerken einheitlich verwendeten Begriff Weg (in dem keine Knoten mehrfach vorkommen dürfen) zu übernehmen. SPTH 17:47, 10. Dez. 2009 (CET)

Hmm, so steht's hier auch in meinem Diestel (4. Auflage). Also genau das Gegenteil von Comas Behauptung, dass Knoten mehrfach in einem Weg erlaubt seien. @Coma, gibt's eine Quelle für deine umgekehrte Definition? In welcher Literatur wird generell ein Pfad (und wie) definiert? --Tddt (Diskussion) 05:08, 6. Jun. 2012 (CEST)

Abstand/Distanz

Also die Änderungen vom 3. Februar verstehe ich nicht so ganz. Es ist doch der Abstandsbegriff der in dem modifizierten Absatz beschrieben werden soll. So wie sich der Absatz nun liest, könnte man meinen, es soll der Begriff "Länge eines kürzesten Weges" beschrieben werden. Die Beschreibung "minimale Länge eines Weges zwischen zwei Knoten" verstehe ich ebenfalls nicht. Wenn ich einen bestimmten Weg zwischen zwei Knoten habe, wieviel Längen hat der denn? Ich finde die Version vom 10. Januar verständlicher. Andere Meinungen? Sledge 23:25, 3. Feb 2005 (CET)

Wenn ich einen bestimmten Weg zwischen zwei Knoten habe, wieviel Längen hat der denn? Eine, wenn man aber versch. Wege zwischen zwei knoten hat, sind die Längen verschieden. Deshalb ist die Länge eines kürzesten Weges die minimale Länge aller Wege zwischen zwei Knoten. Ich hab kürzester Weg als erstes definiert weil man die Wendung viel häufiger braucht als Abstand, bspw. wenn es um das Problem an sich geht. --Bolliver 00:44, 4. Feb 2005 (CET)

Sorry, ich hab das jetzt mal rückgängig gemacht. Ich hab mir damals viele Gedanken gemacht in welcher Reihenfolge ich was definiere, damit das wenigstens Formal korrekt bleibt. Ein paar zusammengehörige Sachen wie Durschschnitt und Tailenweite hast du mit deiner Umstellung auseinander gerissen. --Coma 08:48, 4. Feb 2005 (CET)

Letzteres stimmt, es ist aber wiederum kürzester Weg nicht definiert, was ich problematisch finde. Da das Problem des kürzesten Weges als erstes kommt und man eher darüber stösst (in der Literatur), danach kann man daruf aufbauend Abstand etc. vereinbaren. So bist du momentan inkonsistent, da kurz keine Graphendef. ist. In anbetracht der ganzen dafür vorgesehenen Algorithmen ist vielleciht sogar ein eigener Artikel drüber angebracht.

--Bolliver 11:50, 4. Feb 2005 (CET)

Puh, da hast du sogar recht gehabt. Ist es jetzt besser? --Coma 14:28, 4. Feb 2005 (CET)

..einen Weg, dessen Länge minimal ist. ist noch unglücklich formuliert, da das ein trivialer Weg sein könnte. sonst mM nach ok.--Bolliver 14:53, 4. Feb 2005 (CET)

Was ist ein trivialer Weg? --Coma 15:14, 4. Feb 2005 (CET)

Ich machs an einem Bsp deutlich: Du hast einen Graphen mit 2 Knoten s und t und die kanten s-s mit gewicht 0 und s-t mit gewicht 1. Als einen kürzesten Weg zwischen zwei Knoten in einem Graphen bezeichnet man einen Weg, dessen Länge minimal ist. demnach wäre s-s der kürzeste weg zwischen s und t!??--Bolliver 15:26, 4. Feb 2005 (CET)

Naja, da muss man schon viel willen mitbringen, um die Definition falsch zu verstehen. Aber ich hab es trotzdem jetzt noch exakter gemacht. Ich hoffe du bist jetzt zu frieden! :-) --Coma 19:47, 4. Feb 2005 (CET)

Vielen Dank euch Beiden, dass ihr euch der Definition nochmal angenommen habt. Ich denke sie ist nun ganz gut gelungen. Sledge 20:42, 4. Feb 2005 (CET)

So langsam bekomme ich Angst. Es gibt wirklich Leute die sich das ernsthaft durchlesen und versuchen zu verstehen? Dann kann es mit der Bildung in Dt. ja doch nicht so schlecht bestellt sein. --Coma 01:13, 5. Feb 2005 (CET)

definition zyklus

hat jemand eine mathematisch praezise definition fuer einen zyklus zur hand? (nicht signierter Beitrag von 130.83.244.129 (Diskussion) 16:06, 27. Sep. 2005 (CEST))

Laut meines skriptes (das niemals perfekt ist) ist ein Zyklus ein "Geschlossener Weg, bei dem jeder Knoten, der in einem bogen des Weges an erster Stelle enthalten ist, in genau einem anderen Bogen an zweiter Stelle enthalten ist, und umgekehrt" Wobei ein Geschlossener Weg laut dem Skript ein "Weg mit b = a", also ein Weg mit dem selben knoten als startpunkt und endpunkt... Aber verlass dich nicht drauf, das widerspricht dem was auf der seite steht.195.37.0.7 18:24, 18. Jan 2006 (CET)

Ist sich irgendwer wirklich sicher über die definition? (nicht signierter Beitrag von 195.37.0.7 (Diskussion) 19:24, 18. Jan. 2006 (CET))

das sind alles keine Definitionen der Graphentheorie

Ich möchte anmerken, dass der bisherige Text nicht mit dem übereinstimmt, was in sämtlichen Büchern der Graphentheorie definiert wird. Wege, Pfade, Kreise, Graphen sind aber nun mal in der Graphentheorie angesiedelt! Ich empfehle "Eigner, Graphentheorie" zur Einführung. Eine meiner Studentinnen ist darauf prompt reingefallen.

Ein Weg ist ein ein zusammenhängender Graph, in dem die Knoten maximalen Grad 2 haben. Oder angeordnet werden können. Oder wie auch immer man das formal hinschreibt. Aber das ist die Definition in jedem Graphentheorie-Buch oder Paper.

Man kann darüber Wege in Graphen definieren. Dann ist eine Folge von Punkten ein Weg, wenn der induzierte Teilgraph ein Weg ist. Das heißt aber insbesondere, dass alle Punkte verschieden sein müssen.

Einige algorithmische Graphentheoretiker sprechen von einfachen Wegen (das sind die oben beschriebenen) und Wegen, die dürfen dann Überschneidungen haben. Oder man nennt das andere Kantenzüge.

Auf gar keinen Fall sollte aber "walk" mit "Weg" übersetzt werden (walk ist die englische Entsprechung von Kantenzug), es heißt nämlich maximal "Spaziergang"! Ein "path" (ein einfacher Weg) heißt leider auf Deutsch sowohl "Weg" als auch "Pfad", dadurch ist es wohl irgendwann zu dieser Verwechslung gekommen... (nicht signierter Beitrag von 129.70.160.23 (Diskussion) 15:30, 28. Okt. 2005 (CEST))

Es gibt viele Möglichkeiten die Begriffe zu definieren, die inhaltlich aber alle das selbe Bezeichnen. Leider sind auch die Bezeichnungen uneinheitlich. Bisher hat jedes Buch, das ich gelesen habe leicht unterschiedliche Definitionen. IMHO macht es keinen Sinn sich darüber zu streiten, wie etwas definiert werden sollte, es muss nur innerhalb der Wikipedia konsitent sein. --Coma 19:09, 28. Okt 2005 (CEST)

Für mich ist ein Weg eine injektive Knotenfolge, wobei benachbarte Knoten durch Kanten verbunden sind. Das nennt sich hier bei Wiki offenbar "Pfad". Aber auch nicht einheitlich. Frage: Darf bei einem Wikipedia-Weg eine Kante mehrfach durchlaufen werden? Und was bedeutet die Notation E({v_i,v_{i+1}})? --Zaph 15:59, 20. Dez. 2008 (CET)

Das alles sind tatsächlich keine korrekten und üblichen Definitionen! Deshalb ist wohl auch keine einzige Quelle angegeben... Auch ist der Artikel ein ziemliches Sammelsurium verschiedener Dinge. Ich schlage vor, zumindest den ganzen Absatz über "Wichtige" Algorithmen zu löschen - die jetzige Auswahl ist willkürlich (es macht aber auch keinen Sinn, die Liste zu ergänzen, da sie seeeeehr lang würde) - die fragmentarischen Behauptungen dort sind widersprüchlich (Welches Problem löst Dijkstra denn nun? - sollte nicht schwer rauszukriegen sein, wo das Originalpaper ja nur 2,5 Seiten lang und gut lesbar ist.) und teils falsch (Dijkstra funktioniert nur für nichtnegative Gewichte) Was soll TSP für den Distanzgraph praktisch für einen Sinn ergeben?

Ich bezweifle, dass sich über einen konsistenten Gebrauch der Begriffe Pfad, Weg usw. in Wikipedia Einigkeit erzielen läßt. In manchen Kontexten ist es beispielsweise sehr sinnvoll, vor allem die Kanten eines Pfades zu betrachten - manchmal auch Knoten und Kanten - dies ist die allgemeinste Definition: P = v_0, e_1=(v_0, v_1), v_1, ... , v_n Dies würde ich bevorzugen - dann kann man sich bei Bedarf darauf einigen, dass die Kanten (oder Knoten) bei einer bestimmten Betrachtung gerade (der Kürze halber) weggelassen werden... Auf jeden Fall handelt es sich um Teilgraphen - keine Knotenmengen. Da die Terminologie in der Literatur tatsächlich nicht einheitlich gebraucht wird, würde ich nur von Pfaden und Kreisen sprechen - beide können "einfach" (ohne Knoten- bzw. Kantenwiederholungen) sein oder eben nicht. Zykel (ein gräßliches Wort!) und Wege braucht man dann gar nicht.

Gerichtete und ungerichtete Graphen sollten auch explizit unterschieden werden. Es gibt zwar azyklische Graphen, aber keine zyklischen (Oder? Quelle??) - diese müssen aber nicht kreisfrei (= Wälder) sein! -- Graf Alge 18:35, 16. Jun. 2009 (CEST)

Wege in Multigraphen

Im Artikel Kantenzug fand ich (vor meiner Überarbeitung) die Aussagen vor, Wege seien spezielle Kantenzüge, und im Falle von Multigraphen seien Kantenzüge zu unterscheiden, wenn sie über unterschiedliche Kanten zwischen zwei Knoten verliefen, so dass eine bloße Knotenfolge im Allgemeinen einen Kantenzug (und damit auch einen Weg) nicht identifiziert. Hier wird stattdessen geben, auch bei Multigraphen seien Wege nur Knotenfolgen. Kann überhaupt jemand ein Werk angeben, wo das so ist? Und wenn, auch für die Betrachtung als Kantenfolgen? Das täte auch dem Artikel Kantenzug gut, und zum Artikel Glossar Graphentheorie – Abschnitt Weg – stelle ich dieselbe Frage auf der dortigen Diskussionsseite. In Glossar Graphentheorie#Weg ist auch eine Bemerkung über unterschiedliche Terminologie bei "Weg" vs. "Kantenzug". Für alle drei Artikel wäre es schön, auch hierzu ("Wege" mit bzw. ohne Kanten- bzw. Knotenpaarwiederholung) Literaturbeispiele zu haben. – Die Betrachtungen als Kantenfolgen vs. als Teilgrafen würde ich gleichberechtigt nebeneinander stellen. – Ich habe auch aufgrund bloßer Vermutung bei den gerichteten Multigraphen die Mengenklammern durch normale Klammern ersetzt, ich bitte das zu prüfen und ggf. zu korrigieren. Man verwendet vielleicht überhaupt nur ein Klammernpaar. -- Lückenlos^wecken! 20:50, 12. Jul. 2009 (CEST)

Zusatz: Brückenproblem! Der Graph, der das Königsberger Brückenproblem darstellt, ist ein Multigraph. Die Insel („Kneiphof“) und das Nordufer („Altstadt“) entsprechen zwei Ecken, die durch zwei Kanten – die beiden Brücken (Krämerbrücke, Schmiedebrücke) – verbunden sind. Es ist wesentlich, über welche der beiden Brücken ein Weg führt. Der Weg über die Krämerbrücke ist ein anderer als der über die Schmiedebrücke, die „Knotenfolge“ (Kneiphof,Altstadt) kann den Unterschied nicht darstellen. Es ist ziemlich blöde, wenn die Wikipedia-Version von Weg („Eulerweg“) nicht geeignet ist, das Königsberger Brückenproblem, den unbestrittenen historischen Ausgangspunkt der Graphentheorie, darzustellen. -- Lückenlos^wecken! 02:26, 13. Jul. 2009 (CEST)

Ich sehe, dass das runde Klammernpaar 2006 bereits so vorhanden war, wie ich es jetzt wieder gemacht hatte – überhaupt vom Anfang des Artikels 2002 an. D. h., seitdem werden Wege in Multigraphen als Knotenfolgen dargestellt. -- Lückenlos^wecken! 15:16, 13. Jul. 2009 (CEST)

Und wie oben Zaph 15:59, 20. Dez. 2008 (CET), bitte auch ich um eine Erklärung von E(…)! -- Lückenlos^wecken! 16:08, 13. Jul. 2009 (CEST)

Nach längerem Grübeln: Offenbar ist E eine Funktion von $\{e\subseteq V:|e|=2\}$ nach IN, d. h .E({a,b}) = Anzahl der Kanten zwischen a und b. Äußerst ungewöhnlich. -- Zaph 22:44, 13. Jul. 2009 (CEST)

... in ungerichtenten Multigraphen. In gerichteten Multigraphen scheint $E:V\times V\rightarrow N$ zu sein. --89.247.99.181 11:44, 14. Jul. 2009 (CEST)

Und, wenn ich einen Graph G = (V, E) definiere (mit solch einer Funktion E), was ist dann eine "Kante"? -- Zaph 00:23, 15. Jul. 2009 (CEST)

E ist wohl einfach die Multimenge. Oder? --89.247.71.97 13:25, 15. Jul. 2009 (CEST)

Ich hatte auch Urheber Coma um Aufklärung gebeten, s. Ergebnis. Wenn die Darstellung so rätselhaft ist und niemand Literaturbeispiele dafür angeben kann, dann liegt es nahe, die Darstellung zu wählen, der man durchaus immer wieder begegnet. (Ein Lehrbuch mit Multigraphen habe ich gerade aber auch nicht zur Hand, bitte nachhelfen). Demnach ist ein Weg ein Kantenzug – ob ein Weg dann eine Knotenfolge, eine Kantenfolge oder eine Knoten-Kanten-…-Knoten-Folge ist – siehe dort. Normalerweise (?) ist ein Weg ein Kantenzug, der keine Kante zweimal durchläuft. Ein Pfad ist "normalerweise" ein Weg, der keinen Knoten zweimal durchläuft, Anfangs- und Endknoten dürfen jedoch übereinstimmen. Bei Pfaden ist die Betrachtung als zusammenhängende Teilgraphen mit Grad überall 1 oder 2 interessant, bei ungerichteten Graphen ist ein Effekt, dass man die Kantenfolge $(e_{1},e_{2})$ als Darstellung desselben Pfades betrachtet, den auch $(e_{2},e_{1})$ darstellt, und bei einem geschlossenen Pfad kommt es unter dieser Betrachtung nicht darauf an, welcher Knoten der Anfangs- und Endknoten ist (hierzu sollte aber wirklich Literatur angegeben werden). – Es müssen dann mehrere Artikel überarbeitet werden, auch weitere Stellen im vorliegenden Artikel. -- Lückenlos^wecken! 19:44, 2. Aug. 2009 (CEST)

Ich habe die Diskussion jetzt nur überflogen. Ehrlich gesagt kenne ich keinen Anwendungsfall für Wege/Pfade in Multigraphen. Es wird imho auch nicht definiert, was das in einem Mutligraphen sein soll. Vielleicht sollte man einfach das "(Multi-)" im betreffenden Abschnitt rausschmeißen?! --Koethnig 09:46, 28. Dez. 2009 (CET)

Siehe oben, der Ausgangspunkt der Graphentheorie, das Königsberger Brückenproblem ist ein solcher Anwendungsfall (vgl. dazu inzwischen meine Vorarbeiten). Ich habe schon wieder zuviel Zeit investiert, die ich nicht habe, und möchte deshalb jetzt nicht wieder im Artikel revertieren u.s.w.: Baustein: Die Begründung fürs Entfernen, den Baustein könnte man auch sonst überall anbringen, ist recht dumm, denn das Problem besteht tatsächlich durchgehend in den entsprechenden Artikeln (wie ich gerade vorher erklärt hatte), und ich habe den Baustein tatsächlich noch anderswo angebracht (s. a. meine Diskussion). Noch blöder, dann Diestel als Literatur anzugeben, wo etwas ganz anderes steht als im Artikel (nämlich zum Königsberger Brückenproblem). (Man beachte auch den kürzlichen Beitrag von SPTH weiter oben.) -- Lückenlos^wecken! 00:34, 29. Dez. 2009 (CET)

2013: Immernoch begriffliche Verwirrung

Das bereits 2005 (!!!) konstatierte Problem besteht immernoch! (s. u.a. auch meinen alten Beitrag oben und den vorstehenden von Lückenlos von 2009)

Aktuell: Die derzeitige Definition eines Weges im Artikel ist insbesondere für Multigraphen ungeeignet! Wenn wir Wege als Knotenliste definieren, weiss man ja beim Brückenproblem eben gerade das Wichtigste nicht - nämlich über welche Brücke (Kante) man als nächstes gehen soll! Ich schlage nochmals vor, der üblichen Definition eines Weges als (Teil-)Graph zu folgen. So steht es auch im Distel (Kap. 0.3 bzw. 1.3 in der englischen Version). Alles andere sind dann Vereinfachungen/Spezialfälle. (Auch bei schlichten (=einfachen) Graphen ist die Betrachtung als Kantenfolge oft hilfreich, beispielsweise bei der Implementierung verschiedener Algorithmen. Je nach benutzter Datenstruktur findet man nämlich den Endknoten einer Kante oft schneller als eine bestimmte inzidente Kante vom Knoten aussgehend.)

In vielen Lehrbüchern und Skripten, die Graphen - neben vielen anderen Inhalten - naturgemäß nur in einigen Aspekten behandeln, werden eben Vereinfachungen benutzt, die für die betrachteten Probleme gerade ausreichen bzw. besonders geeignet sind. Das rechtfertigt sich aus didaktischen Gründen (Keine Vorlesung kann alle Themen erschlagen!). Aber: Es macht halt solche Texte auch ungeeignet als Quelle für die Definition grundlegender Begriffe in einer Enzyklopädie wie Wikipedia. Wir sollten also auf originäre Monografien zur Graphentheorie (wie das Buch von Diestel) zurückgreifen. Leider verwenden auch da unterschiedlichen Autoren sowohl im Englischen als auch im Deutschen die Terminologie nicht einheitlich.

Offenbar gibt es jetzt wieder einige Autoren, die sich für Graphen interessieren und mehr Zeit haben als ich. An diese: Bitte, bitte nicht noch mehr Masse produzieren, die andere dann nacharbeiten sollen, sondern vor allem auf die Qualität (Korrektheit) achten. Weniger ist oft mehr. Und bitte eine klare Struktur anstreben. (Alles sollte nur einmal in Wikipedia stehen.)--Graf Alge (Diskussion) 10:32, 20. Aug. 2013 (CEST)

Habe mich dem Artikel angenommen. Sollte jetzt endlich mal auf einen ordentlichen Stand gebracht worden sein. Ein bisschen stören mich noch die ganzen Definitionen (Radius, etc.) die nicht viel mit Weg zu tun haben. --Andreschulz (Diskussion) 09:20, 7. Sep. 2013 (CEST)

Abschnitt Knotendisjunkt

Müsste es nicht heißen, dass i und j aus {2, ..., k-1} respektive {2, ..., l-1} heißen, da v_{k-1} bereits ein innerer Knoten ist? -- (ohne Name, da nicht angemeldet) 18:03, 13. Aug. 2011 (CEST) (ohne Benutzername signierter Beitrag von 178.2.210.233 (Diskussion) )

Jupp. Hab's geändert. --Daniel5Ko 18:54, 13. Aug. 2011 (CEST)

In diesem Abschnitt fehlt jetzt die Definition der (in der Überschrift aufgezählten) kantendisjunkten Wege. Diese lassen sich eben auch mit der jetzigen "Definition" (Weg=Liste von Knoten) nicht erklären. Kantendisjunkte Wege spielen aber eine wichtige Rolle, beispielsweise bei Routing-Algorithmen. --Graf Alge (Diskussion) 10:50, 20. Aug. 2013 (CEST)

A-B-Weg

Nach Diestel (4. Auflage) ist ein A-B-Weg, wenn $V(P)\cap A=\{x_{0}\}$ und $V(P)\cap B=\{x_{k}\}$.

Die hier beschriebene Version wäre hingegen eher: $\{x_{0}\}\cap A=\{x_{0}\}$ und $\{x_{k}\}\cap B=\{x_{k}\}$ – was bei weitem mehr erlauben würde, nämlich das z.B. auch innere Ecken des A-B-Weges Element von A oder B sein dürften.

Oder übersehe ich irgendetwas? --Tddt (Diskussion) 04:50, 6. Jun. 2012 (CEST) (05:25, 6. Jun. 2012 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

Ein Weg ist niemals ein Kreis und erst recht kein Zyklus

Im Artikel steht jetzt im Abschnitt Weg: Ein(sic!) Weg, bei dem der Start- mit dem Endknoten identisch ist, nennt man Zyklus und wenn dies der einzige wiederholte Knoten in der Knotenfolge ist, heißt dieser Kreis.

Nun ist ein Weg gerade so definiert, dass alle Knoten paarweise verschieden sind. Diese Definition von Zyklus ist also in sich widersprüchlich. Wenn ein Weg ein Zyklus ist, dann ist er kein Weg mehr. Bei der dann folgenden Defintion des Kreises wird dann auch noch darauf abgezielt, dass es im Zyklus sogar noch mehr wiederholte Knoten geben könne - damit ist das ganze erst recht nicht mehr mit der Definition des Weges zu vereinbaren.

Es ist nicht so, dass ich nicht verstehe, was gemeint ist, aber hier liest sich das so, als ob Zyklen und Kreise irgendwie besondere Formen von Wegen sind. Das sind sie aber nicht.

Ich schlage vor, die Definition aus Diestel zu übernehmen, danach entsteht ein Kreis aus einem Weg, in dem eine zusätzliche Kante zwischen den Endpunkten des Weges hinzugefügt wird. Ein Zyklus hat bei den Wegen aus den verschiedensten Gründen gar nichts zu suchen: Streng genommen ist ein Zyklus eine Kantenmenge (das spielt insbesondere bei der Betrachtung des Zyklenraums eine Rolle). Wenn man jetzt abweichend von dieser Definition den Zyklus als Teilgraphen auf Grundlage dieser Kanten versteht, dann kann dieser beliebig viele mehrfach vorkommende Knoten haben, das ist dann total ab"WEG"ig.  :-) Ich lass diesen Vorschlag jetzt mal eine Zeitlang hier stehen, bevor ich tätig werde, und bitte die bisherigen Autoren, sich zu äußern. Katzenpfote (Diskussion) 12:08, 4. Apr. 2019 (CEST)

Ich kann die Auffassung von Katzenpfote nicht teilen. Man hat hier auf Wikipedia - einer Enzyklopädie ! - immer bemüht zu sein, das Gesamtbild zu zeichnen. Auf manche Begriffe der Mathematik gibt es nun mal uneinheitliche Sichtweisen und dies ist auch aufzuzeigen.

Um es konkret zu machen: Diestel ist sicher eine erstklassige Quelle, aber eben nicht die einzige. Martin Aigner bspw. sagt es in seiner Graphentheorie (Springer Spektrum 2015) etwas anders: Hier ist ein Kreis ein Kantenzug, in dem alle Kanten und ebenso alle Ecken verschieden sind - mit Ausnahme der Anfangs- und der Endecke, die zusammenfallen sollen.

--Schojoha (Diskussion) 20:28, 5. Apr. 2019 (CEST)

Du hast völlig recht, es gibt gerade in der Graphentheorie ganz unterschiedliche Definition. Das ist hier aber nicht der Punkt, bei der Definition des Kreises ist das schon ziemlich einheitlich. Es geht darum, dass etwas nicht gleichzeitig ein Kreis und ein Weg sein kann. Ein Kreis ist nicht ein spezieller Weg, ein Zyklus erst recht nicht. Die Aigner-Definition unterscheidet sich auch inhaltlich überhaupt nicht vom Diestel. Diestel geht von einem Weg aus, und nimmt dann eine zusätzliche Kante hinzu, die den Anfangsknoten mit dem Endknoten verbindet. Dadurch habe ich ein neues Objekt, das ist dann kein Weg mehr, sondern ein Kreis. Aigner definiert einen Kreis als einen speziellen Kantenzug, nicht wie wir hier als einen speziellen Weg, anders gesagt: Aigner benutzt die Definition eines Kantenzuges und sagt, dass Anfangs- und Endknoten zusammenfallen, ansonsten aber alles (Kanten und Knoten) paarweise verschieden. Kommt genau dasselbe bei heraus.

Hier sagen wir: Das Ding ist ein Kreis und hat gleichzeitig Eigenschaften, die ein Kreis nicht hat. Das ist das (oder mein) Problem. Katzenpfote (Diskussion) 11:18, 6. Apr. 2019 (CEST)

Um es zu konkretisieren: Im Abschnitt "Weg" besteht offenbar eine Unvereinbarkeit zwischen dem Einleitungssatz und dem Schlusssatz. Die sollte bereinigt werden.--Schojoha (Diskussion) 20:45, 6. Apr. 2019 (CEST)

Spaziergang

Ist Spaziergang ein gängiger Begriff der Graphentheorie? Scheint mir in Wikipedia zu fehlen. Ich hätte Spaziergang als Weg verstanden, bei dem keine Kante mehrfach durchlaufen wird. 2A00:20:C061:5332:B9D0:FDB0:BF15:6279 07:28, 31. Mai 2022 (CEST)

Ich bezweifele, dass man den Terminus Spaziergang in den Standardtexten der deutschsprachigen Graphentheorie findet. Vielleicht denkt der obige User an eine Analogie zum walk, den es in den Büchern der englischsprachigen Graphentheorie gibt, etwa in Diestels Graph Theory. Dem entspricht in der deutschsprachigen Graphentheorie der Kantenzug. Kantenzüge können allerdings im Allgemeinen sehr wohl Kanten mehrfach enthalten. Dies hängt indes auch davon ab, welchen Autor man liest. Bei Rudolf Halin etwa findet man im Zusammnehang mit Kantenzügen in gerichteten Graphen die Forderung, dass hier keine Knoten und keine Kanten mehr als einmal auftreten sollen. Aber evtl. meint obiger User auch sowas wie Eulerwege.--Schojoha (Diskussion) 22:37, 2. Jun. 2022 (CEST)