В деревне 9 домов. Соседними будем считать участки, у которых есть общий забор. Известно, что у Петра соседи Иван и Антон, Максим сосед Ивану и Сергею, Виктор — Дмитрию и Никите, а также по соседству живут Евгений с Никитой, Иван с Сергеем, Евгений с Дмитрием и Сергей с Антоном, и больше соседей в деревне нет. Может ли Пётр, перелезая через заборы соседних участков, пробраться на участок к Никите?
Представим каждый участок вершиной графа, а общий забор двух участков — ребром. На схеме первые буквы обозначают жителей:
Из перечисления соседей получаем первую группу: Пётр связан с Иваном и Антоном; Иван — ещё с Максимом и Сергеем; Максим — с Сергеем; Сергей — с Антоном. Значит, из участка Петра можно переходить только между участками Петра, Ивана, Антона, Максима и Сергея.
Вторая группа состоит из Виктора, Дмитрия, Никиты и Евгения: Виктор сосед Дмитрию и Никите, а Евгений — Дмитрию и Никите. По условию других соседей нет, поэтому ребра между первой и второй группами не существует.
Граф соседства несвязен. Никита находится во второй группе, а Пётр — в первой. Пути между ними нет.
Нет, участок Никиты недостижим из участка Петра.
