Page 42 - 2577

3 ПРОЕКТУВАННЯ ТОПОЛОГІЧНОЇ СТРУКТУРИ КОМП’ЮТЕРНОЇ
МЕРЕЖІ

3.1 Короткі відомості з теорії графів

3.1.1 Основні поняття та визначення
Граф є кінцева множина V, яка називається множиною вершин, і множина Е
двоелементних підмножин множини V. Множина Е носить назву множини ребер. Елемент
множини Е називають ребром. Граф позначають G(V,E). Елементи a і b множини V
називають з’єднаними або зв’язаними ребрами.
Зазвичай кінцевий граф, зображують у вигляді діаграми, на якій вершини позначені
точками, а ребра – лініями.
Якщо {a,b} – ребра, тоді вершини a і b називають їх кінцями. Ребро (a,b) називають
інцедентним вершинам a і b і, навпаки, вершини a і b інцедентні ребру (a,b).
Дві вершини називають суміжними, якщо вони є кінцями ребра (інцедентні ребру).
Два ребра називають суміжними, якщо вони інцедентні одній вершині (рис. 3.1)
b c Приклад. Граф з множиною вершин
V={a,b,c,d,e} і множиною ребер E={(a,b),
(a,e), (b,e), (b,c), (b,d), (c,d)} показаний на
a рис. 3.2
a
Рисунок 3.1 – Суміжні ребра (a,b) і
(b,с)
c
Визначені нами графи носять назву –
простих. Обмеження на існування тільки b
одного ребра між двома вершинами дає
можливість подати будь – яке ребро не як d
елемент множини Е.
a e
Рисунок 3.2 – Граф з множиною
вершин V і множиною ребер Е.

Наше визначення виключає також ребра, які називають петлями (рис. 3.3). Ребро яке
з’єднує вершину саму з собою називається петлею. Граф, в якому є петлі, називають графом
з петлями.
b Якщо в графі є більше одного ребра
між двома вершинами, то він носить назву
мультиграфа (рис. 3.4)

a c

Рисунок 3.3 – Граф з петлею
Якщо граф має петлі і вершини, які b
з’єднані більше ніж одним ребром, то такий
граф називають псевдографом.
a c
Рисунок 3.4 – Мультиграф

Степенню вершини v , позначають deg(v), називають кількість ребер, які інцидентні
даній вершині V. Вершина степені 0 називається ізольованою.

39