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

Решение:

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

Представьте 5 точек (вершин), соединенных линиями (рёбрами) согласно списку.

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. Количество рёбер:

• В списке рёбер 6 пар, значит, в графе 6 рёбер.

4. Наличие циклов:

• Да, в графе есть циклы.
• Пример цикла 1: A-B-D-C-A (проходит через вершины A, B, D, C и возвращается в A).
• Пример цикла 2: A-E-D-C-A (проходит через вершины A, E, D, C и возвращается в A).
• Пример цикла 3: A-E-D-B-A (проходит через вершины A, E, D, B и возвращается в A).

Ответ:

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