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

Степени, маршруты, связность

ЛЕКЦИЯ № 13

Def. Степенью вершины v графа называется число инцидентных ей ребер. Обозначается deg v. Вершина степени 0 называется изолированной, степени 1 – концевой или висячей.

Для орграфа вводятся также понятия

- полустепень исхода – число дух выходящих из v; обозначается deg^– v;

- полустепень захода – число дух входящих в v; обозначается deg⁺ v;

Свойство. .

Теорема 2.1. (Теорема Эйлера, лемма о рукопожатиях). ;

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

Теорема 2.2. (о нечетных степенях). В конечном графе число вершин с нечетными степенями четно.

Доказательство. Обозначим . По теореме 1.2. S четно. Далее, положим S_Ч – сумма степеней вершин с четной степенью, S_Н – сумма степеней вершин с четной степенью. Очевидно, S = S_Ч + S_Н. В S_Ч каждое слагаемое четно, значит, само S_Ч тоже четно. Отсюда, в силу четности S, получаем, что S_Н четно. Но каждое слагаемое в нем – нечетно. Следовательно, таких слагаемых должно быть четное число. Ч Т Д.