Путь по графу: нарисуй одним росчерком (8 вершин)
Алгебра, 8 класс · Головоломки: пути и графы
📚 Программа 8 класса · модуль «Практика: Головоломки: пути и графы» — тренажёр 2 из 3. За освоение тренажёра — +15 ★.
Правило и как решать
Одним росчерком обходят связный граф, у которого 0 или 2 нечётные вершины. Двигаясь, выбирай ребро, которое не «отрезает» оставшиеся рёбра от текущей вершины.
Подсказка: Отметь нечётные вершины и начни с одной из них.
Примеры с разбором
Пример 1
Ответ: путь по номерам вершин: 7 → 1 → 4 → 8 → 2 → 3 → 7 → 2 → 5 → 4 → 2 → 1 → 3 → 8 → 1
Решение: Одним росчерком можно обойти граф, если нечётных вершин (с нечётным числом рёбер) ноль или две. Начинай с нечётной вершины и не переходи по ребру-«мосту» раньше времени: после него нельзя будет вернуться к оставшимся рёбрам.
Пример 2
Ответ: путь по номерам вершин: 6 → 4 → 7 → 2 → 5 → 3 → 4 → 2 → 1 → 7 → 6 → 1 → 4 → 8 → 6
Решение: Одним росчерком можно обойти граф, если нечётных вершин (с нечётным числом рёбер) ноль или две. Начинай с нечётной вершины и не переходи по ребру-«мосту» раньше времени: после него нельзя будет вернуться к оставшимся рёбрам.