В некотором графе 5 вершин. а) Сколько всего рёбер в графе, степени вершин которого равны 1, 2, 3, 1, 3? б) Сколько всего рёбер в графе, степени вершин которого равны 4, 2, 1, 3, 4?

Question

Вопрос:

В некотором графе 5 вершин. а) Сколько всего рёбер в графе, степени вершин которого равны 1, 2, 3, 1, 3? б) Сколько всего рёбер в графе, степени вершин которого равны 4, 2, 1, 3, 4?

Фотография

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

Accepted Answer

**Ответ: а) 5; б) 7** Для решения таких задач используется **лемма о рукопожатиях**: сумма степеней всех вершин графа равна удвоенному количеству его рёбер ($2E$). Это происходит потому, что каждое ребро соединяет две вершины и добавляет по единице к степени каждой из них. а) Степени вершин: $1, 2, 3, 1, 3$. 1. Найдём сумму степеней: $1 + 2 + 3 + 1 + 3 = 10$. 2. Найдём количество рёбер: $10 / 2 = 5$. б) Степени вершин: $4, 2, 1, 3, 4$. 1. Найдём сумму степеней: $4 + 2 + 1 + 3 + 4 = 14$. 2. Найдём количество рёбер: $14 / 2 = 7$.

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

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