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

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

Тема 2.3. ДЕРЕВА І ЦИКЛИ У ГРАФАХ

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

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

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

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

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

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

1) ;

2) ;

3) .

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

Дата добавления: 2014-10-17