139 lines
3.8 KiB
Markdown
139 lines
3.8 KiB
Markdown
---
|
|
title: Hamiltonkreise
|
|
date: 2018-11-20
|
|
---
|
|
|
|
**Idee**:
|
|
|
|
* Handelsresenden (traveling salesman)
|
|
* Städte $\widehat{=}$ Knoten
|
|
* Flugverbindungen $\widehat{=}$ Kanten
|
|
|
|
|
|
|
|
Handelsreisende möchte alle Städt genau einmal besuchen und wieder am
|
|
Ausgangspunkt enden. Das heißt, er sucht einen Kreis im Graphen, in dem jeder
|
|
Konten vorkommt. Finden eines solchen Kreises: Traveling Salesman Problem
|
|
(TSP).
|
|
|
|
# Definition (Hamiltonkreis)
|
|
|
|
Sei $G=(V,E)$ zusammenhängender Graph.
|
|
|
|
i) Ein Hamiltonkreis in $G$ ist ein Kreis, in dem jeder Knoten vorkommt, d.h.
|
|
$K = (v_1, ..., v_s)$ mit
|
|
a) K ist Kreis
|
|
a) $\{ v_i | i \in \{1,..., s\} \} = V$
|
|
|
|
i) Ein Graph, der einen Hamiltonkreis enthält, heißt **hamiltonisch**.
|
|
|
|
|
|
**Beispiel**:
|
|
|
|
i) $K_n$ vollständiger Graph mit $n$ Knoten, d.h. $K_n = \{ \{1,...,n\},
|
|
\binom{V}{2} \}$ ist hamiltonisch, da $k = \{1,2,...,n\}$ ein Hamiltonkreis.
|
|
|
|
i) $Q_n$ sind hamilton. Beweis per Induktion und Verbinden der zwei zu
|
|
$Q_{n-1}$ isomorphen Graphen.
|
|
|
|
Betrachte $Q_{n+1}$. Per Induktionsvoraussetzung gibt es in $Q_n$ einen
|
|
Hamiltonkreis $K = (v_1, ..., v_{2^n})$
|
|
|
|
Konstruiere daraus $K' = (\binom{v_1}{0}, \binom{v_2}{0}, ...,
|
|
\binom{v_{2^n}}{0}, \binom{v_{2^n}}{1}, \binom{v_{2^n - 1}}{1}, ...
|
|
\binom{v_1}{1})$ als Hamiltonkreis in $Q_{n+1}$
|
|
|
|
|
|
**Frage**: Wie findet man im allgemeinen einen Hamiltonkreis für einen
|
|
gegebenen Graphen? Oder wie entscheidet man, ob ein gegebener Graph
|
|
hamiltonisch ist?
|
|
|
|
|
|
# Algorithmus (Hamiltonisch)
|
|
|
|
**Eingabe**: $G=(V,E)$ mit $V = \{1, ..., n\}$
|
|
|
|
i) Für alle Permutationen $\pi: \{ 1, ..., n\} \rightarrow \{1,...,n\}$
|
|
a) teste, ob $(\pi(1),\pi(2),...,\pi(n))$ ein Hamiltonkreis ist
|
|
a) falls ja, STOP
|
|
i) Ausgabe: "nicht hamiltonisch"
|
|
|
|
|
|
**Korrektheit**: klar. Algorithmus testet alle möglichen Hamiltonkreise.
|
|
|
|
**Laufzeit**: Anzahl der Permutationen, d.h. $O(n!)$ exponentiell in $n$.
|
|
|
|
|
|
Der Algorithmus ist schon für relativ kleine $n$ ($n \approx 20$) nicht mehr
|
|
praktisch durchführbar.
|
|
|
|
*Vermutung*: Es gibt keinen wesentlich besseren (d.h. polynomielle Laufzeit)
|
|
Algorithmus.
|
|
|
|
Aber es gibt Fälle, in denen es einfach(er) ist. Insbesondere dann, wenn es
|
|
|
|
i) sehr wenige Kanten gibt
|
|
i) sehr viele Kanten gibt
|
|
|
|
|
|
**zum ii) Fall**:
|
|
|
|
# Satz
|
|
|
|
Sei $G=(V,E)$ ein zusammenhängender Graph mit der Eigenschaft, dass $deg(x) +
|
|
deg(y) \geq |V|, \forall x \neq y, \{x,y\} \notin E$
|
|
|
|
Dann ist $G$ hamiltonisch.
|
|
|
|
|
|
# Beweis
|
|
|
|
(per Widerspruch)
|
|
|
|
Wir nehmen an, der Satz ist falsch. Dann gibt es ein Gegenbeispiel. Sei
|
|
$G=(V,E)$ ein solches Gegenbeispiel mit maximaler Anzahl an Kanten (bei
|
|
gegebenen $V$). Da $G$ nicht der vollständige Graph sein kann, gibt es $x,y \in
|
|
V$ mit $\{x,y\} \notin E$. Da $G$ maximal war, gibt es in $G'=\{V,E \cup
|
|
\{x,y\}\}$ einen Hamiltonkreis $k = (x=v_1,v_2,...,v_n=y)$ (die Kante
|
|
$\{x,y\}$ muss in $k$ genutzt werden).
|
|
|
|
Hier könnte ein Bild entstehen.
|
|
|
|
Betrachte 2 Mengen:
|
|
|
|
* $S = \{ v_i | \{x,v_{i+1}\} \in E \}$
|
|
* $T = \{ v_i | \{y, v_i\} \in E \} = \Gamma(y)$
|
|
|
|
Es gilt:
|
|
|
|
i) $y \notin S \cup T$, denn $y \notin T$, da keine Schleifen und $y \notin S$
|
|
per Definition
|
|
i) $|S| + |T| = |\Gamma(x)| + |\Gamma(y)| = deg(x) + deg(y) \geq |V|$ damit
|
|
folgt $S \cap T \neq \emptyset$, da $|V| > |S \cup T| = |S| + |T| - |S\cap T|
|
|
\geq |V| - |S \cap T|$
|
|
|
|
$\Rightarrow |S \cap T| > 0$
|
|
|
|
|
|
Sei $v_i \in S \cap T$, dann ist $k' =
|
|
(x=v_1,...,v_i,y=v_n,v_{n-1},...,v_{i-1})$ ein Hamiltonkreis in $G$.
|
|
|
|
Widerspruch dazu, dass $G$ Gegenbeispiel.
|
|
|
|
$$
|
|
\tag*{$\Box$}
|
|
$$
|
|
|
|
|
|
Der Beweis liefert auch einen Algorithmus, um für solche Graphen effizient
|
|
Hamiltonkreise zu finden.
|
|
|
|
**Idee**: Gegeben $G=(V,E)$. Starte mit beliebigen Hamiltonkreis
|
|
$k=(v_1,...v_n)$ wobei nicht alle Kanten in $E$ liegen (kein Hamiltonkreis in
|
|
$G$).
|
|
|
|
Entferne nach der Konstruktion im Beweis Kanten aus $k$, die nicht in $E$
|
|
liegen, und ersetze diese durch Kanten in $G$.
|
|
|
|
**Laufzeit**: $O(n)$ Iterationen.
|