Компоненти зв’язності

Нагадаємо, що граф називають зв’язним, якщо у ньому існує шлях між кожною парою вершин.

Позначимо множину, що складається з даної вершини і всіх тих вершин графа, що можуть бути з’єднані з нею ланцюгом.

Означення 2.3.1. Компонента зв’язності чи просто компонента – це підграф, породжений множиною типу або вершинно породжений підграф .

Розглянемо незв’язний неорієнтований граф .

Множину його вершин можна розбити на такі підмножини:

; ; , так, що вершинно породжені підграфи , , були зв’язними, і жодна вершина з підмножини не була суміжною з жодною вершиною підмножини , .

Очевидно, виконуються такі властивості для підмножин , які утоворюють розбитття множини :

1) ;

2) ;

3) .

Підграфи , , – компоненти зв’язності графа . Кожен з них – максимально зв’язний підграф графа , тобто не є власним підграфом будь-якого іншого підграфа .

Отже, наведений на прикладі граф має три компоненти зв’язності.

Теорема 2.3.1. Граф буде зв’язним лише у тому випадку, якщо він складається з однієї компоненти зв’язності.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Поняття графа	\|	Ранг та цикломатичне число графа

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.002 сек.