Museum Bewachen

Damit in deinem neuen Kunstmuseum keines deiner kostbaren Bilder angefasst wird, beschließt du, Überwachungsroboter zu kaufen. Ein Roboter kann einen Raum und all seine Nachbarräume überwachen. Ein Museumsraum ist somit überwacht, wenn ein Roboter darin platziert wird, oder sich ein Roboter in einem Nebenraum befindet.

Die Raumnachbarschaftsstruktur deines Museums hast du als Graph modelliert.

Wo solltest du Roboter platzieren, um mit so wenigen Robotern wie möglich, jeden Raum zu überwachen?