KO-System/8/Freier Graph/Spielgraph/Quotientengraph/Aufgabe
Erscheinungsbild
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
Halbfinale
Finale
Wir interpretieren die Begegnungsstriche als Kanten in einem Graphen .
- Was ist die Knotenmenge in ? Skizziere den Graphen allein mit Punkten und Kanten (ohne jede Bennenung)!
- Was sind die Zusammenhangskomponenten von ? Ist der Graph bipartit?
- 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
Finale
Hat sich der Graph verändert?
- Es sei nun die Äquivalenzrelation auf , bei der Knotenpunkte zueinander äquivalent sind, wenn sie durch die gleiche Mannschaft besetzt sind. Skizziere den Quotientengraphen überschneidungsfrei!
- Ist der Graph zusammenhängend? Ist er bipartit?
- Bestimme die Automorphismengruppe von !