Graph-Anwendungsaufgabe |
| 05.02.2007, 19:35 | nicki001 | Auf diesen Beitrag antworten » | ||
| Graph-Anwendungsaufgabe ich hab eine aufgabe, wo ich nicht wirklich ein ansatz finde. Champion gesucht: Ein Turnier auf n Knoten ist ein gerichteter Graph, der dadurch entsteht, dass man den ungerichteten Kanten des vollständigen Graphen Kn Richtungen zuweist. Die Richtung v -> w wird interpretiert als Spieler v schlägt Spieler w. Außerdem dominiert v den Spieler w, falls er ihn schlägt oder es einen Spieler z gibt, so dass v -> z und z -> w Kanten im Turnier sind. Ein Spieler heißt Champion, falls er jeden anderen Spieler dominiert. Beweisen Sie, dass jedes Turnier mit n>=1 Spielern wenigstens einen Champion hat. Ich weiss zwar wie es gemeint ist, aber ich weiss nicht wirklich wie ich vorgehen soll. |
||||
| 06.02.2007, 10:45 | Divergenz | Auf diesen Beitrag antworten » | ||
| RE: Graph-Anwendungsaufgabe Hallo, versuch halt zu zeigen, dass der Graph ein Baum ist, also (zusammenhangend ist und) keine Zyklen enthält. Dann ist die Wurzel des Baumes der Champion und immer eindeutig! |
||||
| 06.02.2007, 11:14 | Abakus | Auf diesen Beitrag antworten » | ||
RE: Graph-Anwendungsaufgabe
Schon, bloß "Turniergraphen" - wie hier betrachtet - können auch Zyklen enthalten. Das ist bereits bei 3 Knoten so: 1 -> 2 -> 3 -> 1. Hier wäre dann jeder Knoten ein Champion. Bei mehr als 3 Knoten ist die Situation allerdings komplexer. Die Aufgabe lohnt sich, um länger drüber zu grübeln. Daher nur ein kleiner Tipp: guck dir doch mal einen Champion-Kandidaten aus, der besonders vielversprechend aussieht und versuche dann zu zeigen, dass dieser Kandidat wirklich bereits Champion sein muss. Grüße Abakus 
|
||||
| 06.02.2007, 11:34 | Divergenz | Auf diesen Beitrag antworten » | ||
| RE: Graph-Anwendungsaufgabe Ok, wenn das so gemeint ist, dann geht es natürlich nicht so direkt. Dennoch halte ich die Idee nicht für unbrauchbar. Man muss nur alle Zyklen finden, jeweils eine Kante entfernen, sich aber den Zyklus merken, da die Knoten ja sozusagen alle gleichwertig sind. Ist das geschafft, müsste meine Methode doch aber funktionieren! Wenn ich alle Champions haben will muss ich natürlich am Ende noch vergleichen, ob mein ermittelter Bestandteil eines Zyklusses war. Falls ja, sind alle Knoten dieses Zyklusses Champions. |
||||
| 06.02.2007, 14:24 | Abakus | Auf diesen Beitrag antworten » | ||
RE: Graph-Anwendungsaufgabe
Fraglich ist zunächst, ob es überhaupt Zyklen gibt. Wenn du aber Zyklen gefunden hast - etwa fünf 7-Zykel und ggf. einige weitere in einem Turniergraph mit zB 340 Knoten, wo ist dann der Champion bzw. wie kriegst du den ? Wenn du dir gleich einen vielversprechenden Kandidaten als Champion ausguckst (zB anhand des Ausgangsgrads), brauchst du nur noch zu zeigen, dass es tatsächlich einer ist. Grüße Abakus
|
||||
| 07.02.2007, 19:06 | Tobias | Auf diesen Beitrag antworten » | ||
Also der prädestinierte Kandidat ist das Spieler x, der gegen die meisten Spieler direkt gewonnen hat. Diese fassen wir in D zusammen. Jetzt zeigen wir, dass er die anderen Spieler, die er nicht direkt geschlagen hat (sei diese Menge R) dominiert: Dominiert x einen Spieler y aus R nicht, so gibt es keinen Spieler z aus D, der gegen y direkt gewonnen hätte. Da aber auch x gegen y nicht direkt gewonnen hat (weil y ja aus R kommt) muss zwangsläufig y gegen x gewonnen haben. Somit hat aber y mehr direkte Siege auf dem Buckel. Was ein Widerspruch zur Voraussetzung ist. |
||||
| Anzeige | ||||
|
|
||||
| 07.02.2007, 19:38 | Abakus | Auf diesen Beitrag antworten » | ||
Genau das ist die Argumentation 
Grüße Abakus
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
