В деревне \(\displaystyle 9\) домов. Известно, что у Петра соседи Иван и Антон, Максим – сосед Ивану и Сергею, Виктор – Диме и Никите, а также по соседству живут Евгений с Никитой, Иван с Сергеем, Евгений с Димой, Сергей с Антоном. Больше соседей в означенной деревне нет (соседними считаются дворы, у которых есть общий участок забора).
Может ли Пётр огородами пробраться к Никите за яблоками?
По условию имеем:
- \(\displaystyle 9\) домов с хозяевами: Пётр, Иван, Антон, Максим, Сергей, Виктор, Дима, Никита, Евгений.
- между некоторым домами есть общий забор (тогда дома считаются соседними).
Требуется определить, может ли Пётр огородами пробраться к Никите за яблоками?
Чтобы ответить на вопрос, изобразим все дома и общие заборы между ними в виде графа:
- вершины графа – дома (обозначим их первыми буквами имён хозяев);
- рёбра – общие заборы (если у домов есть общий забор, связываем их ребром).
По возможности стараемся изображать рёбра так, чтобы они не пересекались.
Будем рисовать граф, постепенно анализируя условие задачи:
1. Известно, что у Петра соседи Иван и Антон.
Изобразим вершины \(\displaystyle П{\small,}\,И{\small,}\,А\) и рёбра \(\displaystyle П-И{\small,}\,П-А{\small:}\)
2. Максим – сосед Ивану и Сергею.
Добавим на рисунок вершины \(\displaystyle М\) и \(\displaystyle С{\small.}\) Нарисуем рёбра \(\displaystyle М - И\) и \(\displaystyle М - С{\small:}\)
3. Виктор – сосед Диме и Никите.
Добавляем вершины \(\displaystyle В{\small,}\,Д{\small,}\,Н\) и рёбра \(\displaystyle В-Д{\small,}\,В-Н{\small:}\)
4. Также по соседству живут Евгений с Никитой, Иван с Сергеем.
Добавим вершину \(\displaystyle Е\) и два ребра: \(\displaystyle Е - Н\) и \(\displaystyle И - С{\small:}\)
5. Соседи Евгений с Димой, Сергей с Антоном.
Изобразим рёбра \(\displaystyle Е - Д\) и \(\displaystyle С - А{\small:}\)
Видим, что построенный граф несвязный, он "распался" на две части. Вершина \(\displaystyle П\) находится в одной части, а вершина \(\displaystyle Н\) – в другой.
Рёбер (общих заборов) между частями графа нет, поэтому Пётр не сможет огородами пробраться к Никите за яблоками.
Ответ: нет.