Diskussion:Durchlaufbarkeit von Graphen

Ich lagere den Komplex Eulertour in einen eigenen Artikel, so dass er auch alleine verständlich ist (z.B. wenn man sich für das Königsberger Brückenproblem interessiert). Folgenden Absatz lasse ich ganz weg, da Multigraphen in der sprachlichen Definition einer Eulertour enthalten sind ("jede Kante einmal" heisst für mich, dass wenn zwischen zwei Knoten mehrere Kanten sind, diese alle benutzt werden müssen, oder sehe ich das falsch?). --JakobVoss 18:33, 16. Feb 2003 (CET)

Ich fände es besser, wenn Du die Artikel so läßt wie sie sind (ggf. erweiterst). Einen spezielleren neuen Artikel kannst Du gerne schreiben! Aber zur Durchlaufbarkeit gehört nun mal auch Eulertour usw... Bei Multigraphen kommt es darauf an, wie man sie interpretiert! Ich habe versucht formal korrekt zu sein. Und für Mutligraphen auf eine Reduktion zu verweisen kann nicht schaden! Es geht ja nicht nur um die Definition, sondern auch darum, wie man die Probleme lößt. Und da ist der Abschnitt wichtig! --Coma 18:41, 16. Feb 2003 (CET)

Ich kann beim besten Willen nicht an den Artikel weiterarbeiten, wenn ich nix verändern darf. Ich kann verstehen, dass es ärgerlich ist, wenn jemand die eigene Struktur verändert und fände es auch erstmal doof, wenn jemand z.B.Bibliothekswesen änders forführt als ich es mir gedacht habe, aber das ist nun mal die Wikipedia-Philosophie, dass jeder Änderungen vornehmen darf. Ich konzentriere mich jetzt auf neue Artikel (z.B. Flüsse und Schnitte in Netzwerken und Königsberger Brückenproblem) aber sobald ich darin Verweise vornehme muss ich zwangsläufig anpassungen vornehmen. Den Artikel Eulerkreis gab es noch nicht und Durchlaufbarkeit von Graphen ist als Verallgemeinerung des Königsberger Brückenproblem mit TSP und Hamilton zu umfangreich, also ist es doch besser einen Artikel zu splitten.

Die Reibungsverluste bei unserer gemeinsamen Arbeit rühren daher, dass Du überall allgemeine formale Definitionen angeben möchtest (Top-Down) und ich versuche daraus ein Nachschlagewerk zu machen, das auch Nicht-Mathematiker verwenden können (Bottom-Up). Selbst in der Mathematik gibt es aber keinen Konsens über die "richtige" Bezeichnung von Phänomenen.

Der Artikel Durchlaufbarkeit von Graphen braucht Meiner Meinung nach unbedingt die Erwähnung aller 3 Teilgebiete (Eulersche Graphen, Hamiltonische Graphen und TSP). Ich hab prinzipiell nichts dagegen, wenn Du noch 3 Extra-Artikel schriebst. Dann kann man den Artikel Durchlaufbarkeit auch als übergeordneten Artikel betrachten und kürzen, sofern die Infos dann in den anderen Artikeln stehen. --Coma 23:53, 16. Feb 2003 (CET)

Ich fände es auch besser den Artikel Eulerkreis nach eulerscher Graph zu verschieben! Falls Du wirklich den Splitt des Artikels haben willst würde ich als Titel für die anderen Artikel hamiltonischer Graph und Traveling-Salesman-Problem vorschlagen! --Coma 23:53, 16. Feb 2003 (CET)

OK. TSP wird denke ich mal auch so oft genannt, dass ein eigener Artikel angebracht ist. --JakobVoss 11:00, 17. Feb 2003 (CET)

---

Für Graphen mit Mehrfachkanten kann man die Begriffe Eulerkreis bzw. eulersch ebenfalls definieren, die Definition ist dann aber technisch etwas schwieriger (eine Kante muss entsprechend ihrer Vielfachheit mehrfach benutzt werden). Da es eine einfache Reduktion auf Graphen ohne Mehrfachkanten gibt, so dass der resultierende Graph ohne Mehrfachkanten genau dann eulersch ist, wenn es der originale Graph mit Mehrfachkanten ist, verzichten wir hier auf die Definition. Die Reduktion ersetzt lediglich Mehrfachkanten {v,w} bzw. (v,w) durch neue Knoten (entsprechend ihrer Vielfachheit) und verbindet diese (im gerichteten Fall unter Berücksichtigung ihrer Richtung) mit v und w.

---

Artikel sollte getrennt werden!

