В некотором графе 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

Для решения задачи используем теорему о сумме степеней вершин графа, которая гласит, что сумма степеней всех вершин графа равна удвоенному числу его рёбер. То есть, $\sum_{i=1}^{n} \text{deg}(v_i) = 2E$, где $E$ — число рёбер. a) Даны степени вершин: 2, 2, 3, 3, 4, 4. Сумма степеней: $2 + 2 + 3 + 3 + 4 + 4 = 18$. Число рёбер: $E = \frac{18}{2} = 9$. б) Даны степени вершин: 0, 1, 2, 2, 3, 4. Сумма степеней: $0 + 1 + 2 + 2 + 3 + 4 = 12$. Число рёбер: $E = \frac{12}{2} = 6$. **Ответ:** а) 9 рёбер б) 6 рёбер

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

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

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