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