Page 14 - 4336

Віддображженням вершини v Г(v ) –– є множжина веершин, вв які
i
i
існуютьь дуги з ввершинии v , тобтто Г(v )=={v :  дууга (v , v )  E}.
i
i
jj
j
i
Таак, для оорграфа G на рис. 1.66, опис заданнямм множжини
1
вершинн і відповідностіі виглядаає настуупним чиином: GG =(V, Г)), де
1
V={v }, і=1, 2, ...., 4 – ммножинаа вершинн, Г(v )=={v }, Г(vv )={v , v },
2
1
2
3
4
i
Г(v )={vv }, Г(v ))={v , v } – відоббраженння.
4
1
4
2
3

G G G
2
1
Рисуунок 1.6.

Длля неоріієнтованого або змішанного графа переедбачаєтться,

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

неорієннтованого ребра двома ппротилежжно напправлениими дугаами,
що споолучаютьь ті ж самі верршини. Наприкклад, дляя графаа G
2
(рис. 1.66) відобрраженняя вершинн v та v буде наступнимм:
2
4
Г(vv )={v , v , v }, ГГ(v )={v , v }.
5
3
1
2
5
33
4
1.33.4 Маттриця сусуміжноості, іннциденттності т та спиисок
ребер гррафа

Від дношенння інциддентностті для гррафа можна опиисати також

матриццею сумміжностті, матррицею інциденттності т та списском

ребер графа. Опишеммо доклладно ккожний із перрераховааних

способіів.

Занумеруєємо всі вершинии графаа G натууральнимми числлами

від 1 доо n.

14