Mathematik Graphentheorie – Euler- und Hamilton-Pfade
Karteikarten zum Thema „Mathematik“ · 15 Karten · von atrio. Beispiele: Was ist ein Euler-Pfad in einem Graphen? · Was unterscheidet einen Euler-Kreis vom Eu…
Karten
15 KartenWas ist ein Euler-Pfad in einem Graphen?
Rückseite
Ein Euler-Pfad durchläuft jede Kante des Graphen genau einmal, Knoten dürfen mehrfach besucht werden.
Was unterscheidet einen Euler-Kreis vom Euler-Pfad?
Rückseite
Ein Euler-Kreis ist ein geschlossener Euler-Pfad, Start- und Endknoten fallen zusammen.
Wann besitzt ein zusammenhängender Graph einen Euler-Pfad?
Rückseite
Genau dann, wenn er null oder zwei Knoten mit ungeradem Grad hat.
Wann besitzt ein zusammenhängender Graph einen Euler-Kreis?
Rückseite
Genau dann, wenn alle Knoten geraden Grad haben.
Was ist ein Hamilton-Pfad in einem Graphen?
Rückseite
Ein Hamilton-Pfad besucht jeden Knoten des Graphen genau einmal, Kanten dürfen mehrfach genutzt werden.
Was ist ein Hamilton-Kreis?
Rückseite
Ein Hamilton-Kreis ist ein geschlossener Hamilton-Pfad, der jeden Knoten genau einmal besucht und zum Startknoten zurückkehrt.
Was ist der fundamentale Unterschied zwischen Euler- und Hamilton-Pfaden?
Rückseite
Euler-Pfade betreffen das einmalige Durchlaufen aller Kanten, Hamilton-Pfade das einmalige Besuchen aller Knoten.
Was besagt der Satz von Dirac für Hamilton-Kreise?
Rückseite
Ein Graph mit n ≥ 3 Knoten und minimalem Grad ≥ n/2 besitzt einen Hamilton-Kreis.
Was besagt der Satz von Ore für Hamilton-Kreise?
Rückseite
Für alle nicht-adjazenten Knotenpaare gilt: Grad(u) + Grad(v) ≥ n ⇒ Graph hat Hamilton-Kreis.
Wie unterscheiden sich die algorithmischen Komplexitäten von Euler- und Hamilton-Problemen?
Rückseite
Euler-Pfade sind in polynomieller Zeit findbar (P), Hamilton-Pfade sind NP-vollständig.
Wie funktioniert der Algorithmus von Fleury für Euler-Pfade?
Rückseite
Startknoten wählen, Kanten nacheinander entfernen, wobei Brücken erst zuletzt gewählt werden, wenn keine Alternative existiert.
Was ist der Vorteil des Hierholzer-Algorithmus gegenüber Fleury?
Rückseite
Hierholzer findet Euler-Kreise in linearer Zeit O(|E|) durch Zyklus-Zerlegung und Einfügen, effizienter als Fleury.
Für welche n besitzt der vollständige Graph K_n einen Euler-Kreis?
Rückseite
K_n hat einen Euler-Kreis genau dann, wenn n ungerade ist (alle Knoten haben Grad n-1, geradzahlig).
Für welche n besitzt der vollständige Graph K_n einen Hamilton-Kreis?
Rückseite
K_n besitzt für alle n ≥ 3 einen Hamilton-Kreis, da jeder Knoten mit jedem anderen adjazent ist.
Welches klassische Optimierungsproblem entspricht der Suche nach einem Hamilton-Kreis minimalen Gewichts?
Rückseite
Das Problem des Reiseverkäufers (TSP) sucht einen Hamilton-Kreis minimalen Gesamtgewichts in gewichteten Graphen.