Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 85, §19
№130. В некотором графе 6 вершин, степени которых равны:
а) 2, 2, 3, 3, 4, 4;
б) 0, 1, 2, 2, 3, 4.
Сколько всего рёбер в этом графе?
Дано:
6 вершин; степени: а) 2, 2, 3, 3, 4, 4; б) 0, 1, 2, 2, 3, 4
Найти:
число рёбер в графе
Воспользуемся теоремой о сумме степеней вершин: сумма степеней всех вершин графа вдвое больше числа рёбер (п. 19, №129). Значит, число рёбер равно половине суммы степеней.
а) Сумма степеней . Число рёбер равно .
б) Сумма степеней . Число рёбер равно .
Проверим, что такие графы вообще существуют. Примеры (в скобках у вершины записана её степень):
В графе а) рёбра АБ, АВ, БВ, АГ, БГ, ВГ, АД, ДЕ и ЕБ — их девять. В графе б) рёбра АБ, АВ, АГ, АД, БВ и БГ — их шесть; вершина Е не соединена ни с кем (степень 0).
Ответ: а) 9; б) 6.
