Графы: доминирующие множества

В российской программе этой темы нет, но она опирается на графы как модели связей (вершины и рёбра; «Введение в теорию графов», 7–8 классы, и «Графы: связность, циклы, степень вершины, деревья», 10 класс) и на задачи о наименьшем числе объектов. Представь, что банкоматы ставят на некоторых перекрёстках города. На каждом перекрёстке должен быть банкомат или он должен быть в одной улице от него. Это моделируем графом: перекрёстки — вершины, улицы — рёбра. Вершина из множества охватывает саму себя и своих соседей.

Множество вершин доминирующее, если каждая вершина графа либо принадлежит этому множеству, либо соседняя с вершиной этого множества. Наименьшее число вершин доминирующего множества — число доминирования, его обозначают γ(G); доминирующее множество такого размера называют наименьшим доминирующим множеством.

Минимальное и наименьшее множества — разные понятия. Минимальное множество перестаёт доминировать, если убрать из него любую одну вершину; наименьшее содержит как можно меньше вершин. Каждая вершина охватывает не более Δ + 1 вершин (Δ — наибольшая степень вершины), поэтому для n вершин нужно не меньше n, делённого на Δ + 1, с округлением вверх.