Diskussion:Weg (Graphentheorie)

[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)

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)