Задание 3. Постройте граф: вершины P, Q, R, S, T. Ребра: Р-Q, P-R, Q-S, R-S, S-T. Сколько существует различных путей из Р в Т, не проходящих дважды через одну вершину?

Решение:

Сначала построим граф согласно условию. Затем найдем все возможные пути из вершины P в вершину T, соблюдая условие, что каждая вершина в пути может быть посещена только один раз.

1. Построение графа:
   Вершины: P, Q, R, S, T.
   Ребра: (P, Q), (P, R), (Q, S), (R, S), (S, T).
2. Поиск путей из P в T:
   
   • Путь 1: P → Q → S → T
   • Путь 2: P → R → S → T
3. Проверка условия:
   В каждом из найденных путей вершины не повторяются.

Ответ: 2