Diskussion:Eulerkreisproblem
Kann es sein das der Text unter dem Beispielbild nciht ganz korrekt ist? Denn afaik ist der grüne "Kreis" gar kein Kreis sondern lediglich ein Zykel oder? Knoten 9 wird ja "zwischendurch" 2x besucht ;) --- (nicht signierter Beitrag von 79.255.192.80 (Diskussion) 20:19, 26. Mär. 2011 (CET))
Sollte es nicht heissen:
"Wenn in einem Graphen G ein offener Eulerweg existiert, dann haben genau 2 Knoten ungeraden Grad" --Roadexpert 13:18, 25. Jun. 2007 (CEST)
Wir sollten konsistent bleiben!!! Ich habe Eulerweg anders definiert, aber das werd ich wohl ändern... --Coma 18:29, 16. Feb 2003 (CET)
Ist klar, da müssen wir aufpassen, aber das Problem der Konsistenz ist bei jeder Bearbeitung an der gesamten Wikipedia zu beachten. Ich habe einige Teile verschoben und einige herausgenommen. Darunter auch folgenden Absatz:
Eine Formale Definition des Problem Eulerkreis ist folgende:
Sei G=(V, E) ein (gerichteter) Graph ohne Mehrfachkanten. Falls E ein Zyklus in G ist, und für jede Kante {va,vb} bzw. (va,vb) gilt, dass es genau ein i aus {1,...,n} gibt, so dass va=vi und vb=vj, wobei j=i+1, falls i≠n und j=0 sonst, so nennt man E Eulerkreis oder Eulertour. Anschaulich bedeutet die Definition, dass W jede Kante genau einmal benutzt. Falls ein Graph G einen Eulerkreis enthält, so nennt man G eulersch. Beim Eulerweg muss der alle Kanten benutzende Kantenzug nicht geschlossen sein.
Könnte auch noch dazu, aber warum kompliziert, wenn's auch einfach geht? --JakobVoss 18:51, 16. Feb 2003 (CET)
Für den Laien, der bei Google nach "Eulerweg" sucht, ist dieser Text immer noch unverständlich. Denn der Eulerweg ist eigentlich eine ganz einfache Sache und auch sehr einfach zu erklären: Sobald ein Graph mehr als 2 "ungerade" Knoten (also Knoten mit ungeradem Grad) hat, kann er keinen Eulerweg (und somit auch keinen Eulerkreis) mehr besitzen. Bei allem respekt vor mathematisch korrekteren und wissenschaftlicheren Definitionen: Warum sollte man diese einfache Aussage dem interessierten Laien vorenthalten? Ich werde sie mit einbauen. --Sevenstar, 22. Feb 2004
Auf der Seite steht "Ein Eulerkreis (auch Eulertour oder Eulersche Linie) ist in der Graphentheorie ein Kreis," - das ist aber soweit ich das erkennen kann nicht konsistent, denn in einer Eulertour ist es durchaus erlaubt eine Ecke mehrfach zu besuchen. Es muss nur jede Kante genau einmal verwendet werden. Ein Kreis ist aber so definiert dass jede Ecke nur einmal besucht werden darf. -- Jan Niehusmann, 02.05.2004
- Ja, es muss "Zyklus" heißen!!! --Coma 19:01, 2. Mai 2004 (CEST)
Unter Eigenschaften werden die äquivalenten Punkte so angegeben, dass jeder eulersche Graph zusammenhängend ist. Nach Definition müssten aber isolierte Knoten erlaubt sein? -- Martin 07.01.2005
- Puh... wenn ich nicht selbst so ein Korintenkacker wäre, würde ich sagen: Korintenkacker! :-))) Ja, du hast wohl recht... ich werde mich noch mal an anderer Stelle schlau machen. Danke für den Hinweis! --Coma 20:33, 7. Jan 2005 (CET)
- So, ich habe das "Problem" mal dadurch gelöst, dass ich von eulerschen Graphen auch verlange, dass sie zusammenhängend sind! Das ist eigentlich auch sinnvoll! Wen interessieren schon isolierte Knoten. --Coma 20:44, 7. Jan 2005 (CET)
Komplexität
"Das Problem lässt sich relativ leicht algorithmisch lösen" - Komplexitätsklasse sollte erwähnt werden.
Allgemeine Formel
Gibt es eigentlich eine allgemeine Formel, mit der man die Anzahl der möglichen verschiedenen Lösungswege eines beliebigen (ungerichteten) Graphen errechnen kann? --85.178.43.207 01:08, 8. Mär. 2008 (CET)
- siehe BEST-Theorem --Chin tin tin 02:24, 8. Aug. 2008 (CEST)
Verschiedene Definitionen von eulersch?
Hallo, die Definition von eulersch ist laut Artikel "Einen zusammenhängenden Graphen, der einen Eulerkreis besitzt, bezeichnet man auch als eulersch.". Unter den Eigenschaften steht dann, dass G eulersch äquivalent ist zu "G ist zusammenhängend und jeder Knoten hat geraden Grad.". Das ist meiner Meinung nach falsch, gemeint ist in diesem Abschnitt mit eulersch, dass G selbst ein Eulerkreis ist, oder? Wenn ja, bitte korrigieren. Gruß --Star Flyer (Diskussion) 00:07, 21. Okt. 2012 (CEST)
