Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 88, §20
№138. В деревне 9 домов. Соседними будем считать участки, у которых есть общий забор. Известно, что у Петра соседи Иван и Антон, Максим сосед Ивану и Сергею, Виктор — Дмитрию и Никите, а также по соседству живут Евгений с Никитой, Иван с Сергеем, Евгений с Дмитрием и Сергей с Антоном и больше соседей в деревне нет. Может ли Пётр, перелезая через заборы соседних участков, пробраться на участок к Никите?
Дано:
9 домов; соседи по общему забору: Пётр—Иван, Пётр—Антон, Максим—Иван, Максим—Сергей, Виктор—Дмитрий, Виктор—Никита, Евгений—Никита, Иван—Сергей, Евгений—Дмитрий, Сергей—Антон
Найти:
может ли Пётр, перелезая через заборы соседних участков, попасть на участок к Никите
Составим граф соседств: каждый участок (дом) изобразим вершиной, а соседние участки (с общим забором) соединим ребром. Условие даёт 10 рёбер: Пётр—Иван, Пётр—Антон, Максим—Иван, Максим—Сергей, Виктор—Дмитрий, Виктор—Никита, Евгений—Никита, Иван—Сергей, Евгений—Дмитрий и Сергей—Антон.
Перелезать через заборы — значит идти по рёбрам графа. Выясним, до каких вершин можно дойти от Пётра. Из Пётра можно попасть к Ивану и Антону; от Ивана — к Максиму и Сергею; от Антона — к Сергею. Новых участков больше нет: Пётр, Иван, Антон, Максим и Сергей — это всё, куда можно добраться. Ни у одного из этих пяти участков нет общего забора с Виктором, Дмитрием, Евгением или Никитой.
Участки Виктора, Дмитрия, Евгения и Никиты образуют вторую часть графа: они граничат только друг с другом (Виктор—Дмитрий, Дмитрий—Евгений, Евгений—Никита, Никита—Виктор). Значит, граф соседств состоит из двух отдельных частей — он несвязный. От Пётра до Никиты по рёбрам пути нет (проверено перебором всех цепей).
Ответ: нет, Пётр не может пробраться на участок к Никите.
Ответ: Нет, граф соседств не связан: участки Пётра, Ивана, Антона, Максима и Сергея не граничат с участками Виктора, Дмитрия, Евгения и Никиты.
