Zum Inhalt springen

KO-System/8/Freier Graph/Spielgraph/Quotientengraph/Aufgabe

Aus Wikiversity

Wir sind mitten in der WM, das Viertelfinale steht fest und beginnt morgen. Die Zeitung druckt den folgenden Restspielplan (ohne Spiel um Platz 3) ab.

Viertelfinale

 VF1 : Arg _− Deu _
 VF2 : Usb _− Bra _
 VF3 : Eng _− Kapv _
 VF4 : Fra _− Cur _

Halbfinale

 HF1 : Sieger VF1 _− Sieger VF2 _
 HF2 : Sieger VF3 _− Sieger VF4 _

Finale

 Finale : Sieger HF1 _− Sieger HF2 _

Wir interpretieren die Begegnungsstriche − als Kanten in einem Graphen G.

  1. Was ist die Knotenmenge in G? Skizziere den Graphen allein mit Punkten und Kanten (ohne jede Bennenung)!
  2. Was sind die Zusammenhangskomponenten von G? Ist der Graph bipartit?
  3. Einige Tage später steht das Finale an. Der Spielplan wurde zwischenzeitlich ergänzt, die unteren Zeilen sehen jetzt so aus (die oberen Zeilen aus dem Viertefinale sind unverändert da).


    Halbfinale

     HF1 : Sieger VF1  Deu _− Sieger VF2  Usb _
     HF2 : Sieger VF3  Kapv _− Sieger VF4  Cur _

    Finale

     Finale : Sieger HF1  Deu _− Sieger HF2  Cur _

    Hat sich der Graph G verändert?

  4. Es sei nun ∼ die Äquivalenzrelation auf G, bei der Knotenpunkte zueinander äquivalent sind, wenn sie durch die gleiche Mannschaft besetzt sind. Skizziere den Quotientengraphen  H=G/∼  überschneidungsfrei!
  5. Ist der Graph H zusammenhängend? Ist er bipartit?
  6. Bestimme die Automorphismengruppe von H!