Урок 17. Степень вершины

Вероятность и статистика, 7 класс · Введение в теорию графов · ~45 минут

🎯 Что ты узнаешь

• Что такое степень вершины и как её сосчитать
• Почему сумма степеней всех вершин всегда равна удвоенному числу рёбер
• Почему вершин с нечётной степенью всегда чётное количество
• Как красиво решать задачи про рукопожатия с помощью этого знания

📖 Разбираемся в теме

Вернёмся к графу дружбы. У каждого человека есть какое-то число друзей: у кого-то трое, у кого-то один, а у кого-то ноль. В мире графов «число друзей» вершины называют красиво — степень вершины.

📌 Запомни: Степень вершины — это число рёбер, которые из неё выходят. Степень вершины А обозначают так: deg(А) (от английского degree — степень).

Сосчитаем степени на рисунке 1:

• deg(А) = 2 (рёбра к Б и В)
• deg(Б) = 3 (рёбра к А, В и Г)
• deg(В) = 2 (рёбра к А и Б)
• deg(Г) = 1 (ребро к Б)

💡 Лайфхак: Чтобы найти степень вершины, просто приложи палец к точке и сосчитай, сколько линий из-под пальца торчит. Не считай вершины-соседей — считай именно линии!

⏱ Попробуй сам: На рисунке 1 сложи все четыре степени: 2 + 3 + 2 + 1. Что получилось? Запомни число, оно нам сейчас пригодится.

Главная теорема: лемма о рукопожатиях

Ты только что сложил степени: 2 + 3 + 2 + 1 = 8. А теперь сосчитай рёбра на рисунке 1: А–Б, А–В, Б–В, Б–Г — это 4 ребра. Заметил? 8 — это ровно в два раза больше, чем 4.

Это не случайность!

📌 Запомни: Сумма степеней всех вершин = 2 × (число рёбер). Это правило называют леммой о рукопожатиях.

Почему так? Подумай про одно-единственное ребро. Оно соединяет две вершины, и каждой из них прибавляет по +1 к степени. То есть каждое ребро добавляет к общей сумме степеней ровно 2. Поэтому, сколько бы рёбер ни было, сумма степеней всегда вдвое больше их числа.

🤔 А знаешь ли ты? Название «лемма о рукопожатиях» придумали так: представь вечеринку, где люди жмут друг другу руки. Каждое рукопожатие — это «ребро» между двумя людьми. Если каждый посчитает, скольким он пожал руку (свою степень), и все сложат — получится ровно в два раза больше, чем было рукопожатий. Ведь в каждом рукопожатии участвуют двое!

Следствие: нечётных вершин — чётное число

Из леммы вытекает удивительный факт.

📌 Запомни: В любом графе число вершин с нечётной степенью всегда чётно (то есть их 0, 2, 4, 6...). Не может быть, например, ровно трёх вершин нечётной степени.

Почему? Сумма всех степеней равна 2 × (число рёбер) — а это всегда чётное число. Вершины с чётной степенью в сумму дают чётный вклад. Значит, и оставшиеся, нечётные, вершины тоже должны в сумме давать чётное число. А сумма нечётных чисел чётна, только если этих чисел чётное количество. Вот и весь секрет.

⚠️ Частая ошибка: Не путай «чётную степень» и «чётное число вершин». Речь идёт о том, что количество вершин-нечётностей чётно. Сами степени у них при этом нечётные (1, 3, 5...).

⏱ Попробуй сам: Может ли в компании быть так, что у каждого из 5 человек ровно 3 друга (внутри этой компании)? Подсказка: это значит 5 вершин степени 3 — а 5 нечётных вершин быть не может!

✍️ Разбор примеров

Пример 1. В графе на рисунке ниже найди степень каждой вершины и проверь лемму о рукопожатиях.

Решение. Рёбра: К–Л, К–Н, Л–М, Н–М, К–М. Считаем степени:

• deg(К) = 3 (Л, Н, М)
• deg(Л) = 2 (К, М)
• deg(М) = 3 (Л, Н, К)
• deg(Н) = 2 (К, М)

Сумма степеней: 3 + 2 + 3 + 2 = 10. Число рёбер: 5. Проверка: 2 × 5 = 10. ✓

Ответ: степени 3, 2, 3, 2; сумма 10 = 2 × 5 рёбер.

Пример 2. В графе 6 рёбер. Чему равна сумма степеней всех вершин?

Решение. По лемме: сумма степеней = 2 × число рёбер = 2 × 6 = 12.

Ответ: 12.

Пример 3. В графе сумма степеней вершин равна 14. Сколько в нём рёбер?

Решение. Сумма = 2 × рёбра, значит рёбра = 14 ÷ 2 = 7.

Ответ: 7 рёбер.

Пример 4. Может ли существовать граф со степенями вершин 1, 2, 2, 3?

Решение. Считаем число вершин нечётной степени: степень 1 (нечётная) и степень 3 (нечётная) — итого 2 вершины. Два — это чётное число, значит всё в порядке. Заодно проверим сумму: 1 + 2 + 2 + 3 = 8, делится на 2, рёбер было бы 4. Такой граф возможен.

Ответ: да, может (нечётных вершин 2 — чётное число).

Пример 5. Может ли быть граф со степенями вершин 1, 3, 3?

Решение. Вершины нечётной степени: 1, 3, 3 — все три нечётные. Значит, нечётных вершин 3, а это нечётное число. Такого быть не может!

Ответ: нет, не может (нечётных вершин получилось бы 3).

Пример 6. На встрече 7 человек, и кто-то предложил, чтобы каждый пожал руку ровно троим. Возможно ли это?

Решение. Это граф из 7 вершин, у каждой степень 3. Тогда нечётных вершин — все 7 штук, а 7 — нечётное число. Невозможно!

Ответ: нет, нельзя устроить так, чтобы каждый из 7 пожал руку ровно троим.

💡 Запомни главное

• Степень вершины — число рёбер, выходящих из неё (deg).
• Сумма степеней всех вершин = 2 × (число рёбер) — лемма о рукопожатиях.
• Каждое ребро добавляет к сумме степеней ровно 2.
• Число вершин нечётной степени всегда чётно (0, 2, 4, ...).
• Если степеней нечётное число «нечётных» — такого графа не существует.

📝 Домашнее задание

1. Найди степень каждой вершины на рисунке 2 ещё раз, не подглядывая в решение, и сложи их.
2. В графе 9 рёбер. Чему равна сумма степеней всех вершин?
3. Сумма степеней вершин графа равна 20. Сколько в нём рёбер?
4. Может ли существовать граф со степенями вершин 2, 2, 2, 2? Если да — нарисуй его.
5. Может ли существовать граф со степенями вершин 1, 1, 1? Объясни.
6. В классе 25 учеников. Может ли быть так, что у каждого ровно 5 друзей внутри класса? Объясни через нечётные вершины.
7. Нарисуй граф из 5 вершин, у которого степени 2, 2, 2, 2, 4. Проверь лемму о рукопожатиях.
8. ⭐ В графе 5 вершин. Известны степени четырёх из них: 1, 3, 2, 2. Чему может быть равна степень пятой вершины, если всего в графе 5 рёбер? Найди её двумя способами: через лемму о рукопожатиях и через правило о чётности нечётных вершин.