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:41, 16. 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.