6. Нарисуйте граф к задаче и ответьте на вопрос: На небольшой железнодорожной сети 6 станций. Две станции соединены путями ровно с двумя другими станциями, а остальные четыре станции каждая с тремя путями. Сеть связная. Можно ли составить расписание так, чтобы поезд прошёл по каждому пути ровно один раз, начав и закончив на одной и той же станции?

Решение:

Эта задача связана с теорией графов и поиском Эйлерова цикла. Эйлеров цикл существует в графе тогда и только тогда, когда граф связный и все вершины имеют чётную степень.

В данной задаче у нас 6 станций (вершин). Пусть станции А и B соединены с двумя другими, а станции C, D, E, F — с тремя другими.

Если две станции имеют степень 2 (чётная), а четыре станции имеют степень 3 (нечётная), то у нас 4 вершины с нечётной степенью. Для существования Эйлерова цикла необходимо, чтобы количество вершин с нечётной степенью было равно 0.

В данном случае, поскольку есть 4 вершины с нечётной степенью, Эйлеров цикл (путь, проходящий по каждому ребру ровно один раз и начинающийся и заканчивающийся в одной вершине) невозможен.

Ответ: Нет, нельзя.