Page 43 - 2577

Граф G V, E  називається підграфом графа G(V,E), він позначається

G V ,  E  G V, E , якщо V  V і E  E . Таким чином, кожна вершина в G є вершиною в

G, і кожне ребро в G є ребром в G.
V
Нехай G = G(V,E) – граф з вершинами v ,v ,...,v  і ребрами e , e ,..., e  E .
0 1 k 1 2 k
Шляхом довжини k із v в v називається послідовність v e v e v e ...v e v така, що
0 k 0 1 1 2 2 3 k 1 k k

e  v ,v . Коротко шлях позначають як v ,v ,...,v . Таким чином, шлях довжиною k має k
i i 1  i 0 1 k
ребер. Простим шляхом із v в v називають шлях, в якому немає вершин, що
0 k
повторюються.
Приклад. В графі який показаний на рис 3.5 шлях v v v v v є простим шляхом.
0 1 2 5 7
Граф G називається зв’язаним, якщо
є шлях між будь-якими двома його різними
вершинами. Граф, який показаний на рис.
3.5 є зв’язаним графом, а граф на рис. 3.6 –
не зв’язаний.

Рисунок 3.5 – Простий граф
Слід відмітити, якщо шлях не є
простим (має вершини, які повторюються
більше одного разу), то вилучивши частину
шляху між двома появами вершини v ,
i
можна отримати простий шлях.
Рисунок 3.6 – Незв’язаний граф

Наприклад, розглянемо шлях (рис. 3.5) v v v v v v v v v v v v v , вилучивши частини
0 3 4 1 0 3 4 1 2 5 4 6 7
шляхуv v v v і v v v v , отримаємо простий шлях v v v v v .
4 1 0 3 1 2 5 4 0 3 4 6 7
Теорема. Нехай G = G(V,E) – граф. Якщо існує шлях із вершини v до вершини v , то
i j
існує простий шлях із вершини v до вершини v .
i j
Підграф G графа G називається компонентою графа G, якщо виконані наступні дві
умови:
1) G – непустий зв’язаний граф;
2) G  – зв’язаний підграф графа G і G  G , тоді G  G  . Звідси G – максимальний

зв’язаний підграф графа G. На рис. 3.7 показаний граф та його компоненти.
Циклом графа називають шлях ненульової довжини, який з’єднує вершину саму з
собою і не вміщує ребер, які повторюються.

a) б)
в)
Рисунок 3.7 – Граф (а) та його компоненти (б і в).

Простим циклом називають цикл, який з’єднує вершину v саму з собою і не вміщує
0
вершин, які повторюються, крім v . Цикл називають k – циклом, якщо він вміщує k ребер і
0

40