TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 201

Für welche $m$, $n$ besitzt der vollständige paare Graph $K_{m,n}$ eine geschlossene Hamilton'sche Linie? (Die Knotenmenge $V$ eines vollständigen paaren Graphen $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}$).

Lösungsvorschlag: (korrigiert)

Eine geschlossene Hamiltonsche 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.

Lt. Angabe liegt ein Graph mit 2 disjunkten (nicht verbundenen) Teilgraphen vor, da er paarig ist, müßte jeder Teilgraph dieselbe Knoten- und auch Kantenanzahl enthalten, somit müßten m und n gleich sein, um die Bedingung zu erfüllen.

Lt. Urbanek ist unter einem vollständigen paarigen Graphen mit 2 disjunkten Teilmengen ein ungerichteter Graph zu verstehen, wobei zunächst jeder Knoten der einen Teilmege mit jedem Knoten der anderen Teilmenge verbunden ist.

Die Hamiltonsche Linie entsteht, indem man den Graphen von eimem Knoten nach dem anderen durchwandert, bis man wieder den Anfagsknoten erreicht hat. Dies geht aber nur, wenn m,n > 1 und m = n, sonst kann kein Kreis entstehen.

Hapi

Danke für den Hinweis!