2. Граф с вершинами А, В, С, D, Е задан списком рёбер: (A,B), (A,C), (B,D), (C,D), (D,E), (E,A). Нарисуйте граф (схематично). Найдите степень каждой вершины. Сколько всего ребер в графе? Есть ли в графе циклы? Если да, приведите один пример.

Решение:

1. Схематичное изображение графа:

Вершины: A, B, C, D, E

Рёбра: (A,B), (A,C), (B,D), (C,D), (D,E), (E,A)

2. Степень каждой вершины:

Степень вершины — это количество рёбер, которые её касаются.

• Степень вершины A: 2 (рёбра (A,B) и (A,C))
• Степень вершины B: 2 (рёбра (A,B) и (B,D))
• Степень вершины C: 2 (рёбра (A,C) и (C,D))
• Степень вершины D: 3 (рёбра (B,D), (C,D) и (D,E))
• Степень вершины E: 2 (рёбра (D,E) и (E,A))

3. Общее количество рёбер:

Перечислим все рёбра: (A,B), (A,C), (B,D), (C,D), (D,E), (E,A). Всего 6 рёбер.

Проверка: сумма степеней вершин = 2 + 2 + 2 + 3 + 2 = 11. По теореме о сумме степеней, сумма степеней должна быть равна удвоенному числу рёбер (2 * 6 = 12). Произошла ошибка в подсчете или в условии. Давайте перепроверим рёбра.

Оригинальный список рёбер: (A,B), (A,C), (B,D), (C,D), (D,E), (E,A). Действительно, 6 рёбер.

Давайте ещё раз посчитаем степени:

• A: (A,B), (A,C), (E,A) - 3 ребра
• B: (A,B), (B,D) - 2 ребра
• C: (A,C), (C,D) - 2 ребра
• D: (B,D), (C,D), (D,E) - 3 ребра
• E: (D,E), (E,A) - 2 ребра

Сумма степеней: 3 + 2 + 2 + 3 + 2 = 12. Теперь всё сходится.

4. Есть ли в графе циклы?

Да, в графе есть циклы.

Примеры циклов:

• A → B → D → C → A
• A → B → D → E → A
• A → C → D → E → A

Ответ:

• Степени вершин: A - 3, B - 2, C - 2, D - 3, E - 2.
• Всего ребер: 6.
• Циклы есть. Примеры: A-B-D-E-A, A-C-D-E-A.