Задачи и упражнения ЗАДАНИЕ 1. (рис. 6). А) Перерисуйте себе в тетрадь и подпишите степени вершин. Б) Существует ли Эйлеров путь в этом графе? В) Приведите пример цикла в этом графе. Г) Какие рёбра можно удалить, чтобы циклов в нём не осталось, но граф остался связным? Д) Какова сумма степеней вершин в получившемся графе? ЗАДАНИЕ 2. (рис. 7). А) Существует ли Эйлеров путь в этом графе? Б) Добавьте минимальное число рёбер, чтобы такой путь появился.

ЗАДАНИЕ 1. (рис. 6)

А) Перерисуйте себе в тетрадь и подпишите степени вершин.

Степень вершины - это количество ребер, инцидентных этой вершине. На рисунке 6 имеем:

• A: 2
• B: 2
• C: 2
• D: 2
• E: 2

Б) Существует ли Эйлеров путь в этом графе?

Эйлеров путь существует, если в графе не более двух вершин с нечетной степенью. В данном графе все вершины имеют четную степень (2), поэтому Эйлеров путь существует.

В) Приведите пример цикла в этом графе.

Цикл - это путь, который начинается и заканчивается в одной и той же вершине. Пример цикла в графе на рисунке 6: A-E-D-C-B-A

Г) Какие рёбра можно удалить, чтобы циклов в нём не осталось, но граф остался связным?

Чтобы удалить циклы, нужно удалить ребра так, чтобы не осталось замкнутых путей, но при этом все вершины оставались связанными. Можно удалить одно из ребер квадрата, например, ребро DC. Тогда получим граф без циклов.

Д) Какова сумма степеней вершин в получившемся графе?

Если удалили ребро DC, то степень вершины D станет 1, степень вершины C станет 1, а степени остальных вершин не изменятся.

• A: 2
• B: 2
• C: 1
• D: 1
• E: 2

Сумма степеней вершин: 2 + 2 + 1 + 1 + 2 = 8

ЗАДАНИЕ 2. (рис. 7)

А) Существует ли Эйлеров путь в этом графе?

Чтобы в графе существовал Эйлеров путь, необходимо, чтобы не более двух вершин имели нечетную степень.

В графе на рисунке 7:

• A: 3
• B: 3
• C: 2
• D: 2
• E: 2
• F: 2

Так как в графе две вершины (A и B) имеют нечетную степень, то Эйлеров путь существует.

Б) Добавьте минимальное число рёбер, чтобы такой путь появился.

В данном вопросе, вероятно, имелось в виду, чтобы граф стал Эйлеровым циклом, а не Эйлеровым путем, поскольку вопрос "чтобы такой путь появился" не имеет смысла, так как Эйлеров путь уже есть.

Чтобы граф имел Эйлеров цикл, нужно, чтобы все вершины имели четную степень. Сейчас две вершины (A и B) имеют нечетную степень (3). Чтобы исправить это, нужно добавить ребро между A и B. Тогда степень каждой из этих вершин увеличится на 1, и они станут четными (4).

Ответ:

Задание 1:

A) Степени вершин: A: 2, B: 2, C: 2, D: 2, E: 2

Б) Эйлеров путь существует.

В) Пример цикла: A-E-D-C-B-A

Г) Удалить ребро DC.

Д) Сумма степеней вершин: 8

Задание 2:

А) Эйлеров путь существует.

Б) Добавить ребро между A и B.

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

Отлично! Ты хорошо справился с задачами по теории графов. Продолжай в том же духе, и у тебя всё получится!