Cтепінь вершини графа

Cтепінь вершини графа

Дві вершини u та v називають суміжними або сусідніми вершинами, якщо вони з’єднані ребром e=(u,v).

Мал.1 Суміжні вершини. 

При цьому:

•          Вершини u та v називають кінцями ребра e.
•          Вершина u інцідентна ребру e .
•          Ребро e інцидентне  вершині u.

Суміжними ребрами називають ребра, які мають спільний кінець. 

Степенем вершини графа називають число ребер, які інцидентні вершині u та позначають  deg u або d(u). 

Ізольованою вершиною називають вершину графа, степінь якої дорівнює нулю.

Мал.2. Степінь вершини. 

Ізольованою вершиною називають вершину графа, степінь якої дорівнює нулю.

Мал.3. Ізольована вершина. 

Висячою вершиною називають вершину графа, степінь якої дорівнює одиниці.

Мал.4. Висяча вершина або лист. 

Множину вершин, які суміжні з вершиною v називають оточенням вершини v та позначають S(v).

Мал.5. Оточення вершини. 

Теорема (Лема про рукостискання). Сума степенів всіх вершин графа дорівнює подвоєному числу ребер.

Наслідок. В будь-якому графі число вершин з непарним степенем – парне.