Задание 2. Граф с вершинами К, L, M, N, P задан ребрами: K-L, L-M, M-N, N-P, P-K, K-M. Найдите степень каждой вершины. Сколько всего рёбер? Существует ли путь из L в Р? Если да, запишите любой такой путь (последовательность вершин).

Решение:

Степень вершины: Количество рёбер, выходящих из данной вершины.

• Степень вершины K: 2 (рёбра K-L, K-M)
• Степень вершины L: 2 (рёбра K-L, L-M)
• Степень вершины M: 3 (рёбра L-M, M-N, K-M)
• Степень вершины N: 2 (рёбра M-N, N-P)
• Степень вершины P: 2 (рёбра N-P, P-K)

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

Перечислим все рёбра: K-L, L-M, M-N, N-P, P-K, K-M. Всего 6 рёбер.

Проверка: Сумма степеней вершин = 2+2+3+2+2 = 11. По теореме о сумме степеней, сумма степеней равна удвоенному числу рёбер. 11 не делится на 2. Давайте пересчитаем рёбра.

Исправленное решение:

Степень вершины:

• K: K-L, P-K, K-M (3)
• L: K-L, L-M (2)
• M: L-M, M-N, K-M (3)
• N: M-N, N-P (2)
• P: N-P, P-K (2)

Всего рёбер: K-L, L-M, M-N, N-P, P-K, K-M. Всего 6 рёбер.

Проверка: Сумма степеней = 3+2+3+2+2 = 12. 12 / 2 = 6 рёбер. Верно.

Существует ли путь из L в P?

Да, существует. Например, L -> M -> N -> P.

Ответ: Степени вершин: K-3, L-2, M-3, N-2, P-2. Всего 6 рёбер. Путь из L в P существует: L-M-N-P.