TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 307

Aus VoWi
Zur Navigation springen Zur Suche springen

Für welche m, n besitzt der vollständige bipartite Graph K_{m,n} eine geschlossene Hamilton'sche Linie? (Die Knotenmenge V eines vollständigen bipartiten Graph K_{m,n} besteht aus 2 disjunkten Teilmengen V_1, V_2 mit \left|V_1\right|=m und \left|V_2\right|=n, und die Kantenmenge E besteht aus allen ungerichteten Kanten (v_1, v_2) mit v_1\in V_1 und v_2\in V_2).

Hilfreiches[Bearbeiten]

Eine geschlossene Hamilton'sche Line besteht nach der Definition aus einem Kreis, wobei jeder Knoten (nicht Kante!) nur einmal durchlaufen wird. Die Minimalvariante eines Kreises wäre ein Dreieck.

Lösung[Bearbeiten]

Ein vollständiger bipartiter Graph mit 2 disjunkten Teilmengen ist ein ungerichteter Graph, wobei zunächst jeder Knoten der einen Teilmenge, mit jedem Knoten der anderen Teilmenge, verbunden ist. Die Hamilton'sche Linie entsteht, indem man den Graphen einen Knoten nach dem anderen durchwandert, bis man wieder den Anfangsknoten erreicht hat. Dies geht aber nur wenn m, n > 1 und m = n, sonst kann kein Kreis entstehen.