TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 312

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}$).

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches

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

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.

Lösung von neo

Laut Satz 2.31 (Mathematik für Informatik, 4.Auflage) gilt: Sei $G$ ein schlichter ungerichteter Graph mit $n$ Knoten, so dass für alle Knotenpaare $x,y\in V(G)$, die in $G$ nicht durch eine Kante verbunden sind, d.h.$(x,y)\notin E(G),d(x)+d(y)\geq n$ gilt. Dann gibt es in $G$ eine geschlossene Hamilton'sche Linie.

Definition 2.30: Eine Kantenfolge in einem (gerichteten oder ungerichteten) Graphen G heißt Hamilton'sche Linie, wenn sie jeden Knoten (mit der möglichen Ausnahme, dass Anfangs- und Endpunkt übereinstimmen) genau einmal enthält.

Nun also zu meiner Lösung:
Da in einem vollständigen bipartiten Graphen alle Elemente einer Menge $A$ mit allen Elementen der Menge $B$ verbunden sind, folgt:
$\forall x\in V_{1}\mid d(x)=|V_{2}|=n\,\,\to \,\,d(x_{i})+d(x_{j}),i\neq j\geq m+n\,\,\to \,\,n+n\geq m+n\,\,\to \,\,2n\geq m+n$
$\forall y\in V_{2}\mid d(y)=|V_{1}|=m\,\,\to \,\,d(y_{k})+d(y_{m}),k\neq m\geq m+n\,\,\to \,\,m+m\geq m+n\,\,\to \,\,2m\geq m+n$
$2n\geq m+n\,\,\to \,\,n\geq m$
$2m\geq m+n\,\,\to \,\,m\geq n$
$n\geq m\land m\geq n\,\,\to \,\,m=n$
Da ein vollständiger bipartiter Graph mit 0 Knoten keine Hamilton'sche Linie haben kann, kann man die 0 damit ausschließen.
Damit wurde bewiesen: $m=n\land m,n\geq 1$
(Edit zur vorigen Lösung: Ich habe die Definition der Hamilton'sche Linie hingeschrieben, weil laut ihr ein bipartiter Graph mit 2 Knoten auch eine Hamilton'sche Linie besitzen kann. Es müssen ja nur alle Knoten durchlaufen werden und Anfangs- und Endpunkt können übereinstimmen, müssen aber nicht.)