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.

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.

• Hier kannst du die Eisstände direkt im Browser platzieren

Gegeben ist ein Graph. Gesucht ist eine Teilmenge der Knoten (= dominierende Menge), so dass jeder Knoten, der nicht in der dominierende Menge ist, mindestens einen Nachbarknoten aus der dominierenden Menge hat. Existenz: Gibt es eine dominierende Menge mit weniger als k Knoten? Optimale Lösung: Finde eine dominierende Menge mit möglichst wenigen Knoten.