Dies ist eine alte Version des Dokuments!
Eisverkäufer
In einem heißen Sommer möchte ein Eisproduzent in einer Stadt eine perfekte Versorgung der Bevölkerung mit Eis sicherstellen (natürlich, um möglichst viel zu verdienen) und stellt dazu Eisstände auf. Kein Bürger und keine Bürgerin der Stadt soll zu weit laufen müssen. Daher muss an jeder Straßenecke entweder ein Eisstand stehen oder - wenn es keinen Eisstand gibt - an mindestens einer der benachbarten Straßenkreuzungen ein Eisstand zu finden sein.
(A1)
Finde für die oben abgebildete Stadt geeignete Standorte für die Eisstände, so dass möglichst wenige Eisstände benötigt werden, da das der Firma Kosten spart. Anmerkung: Auch die Straße um alle Häuser außen herum zählt als Straße und damit die äußeren Ecken als Kreuzungen.
Fachbegriff: Dominierende Menge
- Gegeben ist ein Graph
G - Gesucht ist eine Teilmenge der Knoten - die dominierende Menge - , so dass jeder Knoten, der nicht in der dominierenden Menge ist, mindestens einen Nachbarknoten aus der dominierenden Menge hat.
Zu diesem Problem gibt es zwei Fragestellungen:
- Existenz: Gibt es eine dominierende Menge mit weniger als Knoten, als der Graph hat?
- Optimale Lösung: Finde eine dominierende Menge mit möglichst wenigen Knoten.