Что такое степень вершины графа? Может ли степень вершины равняться 0?

Ниже приведены ответы на вопросы и решения задач из раздела теории графов: **Вопросы** 1. **Степень вершины** — это количество рёбер графа, которые выходят из этой вершины (инцидентны ей). 2. **Да**, может. Такая вершина называется изолированной. 3. **Теорема о сумме степеней вершин:** Сумма степеней всех вершин любого графа равна удвоенному количеству его рёбер. $ \sum_{i=1}^{n} deg(v_i) = 2|E| $ 4. **Нет**, не существует. Согласно «Лемме о рукопожатиях», количество вершин с нечётной степенью в любом графе должно быть чётным. Число 3 — нечётное, поэтому такой граф построить нельзя. **Задачи** 124. **Ответ: Нет.** Посчитаем сумму степеней: $5 \text{ вершин} \times 3 \text{ (степень)} = 15$. Сумма степеней всегда должна быть чётным числом (так как каждое ребро считается дважды). 15 — нечётное число, значит, такой граф невозможен. 125. Примеры двух неодинаковых графов (оба имеют 6 вершин со степенями 1, 1, 2, 2, 3, 3): - **Вариант 1 (связный):** Нарисуйте цепочку, где вершины соединяются последовательно, и добавьте одно ребро внутри так, чтобы степени распределились согласно условию. - **Вариант 2 (несвязный):** Разделите вершины на две отдельные группы (например, треугольник и цепочка) так, чтобы сумма степеней в каждой группе была чётной. 126. **Ответ: а) 0; в) 2; д) 4.** Количество вершин нечётной степени всегда должно быть чётным. Варианты б) 1 и г) 3 невозможны. 127. **Ответ: Нет.** Допустим, на конференции $n$ человек. Если у каждого ровно 3 знакомых, то сумма степеней будет $3n$. Чтобы граф существовал, $3n$ должно быть чётным, значит, $n$ должно быть чётным. Однако в условии сказано «учёные» (множественное число), и если их количество нечётно, это невозможно. Но главное: если «все остальные имеют разное число знакомых», это противоречит условию задачи о конечном наборе возможных степеней в графе. В любом случае, общее количество нечётных вершин обязано быть чётным. 129. **Доказательство:** Каждое ребро соединяет две вершины. При подсчёте суммы степеней каждое ребро учитывается дважды (по одному разу для каждой из двух вершин, которые оно соединяет). Следовательно, сумма степеней равна $2 \times (\text{количество рёбер})$, что и требовалось доказать. 130. Воспользуемся теоремой о сумме степеней: а) Сумма: $2 + 2 + 3 + 3 + 4 + 4 = 18$. Количество рёбер: $18 / 2 =$ **9 рёбер**. б) Сумма: $0 + 1 + 2 + 2 + 3 + 4 = 12$. Количество рёбер: $12 / 2 =$ **6 рёбер**.