Page 23 - 4386

2 СПОСОБИ ЗАДАННЯ ГРАФІВ

Задати граф – означає описати множини його вершин і

ребер, а також відношення інцидентності. Для цього досить

занумерувати вершини та ребра графа.

2.1 Задання графа за допомогою діаграми

Граф G=(V, E) зручно зображати за допомогою рисунка на

площині, який називають діаграмою графа G. Вершинам графа G

ставляться у відповідність точки площини; точки, що

відповідають вершинам v та w, з’єднуються лінією (відрізком або

кривою) тоді і тільки тоді, коли v та w суміжні вершини (рис. 2.1).

Зрозуміло, що діаграма графа змінюватиме свій вигляд у

залежності від вибору відповідних точок на площині.

2.2 Задання графа переліком його елементів

Одним із способів задання графа G=(V, E) є задання кожної з

множин V і E за допомогою переліку їх елементів.

Так, граф G =(V , E ), що складається із чотирьох вершин та
1
1
1
п’яти ребер можна задати наступним чином (рис. 2.1):
V ={v , v , v , v },
1
4
3
2
1
E ={(v , v ), (v , v ), (v , v ), (v , v ), (v , v )}.
1
2
4
2
3
4
3
4
1
1
3
Граф G =(V , E ), що задається так :
2
2
2
V ={v , v , v , v , v },
1
2
5
2
3
4
E ={(v , v ), (v , v ), (v , v ), (v , v ), (v , v ), (v , v ), (v , v )},
5
3
5
3
4
2
4
1
3
2
1
2
5
2
1
складається із п’яти вершин та семи ребер (рис. 2.1).
22