Page 24 - 4386

G G
1
2
Рисунок 2.1

2.3 Задання графів відповідністю

Опис графів відповідністю полягає в заданні множини

вершин V та відповідності Г, яка показує зв'язок між вершинами.

Відповідністю Г називається відображення множини V в V, а

граф в цьому випадку позначається парою G=(V, Г).

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

G G
1
2
Рисунок 2.2

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

що відповідність Г задає такий еквівалентний орієнтований граф,

23