Ich finde die momentane Aufteilung unzweckmäßig. Die Artikel TSP und Hamilton sollten eigene Artikel werden. Stern 17:32, 1. Feb 2004 (CET)

Nein, der Titel sagt worum es geht, und da gehört beides rein. Das beudeutet nat. nicht, dass es Extra-Artikel für TSP und Hamilton geben sollte. Eigentlich gehören hierher auch noch die Euler-Kreise... --Coma 18:40, 1. Feb 2004 (CET)

TSP ist zwar ein Problem der Informatik. Es wird aber beispielsweise in der Logistik, der WI und anderswo angewendet. Teilweise in Bereichen, die sich überhaupt nicht mit der im Artikel beschriebenen informatischen Ebene des TSPs oder mit dem Hamilton-Graphen insgesamt beschäftigen. Teilweise spielt nicht einmal Graphentheorie eine betonte Rolle. Wenn man keine eigenen Artikel zulässt, verwehrt man Nichtinformatikern den Zugang, selbst wenn er zweckmäßig wäre. Man könnte diesen Artikel vielleicht als eine Kurzzusammenfassung der drei Probleme für die Informatiker nutzen und am Ende jeweils auf die eigentlichen Artikel verweisen. Stern 18:48, 1. Feb 2004 (CET)

Ähhm, ich hab oben ein kleines Problem mit meiner doppelten Verneinung gehabt, die dann wohl nur eine einfache war. Also: Ja, eigene Artikel zu TSP und Hamilton sind erlaubt. Aber hier sollten alle 2 (oder besser 3) Probleme auf dieser Ebene (eventuell leichter verständlich) erwähnt werden. Ansonsten ist TSP natürlich kein Problem der Informatik, sondern der Graphentheorie. Das es überall gebraucht wird steigert nur seine Populartität, ändert aber nichts an der Tatsache, dass man es mit graphentheoretischen Mitteln beschreibt und versucht zu lösen und demnach diesem Zweig der diskreten Mathematik zuzuschreiben hat. Der Versuch es aus anderen Richtungen darzustellen würde zwangsläufig in einem Schwafel-Artikel enden, in dem jeder erzählt wo ihm das Problem schon mal über die Leber gelaufen ist. D.h. natürlich nicht, dass man nicht auch erwähnen sollte, wo Anwendungsfälle liegen (so, diesemal hat die doppelte Verneinung hoffentlich funktioniert *g*) --Coma 00:11, 2. Feb 2004 (CET)

Wenn man mal auf "Was zeigt hier hin" klickt, wird deutlich, wie viele Artikel eigentlich lieber auf einen Einzelartikel als auf die hier zwanghaft vereinigten beiden Artikel zeigen wollen. Lieber kurze Artikel! Wer das jeweils andere Problem lesen will, kommt mit einem Klick dort hin, die Übersicht aber steigt enorm. Stern 18:35, 3. Feb 2004 (CET)

Ich merke schon, dass ich mal wieder ran muss und einiges umstrukturieren darf. Ich hoffe ich finde bald die Zeit dazu, dann schau ich mir das Gebiet der Graphentheorie in der Wikipedia mal wieder näher an... --Coma 19:57, 3. Feb 2004 (CET)

Graphentheorie II ist immer im WS, oder? Sonst könnte ich auch mal wieder mitmachen ;-) -- Nichtich 14:57, 4. Feb 2004 (CET)

Du meinst "Graphen und Algorithem II"! Nein, dass ist im Sommersemester. Mir schwebt momentan vor, ein extra Portal für Graphentheorie aufzumachen... --Coma 16:39, 4. Feb 2004 (CET)

Generell sollten in der Wikipedia immer lieber viele kleine statt einem großen Artikel geschrieben werden. Das mag zunächst absurd erscheinen: es wurde jedoch wissenschaftlich erwiesen, dass gut vernetzte Dateien mit geringem Umfang der Informationsauffindung in semantischen Netzen am dienlichsten sind. Dazu gab es Studien. Es würde also durchaus Sinn machen, auch diesen Artikel aufzuteilen, solange eine zweckmäßige und übersichtliche Vernetzung der Artikel untereinander gewährleistet ist. Die momentane Aufteilung ist also die der Informationauffindung am meisten entgegenstehende. 82.83.11.41 18:31, 15. Feb 2004 (CET)

---

Ich habe nun mal Nägel mit Köpfen gemacht und die Artikel getrennt. Ich hoffe, dass es mir gelungen ist. Ich habe die REDIRECTS bereits größtenteils entsprechend angepasst. Stern 00:17, 22. Feb 2004 (CET)