Graphen: dominierende Mengen
Platziere Stationen so, dass jeder Punkt der Karte abgedeckt ist, und finde die kleinste Anzahl, die genügt: die Dominierungszahl des Graphen.
📖 Hier beginnen: Lies die Schritte der „Lektion“ der Reihe nach (1, 2, 3 …) und beantworte jede Frage. Danach geht es mit „Üben“ weiter.
- Frankreich: Klasse 12
- Russland: Klasse 7
- Iran: Klasse 12
Hinweise für Erwachsene
Im bayerischen Mathematiklehrplan kommt dieses Thema nicht vor; Graphen begegnen den Schülerinnen und Schülern höchstens im Informatikunterricht. Die Aufgaben zeigen, wie man ein Alltagsproblem mit einem Graphen modelliert.
Angenommen, in einer Stadt sollen an einigen Kreuzungen Geldautomaten aufgestellt werden. An jeder Kreuzung muss entweder ein Automat stehen oder in einer Straße Entfernung ein Automat sein. Wir modellieren das mit einem Graphen: Kreuzungen sind Ecken, Straßen sind Kanten. Eine Ecke der Menge dominiert sich selbst und ihre Nachbarn.
Eine Menge von Ecken ist dominierend, wenn jede Ecke des Graphen in der Menge liegt oder neben einer Ecke der Menge. Die kleinste Anzahl von Ecken einer dominierenden Menge ist die Dominierungszahl, geschrieben γ(G); eine dominierende Menge dieser Größe heißt kleinste dominierende Menge.
„Minimal“ und „kleinstmöglich“ sind verschieden. Eine minimale Menge ist nicht mehr dominierend, sobald man irgendeine Ecke entfernt; eine kleinste Menge hat die geringstmögliche Anzahl von Ecken. Jede Ecke dominiert höchstens Δ + 1 Ecken (Δ ist der größte Grad), also braucht man für n Ecken mindestens n geteilt durch Δ + 1, aufgerundet.