Тема 12. Частини графа. Зв'язність і роздільність графів.

Питання теми

1. Частини графа.

2. Поняття зв’язності.

3. Поняття роздільності.

Основні терміни теми : маршрут, ланцюг, цикл, суграф.

1. Частини графа

Граф G` = (V`,E`)  є частиною графа G = (V,E), якщо V`  V та E`  E тобто граф має всі вершини та ребра любої його частини. Частина , яка поряд з деякою підмножиною ребер графа, має і всі інцидентні до них вершини, називають підграфом. Частина, яка поряд з деякою підмножиною ребер графа, має всі вершини графа (V` = V, E`  E) називається суграфом. На рис. 5 показані розглянуті графи:

 

а) б) в)  г)

Рис 6. Граф та його частини:

а - граф; б - частина графа; в - підграф; г - суграф

Початковий граф по відношенню до його підграфа називається надграфом, а по відношенню до суграфа - понадграфом. Сукупність всіх ребер графа, що не належать до його підграфа (разом з інцидентними вершинами), утворює доповнення підграфа. Говорять, що підграфи G` = (V`,E`) та G`` = (V``,E``)  розділені ребрами, якщо вони не мають спільних ребер (Е` E`` =  )  і розділені вершинами, якщо у них немає спільних вершин (V` V`` =  ).

2. Поняття зв’язності

Дві вершини називаються зв’язаними, якщо існує маршрут, який з’єднує ці вершини. Граф, будь-яка пара вершин котрого зв’язана, називають зв’язним графом. Очевидно, що у зв’язному графі між любими двома вершинами існує простий ланцюг, такий що із маршруту, що їх зв’язує завжди можна вилучити циклічну дільницю, яка проходить через деяку вершину більш ніж один раз (див. рис.7, де маршрут між вершинами v  i v  зображений жирними лініями).

   Цикл, який вилучається

 

Простий ланцюг

Рис. 7.  Зв’язний граф.

Якщо граф не зв’язний, тоді множину його вершин можна єдиним чином  розділити на непересічні множини, кожна з яких має всі зв’язані між собою вершини та разом з інцидентними їм ребрами утворює зв’язний підграф. Таким чином, незв’язний граф представляє сукупність окремих частин (підграфів), які називаються компонентними. На рис. 8 показаний підграф, який складається з трьох компонент (ізольована вершина теж є компонентою).

Зв’язність орграфів визначається також як і для неорієнтованих (без рахунку направлення дуг). Специфічним для орграфа або змішаного графа є поняття сильної зв’язності. Орграф називається сильно зв’язним, якщо для будь якої пари його вершин  та  існує шлях з  в  . Граф, який представляє план міста з одностороннім рухом по деяким вулицям, повинен бути сильно зв’язним, тому що в протилежному випадку знайшлися б вершини (площі та перехрестя), між якими не можна було б проїхати по місту, не порушуючи правил дорожнього руху.

 

Рис. 8. Незв’язний граф, який складається з трьох компонент

(G , G , G ).

3. Поняття роздільності

Зв’язний граф може бути розділеним на незв’язні підграфи вилученням з нього деяких вершин та ребер (при вилученні вершин вилучаються і всі інцидентні їм ребра, а при вилученні ребер вершини зберігаються). Якщо існує така вершина, вилучення  якої перетворює зв’язний граф (чи компоненту незв’язного графа) в незв’язний, тоді вона називається точкою співчленення (див. рис. 9, а). Ребро з такими ж властивостями називається мостом (див. рис. 9, б). Ясно, що при існуванні моста в графі є по крайній мірі, дві точки з’єднання.

 

a)  б)

 

в)

Рис. 9. Роздільні графи.

а - з точкою з’єднання; б - з мостом; в - блоки В  - В  графа з мостом

 Граф називається нероздільним, якщо він зв’язний та не має точок  з’єднання (наприклад, граф на рис. 6, а нероздільний). Граф, який має хоча б одну  точку з’єднання, є роздільним і називається сепарабельним. Він розбивається на блоки, кожний з яких представляє собою максимальний нероздільний підграф ( на рис. 9, в показані блоки В , В , В  графа рис. 9, б).

Кожне ребро графа, як і кожна вершина (за виключенням точок з’єднання), належать тільки одному з його блоків. Більш того, тільки одному блоку належить і кожний простий цикл. Звідси виходить, що сукупність блоків графа розбиття множин ребер та простих циклів на підмножини, що не перехрещуються.