date-created: 2024-06-14 04:03:42 date-modified: 2024-07-04 06:55:14

Hamiltonkreise

anchored to 115.00_graphentheorie_anchor proceeds from 115.01_grundlagen

Während wir bei 115.02_eulersche_Graphen geschaut haben, dass wir Kreise finden können, die jede Kante maximal einmal besuchen und somit komplett traversieren, möchten wir mit Hamiltonkreisen stattdessen Kreise konstruieren, die jeden Knoten nur einmal besuchen! (Dabei wird auch schon ausgeschlossen, dass man eine Kante mehrfach nehmen kann - logischerweise).

Definition

[!Definition] Hamiltonkreis #card

Betrachten wir einen Graphen $G$. Wir nennen einen Kreis (oder wieder Weg, mit unterschiedlichen Anfang/Ende) jetzt Hamiltonkreis/weg, wenn dieser jeden Knoten genau einmal durchläuft.

Ein Graph ferner hamiltonisch. falls wir darin einne Hamiltonkreis finden können. mögliches Beispiel:

[!Example] ist hier ein Hamiltonkreis möglich? (Skelett eines Dodekaeder) #card

Ja, wenn man ihn “entsprechend durchläuft”, kann man immer erst alle anderen Ebenen durchlaufen und so nach und nach wieder zum Anfang kommen.

Satz (5) | Hamiltonkreise/wege sind NP-schwer

(siehe Karp 1972).

[!Definition] Hamiltonkreise / wege sind NP-schwer zu finden warum? #card Es ist möglich das Problem der Hamiltonkreise auf das SAT-Problem zu reduzieren, welches ebenfalls NP-schwer ist. $SAT{⪯}_{p}CLIQUE{⪯}_{p}VC{⪯}_{p}gerHK{⪯}_{p}HK$ -> das Problem lässt sich also in Polynomialzeit auf ein anderes reduzieren ( gemeint mit ${⪯}_p$) -> es ist höchstens so schwer, wie das reduzierte -> hier SAT. WEll und SAT IS NP-Schwer!

Was machen mit Hamiltonschen Graphen

Da wir nur in NP bestimmen können, ob ein Graph hamiltonsch ist, bieten sich andere Ansätze um dennoch etwas schneller in der Bestimmung zu werden. Diese inkludieren folgende: welche? #card

• Graphenklassen finden, in welchen alle Graphen hamiltonsch sind
• möglichst große Graphenklassen finden, in welchen man das Problem polynomiell lösen kann
• notwendige oder hinreichende Bedinungen finden, sodass ein Graph als hamiltonsch bestimmt werden kann

Ferner möchten wir jetzt also bestimmte Eigenschaften aufbauen, die uns dabei helfen über hamiltonsche Graphen gewisse Informationen zu erlangen.

Satz (6) | erweitern eines hamiltonsch’en Graphen

[!Definition]

Sei $G=(V,E)$ ein Graph mit $\mid V\mid \ge 3$ Weiterhin seien jetzt $u,v\in V$ zwei nicht adjazente Knoten mit ${\mathrm{deg}}_G(u)+{\mathrm{deg}}_G(v)\ge |V\mid$ Dann gilt folgend:

Was gilt jetzt im Bezug auf hamiltonsch? #card

$$G\text{ hamiltonsch }⟺G+uv\text{ hamiltonsch }$$ also eigentlich ist $G$ folgend: ($G^{\prime }=(V,E\cup \{uv\}$)

eine Beweisüberlegung wäre:

• Da gefordert wird, dass die Summe von inzidenten Kanten größer gleich der Menge von Kanten in $V$ ist

Satz von Bondy-Chávtal

Der (Hamiltonsche) Abschluss $H=h(G)$ von einem einfachen Graphen $G$ mit $n$ Knoten ist der kleinste Obergraph - geringste Menge von Kanten, Knoten ändert sich ja nicht - von $G$, für welchen gilt:

$d_H(u)+d_H(v)<|V\mid =n$ für alle in H nicht adjazenten Knoten $u,v$.

$d_H(x)$ meint hierbei den Grad des Knotens $x$ in $H$ -> also dem Abschluss, einem Obergraph.

Satz (7) | Bondy-Chávtal

[!Definition]

Ein einfacher Graph $G$ ist genau dann hamiltonsch, wenn sein Abschluss $h(G)$ ebenfalls hamiltonsch ist.

Was heißt das, wie was wäre ein Ansatz das zu beweisen? #card

–> weil wir auch hier die Eigenschaft von Satz (6) erweitern eines hamiltonsch’en Graphen betrachten können und zeigen, dass der neue Obergraph - mit mehr Kanten/Knoten - hamiltonsch ist und daher dann auch G sein muss

Satz (8) | Ore-Dirac

[!Definition]

Sei $G=(V,E)$ ein einfacher Graph mit $\mid V\mid \ge 3$

Wann gilt hier, dass der Graph dann hamiltonsch ist? #card

Wenn jetzt $deg(u)+deg(v)\ge |V\mid$ für jedes Paar von nicht adjazenten Knotenpaaren gilt, dann ist $G$ hamiltonsch.

[!Attention] vereinfachte Bedingung bei betrachtbaren Graden: Das trifft insbesondere zu, wenn $d(u)\ge \frac{|V\mid }{2}\forall u\in V$ –> Das kommt daher, dass dann die Summe nach Satz (6) erweitern eines hamiltonsch’en Graphen dann evaluieren kann und weiß, dass eine neue Verbindung auch aussagt, dass die alte Verbindung

Beweis | Satz (8) Ore-Dirac

Betrachten wir einen Beweis durch Widerspruch, um entsprechend lösen / zeigen zu können, dass dieser Satz gilt.

Wir möchten hierbei einen Graphen konstruieren, der aus allen Gegenbeispielen - die möglich sind - die meisten Kanten bei $n$ Knoten aufweist.

Hierbei muss gelten, dass das Beispiel in dem Falle nicht hamiltonsch ist ( also wir nehmen an, dass unter den maximalen Kanten die obig genannte Eigenschaft gilt, er jedoch nicht hamiltonsch ist). Ferner nehmen wir jetzt zwei nicht adjazente Knoten ( nicht benachbart) $u,v$. Fügen wir jetzt die Kante zwischen diesen beiden Knoten ein, dann folgt daraus: (Unter Betrachtung von Satz 6!) $⟹G\cup \{uv\}$ ist hamiltonsch, da jetzt $deg(v)+deg(u)\ge |V\mid$ und unter Betrachtung von Satz (6) erweitern eines hamiltonsch’en Graphen auch hamiltonsch ist ( auch ohne diese extra Kante).

[!Important] vollständiger Graph Wichtig hierbei: Der vollständige Graph $K_n$ - Graph mit $n$ Knoten, mit allen möglichen Kanten - ist ebenso hamiltonsch