6 Нарисуйте граф к задаче и ответьте на вопрос:

Решение задачи:

1. Анализ условия:

• Всего 6 станций.
• Две станции соединены путями ровно с двумя другими станциями (степень вершины = 2).
• Остальные четыре станции соединены с тремя другими станциями (степень вершины = 3).
• Сеть связная.

2. Построение графа:

Пусть станции с двумя путями будут A и B. Пусть станции с тремя путями будут C, D, E, F.

Возможный граф:

Станции A и B соединены друг с другом (1 путь). Затем каждая из них соединена с двумя станциями из {C, D, E, F}.

Пример соединения:

• A соединена с B, C, D. (степень A = 3, но по условию должно быть 2. Значит, A и B — это как раз те станции с 2 путями, которые соединены с другими).
• A соединена с C и D.
• B соединена с E и F.
• Станции C, D, E, F должны быть соединены с тремя другими.

Попробуем иначе:

• Станции 1 и 2 имеют степень 2.
• Станции 3, 4, 5, 6 имеют степень 3.
• Граф связный.

Пример графа:

• 1 -- 3, 1 -- 4
• 2 -- 5, 2 -- 6
• 3 -- 5, 3 -- 1 (уже есть), 3 -- 6
• 4 -- 6, 4 -- 1 (уже есть), 4 -- 5
• 5 -- 3 (уже есть), 5 -- 2 (уже есть), 5 -- 4 (уже есть)
• 6 -- 4 (уже есть), 6 -- 2 (уже есть), 6 -- 3 (уже есть)

Давайте перечислим ребра:

(1,3), (1,4) — степень 1 = 2

(2,5), (2,6) — степень 2 = 2

(3,1), (3,5), (3,6) — степень 3 = 3

(4,1), (4,5), (4,6) — степень 4 = 3

(5,2), (5,3), (5,4) — степень 5 = 3

(6,2), (6,3), (6,4) — степень 6 = 3

Все условия соблюдены.

3. Ответ на вопрос: Можно ли составить расписание так, чтобы поезд прошёл по каждому пути ровно один раз, начав и закончив на одной и той же станции?

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

В нашем случае вершины 3, 4, 5, 6 имеют степень 3 (нечётную).

Следовательно, Эйлерова цикла в данном графе не существует.

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