Hammiltonkreise < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | In unserem Skript steht:
Es sei n:=|V| ≥ 3 und G zusammenhängend. Falls für alle u,v [mm] \in [/mm] V mit
[mm] u\not=v [/mm] und uv [mm] \not\in [/mm] E gilt deg(u)+deg(v) [mm] \ge [/mm] n so besitzt G einen Hamiltonkreis. |
[Dateianhang nicht öffentlich]
Wenn man die Aussenkanten einmal umfährt ist man durch jeden Knoten gefahren, das ist doch ein Hammiltonkreis oder?
Nur stell ich mir die Frage wenn für alle u,v [mm] \in [/mm] V deg(u)+deg(v) [mm] \ge [/mm] n gelten soll wieso ein Hammiltonkreis existiert. Nimmt man sich nämlich den obersten (u) und untersten Knoten (v) dann käme die Ungleichung zustande [mm] 2+2\ge [/mm] 6
(nur da wo der Grad dran steht ist ein Knoten)
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
Hallo DrNetwork,
> In unserem Skript steht:
>
> Es sei n:=|V| ≥ 3 und G zusammenhängend. Falls für alle
> u,v [mm]\in[/mm] V mit
> [mm]u\not=v[/mm] und uv [mm]\not\in[/mm] E gilt deg(u)+deg(v) [mm]\ge[/mm] n so
> besitzt G einen Hamiltonkreis.
> [Dateianhang nicht öffentlich]
>
> Wenn man die Aussenkanten einmal umfährt ist man durch
> jeden Knoten gefahren, das ist doch ein Hammiltonkreis
> oder?
>
> Nur stell ich mir die Frage wenn für alle u,v [mm]\in[/mm] V
> deg(u)+deg(v) [mm]\ge[/mm] n gelten soll wieso ein Hammiltonkreis
> existiert. Nimmt man sich nämlich den obersten (u) und
> untersten Knoten (v) dann käme die Ungleichung zustande
> [mm]2+2\ge[/mm] 6
Nun, so, wie du den Satz oben hingeschrieben hast, ist doch die ganze Voraussetzung, also [mm] $\forall u,v\in [/mm] V, [mm] u\neq [/mm] v, [mm] (u,v)\in [/mm] E $ mit [mm] $d(u)+d(v)\ge [/mm] n$ lediglich eine hinreichende Bedingung dafür, dass $G$ eine Hamiltonkreis besitzt.
Keinesfalls ist sie notwendig.
Dh. Falls die Vor. erfüllt ist, enthält $G$ auf jeden Fall einen HK, $G$ kann aber auch unter anderen Umständen einen HK haben ...
Du kannst also aus der Nicht-Erfüllung der Voraussetzung nicht schließen, dass $G$ keinen HK hat.
Formal ist der Satz eine Aussage [mm] $p\Rightarrow [/mm] q$, die nur dann nicht gilt, wenn $p$ gilt und $q$ nicht.
Gilt $p$ nicht, so gilt die Aussage unabh. von q
Wenn also die Vor. $p$ nicht gilt, kann $G$ einen HK haben, muss es aber nicht, du kannst einfach nicht darauf schließen.
> (nur da wo der Grad dran steht ist ein Knoten)
Gruß
schachuzipus
|
|
|
|
