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

Question

Вопрос:

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

Фотография

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

Accepted Answer

**Ответ: а) 9 рёбер; б) 6 рёбер.** В теории графов существует «Лемма о рукопожатиях», которая гласит: сумма степеней всех вершин графа равна удвоенному количеству его рёбер ($2E = \sum deg(v)$). Чтобы найти количество рёбер, нужно сложить степени всех вершин и разделить полученную сумму на 2. а) Сумма степеней: $2 + 2 + 3 + 3 + 4 + 4 = 18$. Количество рёбер: $18 : 2 = 9$. б) Сумма степеней: $0 + 1 + 2 + 2 + 3 + 4 = 12$. Количество рёбер: $12 : 2 = 6$.

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

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

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