Графи: домінівні множини
Розмісти станції так, щоб кожна точка карти була охоплена, і знайди найменшу кількість станцій: число домінування графа.
- Росія: 7 клас
- Франція: 12 клас
- Іран: 12 клас
Поради для дорослих
В українській програмі цієї теми немає, але вона спирається на графи як моделі зв'язків (вершини й ребра) та на задачі на найменшу кількість об'єктів. Уяви, що банкомати ставлять на деяких перехрестях міста. На кожному перехресті має бути банкомат або він має бути за одну вулицю від нього. Це моделюємо графом: перехрестя — вершини, вулиці — ребра. Вершина з множини охоплює саму себе та своїх сусідів.
Множина вершин домінівна (домінувальна), якщо кожна вершина графа або належить цій множині, або сусідня з вершиною цієї множини. Найменша кількість вершин домінівної множини — число домінування, його позначають γ(G); домінівну множину такого розміру називають найменшою домінівною множиною.
Мінімальна й найменша множини — різні поняття. Мінімальна множина перестає домінувати, якщо вилучити з неї будь-яку одну вершину; найменша має якнайменше вершин. Кожна вершина охоплює щонайбільше Δ + 1 вершин (Δ — найбільший степінь вершини), тому для n вершин потрібно щонайменше n, поділене на Δ + 1, округлене вгору.