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

Решение:

Дан граф с вершинами K, L, M, N, P и рёбрами: K-L, L-M, M-N, N-P, P-K, K-M.

• Степень вершины: Количество рёбер, инцидентных вершине.
• Рёбра: Линии, соединяющие вершины.

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

• K: рёбра K-L, P-K, K-M. Степень K = 3
• L: рёбра K-L, L-M. Степень L = 2
• M: рёбра L-M, M-N, K-M. Степень M = 3
• N: рёбра M-N, N-P. Степень N = 2
• P: рёбра N-P, P-K. Степень P = 2

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

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

Проверка: Сумма степеней вершин = 3 + 2 + 3 + 2 + 2 = 12. По теореме о рукопожатиях, сумма степеней равна удвоенному числу рёбер, то есть 12 = 2 * 6. Всё верно.

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

Да, существует. Мы можем пройти из L в P, например, по следующему пути:

• L → M → N → P

Другой возможный путь:

• L → K → P

Финальный ответ:

Степень каждой вершины: K=3, L=2, M=3, N=2, P=2.

Всего рёбер: 6.

Путь из L в P существует. Пример пути: L → M → N → P