Степень вершин

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

Определение 1.10. Полустепенью исхода вершины для орграфа называется количество дуг, для которых является начальной вершиной, обозначается: . Полустепенью захода вершины называется количество дуг, для которых является конечной вершиной, обозначается: . Если , то вершина называется истоком. Если , то вершина v называется стоком.

Теорема 1.1 (Эйлера). Сумма степеней вершин графа равна удвоенному количеству ребер:

.

Доказательство.

При подсчете суммы степеней вершин каждое ребро учитывается два раза: для одного конца ребра и для другого.,

Следствие 1.1. Число вершин нечетной степени четно.

Доказательство.

По теореме Эйлера сумма степеней всех вершин – четное число. Сумма степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна, следовательно, их четное число.,

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

.

Доказательство.

Сумма полустепеней вершин орграфа равна сумме степеней вершин графа, полученного из орграфа забыванием ориентации дуг.,

Пример 1.4. Определить степени вершин данного графа.

Пример 1.5. Определить полустепени исхода и захода данного орграфа.

,