124 Нарисуйте какой-либо граф, в котором 5 вершин со степенями 1, 2, 2, 3, 3.

Фотография

Ответ ассистента

**Ответ: граф с 5 вершинами и 5 рёбрами.** Степень вершины — это количество рёбер, которые из неё выходят. Нам нужно, чтобы у пяти вершин были степени: $1, 2, 2, 3, 3$. **Проверка возможности построения:** Сумма степеней всех вершин: $1 + 2 + 2 + 3 + 3 = 11$. Согласно лемме о рукопожатиях, сумма степеней вершин графа всегда должна быть четной (она равна удвоенному числу рёбер: $\sum deg(v) = 2|E|$). Так как $11$ — нечётное число, такой граф **построить невозможно**. **Допущение:** Вероятно, в условии опечатка, и сумма должна быть чётной. Если бы степени были, например, $1, 2, 2, 3, 2$, то сумма была бы $10$, и граф существовал бы. Но для данных чисел $1, 2, 2, 3, 3$ решения в классической теории графов не существует.

Задать вопрос История вопросов

Другие решения

Что ещё задавали пользователи

124 Нарисуйте какой-либо граф, в котором 5 вершин со степенями 1, 2, 2, 3, 3.

Ответ ассистента

Похожие задачи

Другие решения