Лемма о рукопожатиях в графах

Лемма о рукопожатиях — одно из фундаментальных утверждений в теории графов, связывающее количество рёбер графа со степенями его вершин.

Формулировка леммы

Сумма степеней всех вершин графа равна удвоенному количеству рёбер:

∑ deg(v) = 2E

где deg(v) — степень вершины v, а E — количество рёбер в графе.

Происхождение названия

Название "лемма о рукопожатиях" происходит из популярной интерпретации: если на вечеринке каждый участник пожимает руку определённому количеству гостей, то общее количество рукопожатий будет равно половине суммы всех индивидуальных рукопожатий.

Эта лемма работает для любых графов, включая мультиграфы и псевдографы.

Доказательство леммы

  1. Каждое ребро графа соединяет две вершины
  2. Таким образом, каждое ребро увеличивает степень каждой из этих вершин на 1
  3. Следовательно, сумма всех степеней вершин равна удвоенному количеству рёбер

Пример доказательства

Рассмотрим простой граф с тремя вершинами A, B, C и рёбрами AB, BC, AC:

Сумма степеней: 2 + 2 + 2 = 6

Количество рёбер: 3

Удвоенное количество рёбер: 6

Следствия леммы

В любом графе количество вершин с нечётной степенью всегда чётно.

Это следствие имеет важное значение в теории графов:

Практическое применение

Лемма о рукопожатиях находит применение в различных областях:

  1. Сетевая топология: анализ компьютерных сетей
  2. Молекулярная химия: изучение структуры молекул
  3. Социология: анализ социальных связей
  4. Городское планирование: проектирование дорожных сетей

Сравнение с другими теоремами

ТеоремаСвязь с леммой
Теорема ЭйлераИспользует следствие о вершинах нечётной степени
Теорема ДиракаОпирается на свойства степеней вершин

Исторический контекст

Хотя точное авторство леммы неизвестно, её первые формулировки встречаются в работах Леонарда Эйлера в XVIII веке, когда он решал задачу о Кёнигсбергских мостах — проблему, считающуюся началом теории графов.

Лемма остается актуальной уже более двух столетий, демонстрируя глубину и универсальность математических истин.

Ограничения и исключения

Важно понимать, что лемма работает только для:

Для графов с петлями формулу нужно корректировать, так как петля увеличивает степень вершины на 2.

Программная реализация

Проверку леммы легко реализовать алгоритмически:

function checkHandshakeLemma(graph) {
  let sumDegrees = 0;
  for (let vertex of graph.vertices) {
    sumDegrees += vertex.degree;
  }
  return sumDegrees === 2 * graph.edges.length;
}

Заключение

Лемма о рукопожатиях — это элементарное, но мощное утверждение, которое:

#граф#математика#теория_графов