hamiltonsch? < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:29 So 18.01.2009 | | Autor: | MacMath |
| Aufgabe | Es sei G ein schlichter Graph.Weiter besitze G einen geschlossenen Kantenzug C, so dass
jede Kante, die nicht zu C gehört, mit einer Kante aus C inzidiert. Man zeige, dass L(G) Hamiltonsch ist. |
Gibts da einen bestimmten Satz bzw. einen Ansatz bei dem ich starten kann? Habe bisher keine Idee zum beginn eines beweises.
Gruß Daniel
|
|
| |
|
Hallo MacMath,
das wird ein recht einfacher Widerspruchsbeweis. Dazu brauchst Du allerdings ein Minimum an Aussagenlogik sowie die Definitionen aller verwendeten Begriffe.
Nimm an, es gebe eine Kante, die weder zu C gehört, noch mit einer Kante aus C inzidiert, und dass der Graph dennoch hamiltonsch ist. Was heißt das für die Knoten, die die betrachtete Kante verbindet? Warum kann der Graph dann nicht hamiltonsch sein? Fertig.
Du musst dafür definieren können:
- schlichter Graph
- Kante
- Knoten (hier nur implizit verwendet)
- inzidieren
- geschlossener Kantenzug
- hamiltonsch
lg,
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:41 Mo 19.01.2009 | | Autor: | MacMath |
Habe die Aufgabe nun doch lösen können, allerdings etwas anders (ich vermute es wird kürzer ;)
Ich betrachte einen Ausschnitt von G bestehend aus allen Kanten die zu einer Kante [mm] k_i \in [/mm] C inzident sind (sowie [mm] k_i [/mm] selbst, ausgenommen sind natürlich Kanten die schon vorher betrachtet wurden)
Betrachtet man den gleichen Ausschnitt in L(G) lässt sich leicht ein Hamiltonweg [mm] h_i [/mm] von [mm] k_{i} [/mm] nach [mm] k_{i+1} [/mm] bilden.
Diese Hamiltonwege ergeben "aneinandergehangen" den gesuchten Hamiltonkreis.
Gruß Daniel
|
|
|
|
![[]](/images/popup.gif){kind=small}
Hamiltonkreisproblem
Vielleicht könntest Du so auch noch P=NP nachweisen. Mindestens die Informatiker wären glücklich, und Dir ein hohes Preisgeld sicher.
