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

Граф с заданными вершинами и рёбрами:

Из P можно перейти в Q или R. Далее оба пути ведут через S, а затем в T. Получаем пути без повторного прохождения через вершину: P–Q–S–T и P–R–S–T.

Ответ: 2 пути.