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 explizt den Abschnitt für Mutligraphen und 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)
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.