Source code |
|
1 2 3 4 5 6 7 8 |
0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 0 |
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Den Graph aufmalen auf "scharf hingucken" (allzuviel Schärfe ist hier nicht erforderlich). Die von Dir genannten Bedingungen sind nur hinreichend für einen Hamiltonkreis. Das allgemeine Problem (also für beliebige Graphen festzustellen, ob dieses einen Hamiltonkreis besitzen) ist ja NP-vollständig, im großen und ganzen also wohl nur durch Durchprobieren aller möglichen Pfade zu lösen.
Source code
1 2 3 4 5 6 7 8 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 0
Angeblich existiert ein Hamiltonkreis. Aber woher weiß ich das ?
Ich schätze mal, dass die so gerechnet haben, dass die 4 Ehepaare auf 4 Tanzpaare verteilt haben. Und zwar (was ja beim Tanzkurs irgendwie gar keinen Sinn macht) mit Berücksichtigung der Startreihenfolge: Also 4! = 24.Weiß jemand noch den Lösungsweg für eine Aufgabe aus Blatt 2 ?
Vier Ehepaare nehmen an einem Tanzkurs teil. Bei wievielen der 24 verschiedenen
Tanzkonstellationen tanzt kein Ehepaar miteinander?
Lösung: 9 - aber wie ?
This post has been edited 2 times, last edit by "snoopy" (Jul 15th 2008, 12:37am)
Quoted from "Wikipedia"
Die Anzahl der möglichen Derangements einer Menge mit Elementen entspricht der Subfakultät :
.
This post has been edited 1 times, last edit by "Schokoholic" (Jul 15th 2008, 12:51am)