Page 60 - 4496

n
 ( v )   
і 2 i ik (3.2)
k 1
Оскільки кожне ребро орграфа має один початок і один
кінець, то (3.1) і (3.2) є рівні між собою. Звідси випливає, що в
однорідному орграфі степені k з n вершинами і m ребрами
m=kn.

3. 8 Частини графа, суграфи та підграфи
Означення 2. Граф H називають частиною графа
G(H  G), якщо множина його вершин V(H) міститься в
множині V(G), а множина ребер E(H) — в E(G).
Якщо V(H)= V(G), то H називають суграфом.
Суграф H покриває вершини неорієнтованого графа G (є
покривним), якщо будь-яка із вершин останнього—
інцидентна хоча б одному із ребер H.
Означення 2. Під графом графа G називається частина

графа з множиною вершин U V(G), якщо її ребрами є всі
ребра з E(G), обидва кінці яких належать U.
Підграф – зірка.

3. 9 Операції з частинами графа
Доповнення H частини H називається множина всіх
частин графа G, що не належать H.
Об’єднання H1 і H2 визначається так:
V(H1  H2)= V(H1)  V(H2); тобто об’єднання вершин і
E(H1  H2)= E (H1)  E (H2). об’єднання ребер.
Переріз H1 і H2 визначають аналогічно

57