У графа 5 вершин степени 4 и ещё 5 вершин степени 6. Других вершин в этом графе нет. Сколько рёбер в этом графе?
Показать решение
1. Всего вершин:
2. Найдём сумму степеней всех вершин. У каждой вершины степень равна числу рёбер, которые из неё выходят:
3. Каждое ребро соединяет ровно две вершины, поэтому оно учитывается в сумме степеней дважды — по разу у каждой концевой вершины.
Значит, сумма степеней в два раза больше числа рёбер:
4. Найдём число рёбер:
Ответ: 25.
Теория
1. Степень вершины
Степень вершины — это число рёбер, которые из неё выходят (или, в простом графе, число соседей).
2. Главное правило
Сумма степеней всех вершин графа равна удвоенному числу рёбер:
сумма степеней = 2 · (число рёбер)
Почему: каждое ребро имеет два конца, поэтому в общую сумму степеней вклад каждого ребра равен 2.
3. Алгоритм
а) Запиши, сколько вершин какой степени дано.
б) Посчитай сумму степеней: (число вершин) · (их степень) для каждой группы, затем сложи.
в) Раздели сумму на 2 — получишь число рёбер.
4. Пример
7 вершин степени 4 и 6 вершин степени 3.
Сумма степеней: 7 · 4 + 6 · 3 = 28 + 18 = 46.
Число рёбер: 46 : 2 = 23.
5. Проверка
Сумма степеней всегда должна получиться чётной. Если нечётная — где-то ошибка в расчёте.