Номер 1, страница 85, часть 1 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

1 Что такое степень вершины графа?

Степень вершины графа — это одна из ключевых числовых характеристик вершины, которая показывает, сколько рёбер с ней связано. Определение различается для неориентированных и ориентированных графов.

Степень в неориентированном графе

В неориентированном графе степенью (или валентностью) вершины $v$ называют количество рёбер, инцидентных ей, то есть рёбер, для которых $v$ является одним из концов. Степень вершины $v$ обычно обозначают как $deg(v)$ или $d(v)$.
Важно отметить, что если в графе есть петли (рёбра, соединяющие вершину саму с собой), то каждая петля при подсчёте степени традиционно добавляет 2 к общей степени, а не 1. Это логично, так как у ребра два конца, и в случае петли оба они "прикреплены" к одной и той же вершине.
Пример: если к вершине $A$ подходит 3 обычных ребра и одна петля, её степень будет $deg(A) = 3 + 2 = 5$.

Ответ: Степень вершины в неориентированном графе — это количество соединённых с ней рёбер, при этом каждая петля считается дважды.

Степень в ориентированном графе (орграфе)

В ориентированных графах рёбра (называемые дугами) имеют направление. Поэтому для каждой вершины различают два вида степеней:
• Полустепень захода (in-degree), обозначаемая $deg^-(v)$ или $d^-(v)$, — это количество дуг, которые входят в вершину $v$.
• Полустепень исхода (out-degree), обозначаемая $deg^+(v)$ или $d^+(v)$, — это количество дуг, которые исходят из вершины $v$.
Полной степенью вершины $deg(v)$ в орграфе называют сумму её полустепени захода и полустепени исхода: $deg(v) = deg^-(v) + deg^+(v)$.

Ответ: В ориентированном графе у вершины есть две степени: полустепень захода (число входящих дуг) и полустепень исхода (число исходящих дуг).

Фундаментальное свойство (Лемма о рукопожатиях)

Существует важное свойство, связывающее степени вершин с общим числом рёбер в графе, известное как лемма о рукопожатиях.
Для неориентированного графа: сумма степеней всех вершин равна удвоенному числу рёбер. Формула: $\sum_{v \in V} deg(v) = 2|E|$, где $V$ — множество вершин, а $E$ — множество рёбер. Это следует из того, что каждое ребро вносит по единице в степени ровно двух вершин (или двойку в степень одной вершины в случае петли). Из этой леммы следует, что число вершин с нечётной степенью в любом графе всегда чётно.
Для ориентированного графа: сумма всех полустепеней захода равна сумме всех полустепеней исхода, и обе эти суммы равны общему числу дуг в графе. Формула: $\sum_{v \in V} deg^-(v) = \sum_{v \in V} deg^+(v) = |E|$. Это верно, поскольку каждая дуга имеет ровно одно начало и один конец.

Ответ: Сумма степеней всех вершин в неориентированном графе равна удвоенному числу рёбер. В ориентированном графе сумма полустепеней захода и сумма полустепеней исхода равны между собой и равны общему числу дуг.