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

Вершина Xi називається инцидентной дузі (ребру) графа, якщо вона є початком або кінцем цієї дуги (ребра).

Ступенем вершини графа називають число дуг (ребер), інцидентних даній вершині. Ступінь позначається P (Xi).

Для орієнтованого графа розрізняють полустепені заходу P + - число дуг, що входять в дану вершину, і полустепені результату P - - число дуг, що виходять з даної вершини. Ступінь вершини орієнтованого графа складе сума полустепені результату і заходу.

Якщо для деякої вершини орієнтованого графа полустепені заходу деякої вершини P + = 0 і при цьому полустепені результату P - ¹0, то вершина називається входом графа.

Якщо для деякої вершини орієнтованого графа P - = 0, а P + ¹0, то вершина називається виходом графа.

Граф, зображений на рис. 3.1.2, має один вхід - вершину X0

Число ребер графа N пов'язано зі ступенями його вершин наступним співвідношенням:

де n - число вершин графа. Звідси випливає справедливість наступних тверджень:

1) Сума ступенів вершин будь-якого графа парна;

2) Для будь-якого графа число вершин, що мають непарні ступеня, парне;

3) Для однорідного графа, тобто графа, все ступеня вершин якого однакові і рівні r, N =;

4) Для повного графа, тобто графа, в якому кожна пара вершин з'єднана ребром або дугою, P (Xi) = n-1, а N =.

Деякою протилежністю повного графу є нуль-граф, який не має ребер або дуг і складається з ізольованих вершин. Очевидно, ступеня вершини нуль-графа рівні 0.

Граф називається зв'язковим. якщо безліч його вершин не можна розбити на два або більше підмножин так, щоб жодна вершина одного підмножини не відображаються в вершину іншого. В іншому випадку граф називається незв'язних. Число підмножин, не пов'язаних відображеннями, на яке розбивається безліч всіх вершин графа, називається числом компонент зв'язності для незв'язного графа.

Існує інше визначення зв'язності графа. Граф називається зв'язковим, якщо дві будь-які його вершини можна з'єднати ланцюгом. Граф (рис. 3.1.3) є незв'язним з двома компонентами зв'язності.

Ребро графа називається перешийком, або сполучною лінією, якщо його видалення призводить до того, що граф стає незв'язним. На рис. 3.1.4 зображені три зв'язкових неорієнтованих графа, причому граф 1 не має жодного перешийка, 2 містить один перешийок (відзначений жирною лінією), граф 3 цілком складається з одних перешийків. Такий граф (3) називається деревом.