В теории графов сумма степеней всех вершин является важной характеристикой, связанной с фундаментальными свойствами графа. Рассмотрим ключевые аспекты этой величины.
Содержание
В теории графов сумма степеней всех вершин является важной характеристикой, связанной с фундаментальными свойствами графа. Рассмотрим ключевые аспекты этой величины.
Основное утверждение
Для любого графа (ориентированного или неориентированного) сумма степеней всех его вершин связана с количеством рёбер.
Для неориентированных графов
Лемма о рукопожатиях
В неориентированном графе сумма степеней всех вершин равна удвоенному количеству рёбер:
∑deg(v) = 2E
- deg(v) - степень вершины v
- E - количество рёбер в графе
Следствия
- Количество вершин с нечётной степенью всегда чётно
- Средняя степень вершины равна 2E/V, где V - число вершин
Для ориентированных графов
В ориентированном графе различают:
| Полустепень исхода | deg+(v) - число исходящих дуг |
| Полустепень захода | deg-(v) - число входящих дуг |
Сумма всех полустепеней исхода равна сумме всех полустепеней захода и равна количеству дуг:
∑deg+(v) = ∑deg-(v) = A
- A - количество дуг в графе
Примеры вычислений
| Тип графа | Сумма степеней |
| Полный граф Kn | n(n-1) |
| Цикл Cn | 2n |
| Дерево с n вершинами | 2(n-1) |
Применение
Знание суммы степеней вершин позволяет:
- Проверять корректность задания графа
- Доказывать существование определённых структур в графе
- Решать задачи на построение графов
- Анализировать сети и их свойства
Теоретические следствия
- В любом графе есть как минимум две вершины одинаковой степени
- Невозможно построить граф с нечётным числом вершин нечётной степени
- Последовательность натуральных чисел является графической тогда и только тогда, когда сумма элементов чётна
Таким образом, сумма степеней вершин графа - это фундаментальная характеристика, связывающая количество вершин и рёбер, имеющая важные теоретические и практические приложения.
