Graphentheorie < Algorithm. Geometrie < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:06 Mi 10.11.2010 | | Autor: | Astanda |
| Aufgabe | Ein Gärtner möchte Tulpen in vier verschiedenen Farben in einem Kreis anpflanzen. Dabei will er jede FArbe genau einmal neben jeder anderen Farbe pflanzen (zweimal dieselbe Farbe hintereinander ist ausgeschlossen). ER probiert stundenlang alle möglichen Kombinationen aus, aber kommt leider nicht zum Ziel.
a) Beweise, dass die Aufgabe mit vier Farben unlösbar ist.
b) Verallgmeinere das Problem auf n Farben. Für welches n (natürliche Zahl) ist das Problem lösbar? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
a) soll man angeblich mit Kombinatorik lösen können. hab aber keine idee!
b) also ich denke, dass das irgendwas mit hamiltonschen kreisen zu tun hat. der grad von allen meinen knote beträgt ja 3. d. h. es gibt keine euler tour... aber hat das was damit zu tun?
mhh verzweifel irgendwie völlig über dieser aufgabe. helft mir doch bitte!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:21 Mi 10.11.2010 | | Autor: | felixf |
Moin!
Tipp: es hat etwas mit Eulerkreisen und vollstaendigen Graphen zu tun.
LG Felix
|
|
|
| |
|
Hallo Astanda, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
zu a): für gerade n ist die Aufgabe nicht zu lösen. Die Farbe [mm] F_i [/mm] kommt im Kreis k-mal vor und hat also 2k Nachbarn. Es gibt aber n-1 "nötige" Nachbarschaften.
zu b): falls die Aufgabe für ungerade n generell lösbar wäre, müsste ein Algorithmus anzugeben sein.
Für n=3 ist der Kreis ABC eine Lösung, für n=5 ABCDEACEBD.
Allgemein muss der Kreis für 2m+1 Farben genau m*(2m+1) Blumen enthalten.
Interessant ist in der Tat, dass das Problem als Hamiltonkreisproblem zu definieren wäre, in dem die Knoten jede Farbkombination beinhalten.
Felix hat aber Recht, dass es sich auf ein Eulerkreisproblem reduzieren lässt, wobei jeder Knoten eine andere Farbe hat.
Ob das jetzt aber ein Schritt für die P=NP Frage ist, halte ich für fraglich. Da müsste man ja zeigen, dass jedes Hamiltonkreisproblem auch als Eulerkreisproblem darzustellen ist.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:28 Do 11.11.2010 | | Autor: | felixf |
Moin reverend,
> Felix hat aber Recht, dass es sich auf ein
> Eulerkreisproblem reduzieren lässt, wobei jeder Knoten
> eine andere Farbe hat.
> Ob das jetzt aber ein Schritt für die P=NP Frage ist,
> halte ich für fraglich. Da müsste man ja zeigen, dass
> jedes Hamiltonkreisproblem auch als Eulerkreisproblem
> darzustellen ist.
nun, man kann aus jedem Eulerkreis/-pfad einen Hamiltonkreis/-pfad machen, indem man den dualen Graphen betrachtet, sprich man vertauscht Ecken und Kanten. Ein Eulerkreis/-pfad im Graphen entspricht dann einem Hamiltonkreis/-pfad im dualen Graphen.
Umgekehrt geht das allerdings nicht, da man im dualen Graphen nicht notwendigerweise alle Ecken treffen muss (da ein Hamiltonkreis nicht alle Kanten benutzen muss).
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:49 Do 11.11.2010 | | Autor: | reverend |
Moin Felix,
> nun, man kann aus jedem Eulerkreis/-pfad einen
> Hamiltonkreis/-pfad machen, indem man den dualen Graphen
> betrachtet, sprich man vertauscht Ecken und Kanten. Ein
> Eulerkreis/-pfad im Graphen entspricht dann einem
> Hamiltonkreis/-pfad im dualen Graphen.
>
> Umgekehrt geht das allerdings nicht, da man im dualen
> Graphen nicht notwendigerweise alle Ecken treffen muss (da
> ein Hamiltonkreis nicht alle Kanten benutzen muss).
eben, eben...
Sonst wäre P=NP auch längst gelöst.
Grüße
reverend
|
|
|
|
