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

Question

Вопрос:

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

Фотография

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

Accepted Answer

**Ответ: 18** Решение: В теории графов существует «Лемма о рукопожатиях», согласно которой сумма степеней всех вершин графа равна удвоенному числу его рёбер ($2E = \sum \deg(v)$). 1. Найдём сумму степеней всех вершин: $10 + 15 + 6 + 2 + 3 = 36$ 2. Так как каждое ребро соединяет две вершины, оно учитывается дважды в этой сумме. Разделим полученную сумму на 2: $36 : 2 = 18$ Следовательно, в графе 18 рёбер.

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

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

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