 |
 |
 |
 |
 |
 |
Startseite » Forum » Euler-Zyklus prüfen bei Graphen.
Euler-Zyklus prüfen bei Graphen.
Universität / Fachhochschule
Graphentheorie
Tags: euler, Graphentheorie
 
|
  |
|---|
|
Hallo, habe eine Frage schreibe bald eine Klausur, die auch das Thema Graphentheorie beinhaltet. Nun ist mir eine Adjanzenmatrix eines ungerichteten Graphen vorgegeben. Ich muss dann den Graphen zeichnen und dann die frage beantworten ob es eben einen Euler-Zyklus vorhanden ist. ich habe die Lösung für diese aufgabe, der Graph ist nicht zusammenhämgend...also nicht eulersch. Das hilft mir nicht unbedingt weiter und durchs googlen wird es mir auch nicht unbedingt klarer. Es ist immer die Rede von einem geraden Knotengrad... kann mir da einer helfen? Wie stelle ich bei einem Graphen fest, dass er einen Eulerischen Zyklus hat? Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg." |
|
 |
|
nen eulerkreis ist eine tour durch den graphen die jede kante ganau einmal besucht und alle knoten beliebig oft. 1. wenn der graph nicht zusammenhängend ist, kannst du keine tour finden in der alle kanten sind, da es ja keine Verbindung zwischen den Teilgraphen gibt. Da es also überhaubt keine Tour gibt die alle kanten beinhaltet gibt es natürlich auch keine tour die jede kante genau einmal enthält. 2. angenommen der Graph wäre zusammenhängend, so müsste jeder knoten im graphen einen geraden grad haben damit es einen Eulerweg gibt. (wenn dieses kriterium erfüllt ist, gibt es mit 100%er wahrscheinlichkeit eine solche tour) Der grad eines Knotens ist die anzahl der kanten, die an diesen knoten anliegen. Du musst also nur jeden Knoten angucken und wenn keiner dabei ist mit ungeradem grad so gibt es automatisch einen Eulerweg, diesen dann auch zu finden kann aber ein wenig dauern, ist aber gar nicht nötig von der Aufgabenstellung her. |
 |
|
Supi, danke für die Antwort! habs verstanden :-) |
679620
679522