Задание 6. Даша и её родители собираются поехать на машине из Самары к родственникам в Киров. Вершинами графа являются регионы Приволжского федерального округа, а ребро между вершинами построено, если соответствующие регионы являются соседними, то есть имеют участок сухопутной границы. 1 — Нижегородская область; 2 — Республика Мордовия; 3 — Чувашская Республика; 4 — Республика Марий Эл; 5 — Кировская область; 6 — Пензенская область; 7 — Ульяновская область; 8 — Республика Татарстан; 9 — Удмуртская Республика; 10 — Пермский край; 11 — Самарская область; 12 — Оренбургская область; 13 — Республика Башкортостан; 14 — Саратовская область. Найдите какой-нибудь простой путь из Самары в Киров через четыре региона (включая Самарскую и Кировскую области). Ответ дайте в виде последовательности соответствующих регионам чисел без разделителей. Сколько существует различных простых путей, соответствующих такому маршруту? Можно ли выехать из Самары, доехать до Кирова и вернуться обратно в Самарскую область так, чтобы побывать в каждом из остальных 13 регионов Приволжского федерального округа ровно один раз?

Шаг 1. Путь через четыре региона содержит три ребра. Начальная вершина — 11 (Самарская область), конечная — 5 (Кировская область).

Шаг 2. По графу получаем один подходящий путь: 11 → 7 → 8 → 5. Значит, требуемая запись — 11785.

Шаг 3. Переберём возможные пути длиной три по соседним вершинам: 11 → 7 → 8 → 5; 11 → 8 → 4 → 5; 11 → 8 → 9 → 5; 11 → 12 → 8 → 5. Других подходящих вариантов на графе нет.

Ответ: 11785; существует 4 различных простых пути.

Шаг 4. Для поездки туда и обратно достаточно проверить, можно ли пройти по графу циклом через все вершины ровно по одному разу, кроме начальной, которая повторяется в конце. Такой цикл существует: 11 → 14 → 2 → 6 → 7 → 3 → 1 → 4 → 5 → 10 → 9 → 13 → 12 → 8 → 11. Каждая вершина графа встречается в цикле ровно один раз, кроме 11, которая обозначает начало и возвращение.

Ответ: да.