Transitives Turnier < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) überfällig | Datum: | 06:08 So 13.06.2010 | Autor: | itse |
Aufgabe | [Dateianhang nicht öffentlich]
Man ergänze den Graphen zu einem transitiven Turnier und geben den hamiltonschen Pfad an. |
Guten Morgen,
bei einem Turnier gilt ja, das der zugrundeliegende Graph vollständig sein muss und bei einem transitiven Turnier gilt noch, wenn Ecke [mm] (e_1 [/mm] und [mm] e_2) [/mm] -> [mm] (e_2 [/mm] und [mm] e_3), [/mm] dann muss auch eine Linie von [mm] e_1 [/mm] nach [mm] e_3 [/mm] führen.
Bei einem transitiven Turnier gilt außerdem, das es nur einen hamiltonsche Pfad gibt, also ein Pfad der alle Ecken genau einmal enthält.
Ich habe nun probiert es auf dem Graphen zuerst einen vollständigen Graphen zu machen, jede Ecke ist direkt über eine Kante mit allen anderen Ecken verbunden. Im Anschluss in rot habe ich die Transitivität eingezeichnet.
[Dateianhang nicht öffentlich]
Jedoch kann dies nicht stimmen, es gibt noch immer mehrere hamiltonsche Pfade. Ich kann doch außerdem nicht einfach den Graphen zu einem vollständigen ergänzen und die Richtungen der Kanten selbst bestimmen?
Ansonsten verstehe ich nicht, wie ich aus dem Graphen ein transitives Turnier mache, da keine Ecke mit mehr als einer anderen Ecke verbunden ist, somit kann ich doch keine weiteren Kanten einzeichnen um Transitivität herzustellen?
Vielen Dank
itse
Dateianhänge: Anhang Nr. 1 (Typ: png) [nicht öffentlich] Anhang Nr. 2 (Typ: png) [nicht öffentlich]
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 19:00 So 13.06.2010 | Autor: | itse |
Hat jemand eine Idee?
Gruß
itse
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 06:20 Di 15.06.2010 | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|