Графы здесь служат двум задачам: надёжности сетей и анализу игр. Игру представляют графом позиций и размечают его с конца, и тогда выигрышная стратегия видна без перебора партий.
Что нужно знать
- В дереве с n вершинами n − 1 ребро: при 12 вершинах — 11.
- Сумма степеней вершин вдвое больше числа рёбер: 18 — это 9 рёбер.
- Мост — ребро, при удалении которого граф распадается; точка сочленения — такая же вершина. В сети это единая точка отказа.
- Обход в ширину сначала посещает всех соседей; в графе с одинаковыми рёбрами он находит кратчайший путь.
- Для графа с множеством вершин и малым числом рёбер удобнее списки смежности, а не матрица.
- Каркас минимального веса жадно: рёбра по возрастанию веса, берут ребро, если оно не образует цикла.
- Позиция проигрышная, если любой ход ведёт в выигрышную для соперника; выигрышная — если есть ход в проигрышную.
- Инвариант стратегии — свойство позиции, которое игрок сохраняет после каждого своего хода.
Где чаще всего ошибаются
- Считают в дереве столько же рёбер, сколько вершин.
- Приравнивают число рёбер сумме степеней.
- Размечают позиции от начала игры.
- Ищут кратчайший путь обходом в глубину.
Проверить себя
По этой же главе есть проверочная работа из 11 заданий на 25 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Информатика · 11 класс · Гейн, 2023 · Глава 11 · Графы, деревья и выигрышные стратегии