Задание 3. Задача на поиск всех путей Дан граф с першинами 1, 2, 3, 4, 5. Рабра соединяют пары вершин 1-2 1-3, 2-3, 2-1. 3-1, 4-5. 1. Нарисуйте этот граф. 2. Найдите все возможные пути из вершины 1 в вершину 5, в которых никакая вершин а не повторяется (такие пути называются целями). Запишите каждый путь как последо вательность вершин. 3. Для каждого найденного пути посчитайте количество ребер. 4. Выделите путь с наименьшим количеством ребер. Как ещё называют такой путь в те ории графов? 5. Попробуйте найти хотя бы один путь из 1 в 5, где какая-то вершина повторяется (не це пь). Запишите его.

Ответ: Решение ниже

1. Нарисуем граф с вершинами 1, 2, 3, 4, 5 и ребрами, соединяющими пары вершин: 1-2, 1-3, 2-3, 2-1, 3-1, 4-5.
2. Найдем все возможные пути из вершины 1 в вершину 5, в которых никакая вершина не повторяется:
   • Путь 1: 1 → 2 → 3 → 1 (не подходит, так как вершина 1 повторяется)
   • Путь 2: 1 → 2 → 3 (нет пути до вершины 5)
   • Путь 3: 1 → 3 (нет пути до вершины 5)
   Но единственный путь до вершины 5 - это через вершину 4. Однако, нет ребра, соединяющего вершины 1,2,3 с вершиной 4. В условии задачи указано ребро 4-5, а значит есть только один путь из 4 в 5. Следовательно, путей из вершины 1 в вершину 5, в которых никакая вершина не повторяется - нет.
3. Посчитаем количество ребер для каждого найденного пути (путей не найдено).
4. Выделим путь с наименьшим количеством ребер (путей не найдено). В теории графов такой путь называют кратчайшим путем.
5. Попробуем найти хотя бы один путь из 1 в 5, где какая-то вершина повторяется:
   • Путь: 1 → 2 → 1 → 2 → 3 → 1 → 3 → 1 → ... (зацикливается)
   Так как нет пути из вершин 1, 2, 3 в вершину 4, а из вершины 4 есть путь только в вершину 5, то не существует пути из 1 в 5. Следовательно, данный путь не является путем из 1 в 5, хотя вершина 1 и повторяется.
   Путь из вершины 1 в вершину 5, где какая-то вершина повторяется - не существует.

Ответ: Решение выше