Page 15 - 4386

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

Степенем вершини v в графі G називається кількість ребер,

інцидентних вершині v і позначається δ(v). Множину вершин,

суміжних з вершиною v, позначають O(v). Очевидно, що

|O(v)|=δ(v).

У неорієнтованому графі без петель з n вершинами степінь

вершини може мати значення від 0 до n-1. Вершина степеня 0

називається ізольованою (вона не має інцидентних ребер та

суміжних вершин), а степеня 1 – кінцевою або висячою (має

тільки одне інцидентне ребро). Якщо вершина має степінь n-1, то

вона суміжна з усіма іншими вершинами і у графі немає

ізольованих вершин. Аналогічно, якщо в графі є ізольована

вершина, то немає вершини степеня n-1 (суміжної з усіма

іншими). У графі з петлями, петля дає внесок у 2 одиниці в

степінь вершини.

Отже, справджуються наступні твердження для будь-якого

неорієнтованого графа без петель:

1. У будь-якому графі з n вершинами одночасно не можуть

існувати вершини степенів 0 і n-1.

2. У будь-якому графі з n вершинами (n≥2) є принаймні дві

вершини з однаковими степенями.

3. Сума степенів вершин графа G=(V, E) дорівнює подвоєній

кількості його ребер:

∑ ( δ v) = E . (1.1)
2
v ∈V

Справедливість цього твердження випливає з того, що кожне

ребро графа інцидентне двом вершинам, тому у суму степенів

усіх вершин воно вносить дві одиниці.

14