Page 36 - 4386

а б

Рисунок 3.3 – Приклад незв’язного (а) та зв'язного (б) графів

Максимальний непорожній зв'язний підграф G′ графа G

називається компонентою зв'язності (зв’язною компонентою)

графа G. Кожний граф можна однозначно подати як пряму суму

зв’язних компонент. Для будь-якого графа G=(V, E) або він сам,

або його доповнення є зв’язним графом. Якщо G незв’язний граф,

то граф G зв’язний.

Незв'язний граф має, як мінімум, дві компоненти зв'язності.

Наприклад, граф, зображений на рис. 3.3 а, має дві компоненти:

=({v , v }, {(v , v )}) та =({v , v , v }, {(v , v ), (v , v ), (v , v )}).
′
′
1 1 2 1 2 2 3 4 5 3 4 3 5 4 5
До якісних ознак зв’язності слід віднести такі.
Нехай G′ – це граф, який одержаний після вилучення із

зв’язного графа G=(V, E) деякого ребра e∈E. Тоді:

1) граф G′ зв’язний, якщо ребро e належить циклу в графі G;

2) граф G′ незв’язний і має тільки дві компоненти зв’язності,

якщо ребро e не входить у жодний цикл у графі G.

До кількісних ознак зв’язності слід віднести такі.

1. У довільному графі з n вершинами, k компонентами

зв’язності та кількістю ребер m задовольняються нерівності

n-k≤m≤(n-k)(n-k+1)/2.

2. Довільний зв’язний граф з n вершинами містить не менше

ніж n-1 ребро. Якщо m<n-1, то граф з n вершинами та m ребрами

незв’язний.

35