Page 37 - 4386

3.4 Точки зчленування, мости

При вирішенні практичних задач із графами досить часто

доводиться розв’язувати задачу для окремих частин графа, а

потім результати об’єднувати. Розклад графа на окремі

структурні частини дозволяє зменшувати розмірність

розв’язуваних підзадач і досягати ефективнішого розв’язку всієї

задачі.

Найпростіший спосіб розкладу графа – у пряму суму його

компонент зв’язності. Проте існують класи зв’язних графів, які

можна піддавати структурній декомпозиції, тобто розкладати на

компоненти зв’язності в результаті вилучення однієї вершини чи

ребра. Виявлення таких вершин та ребер допомагає вивчати

структуру зв’язного графа.

Точкою зчленування графа або розділовою вершиною

називається вершина, вилучення якої збільшує кількість

компонент зв’язності; ребро з такою ж властивістю називається

мостом. Таким чином, якщо v – точка зчленування зв’язного

графа G, то граф G-v – незв’язний.

Нероздільним називається нетривіальний зв’язний граф, що

не має точок зчленування. Блок графа – це його максимальний

(за відношенням включення) нероздільний підграф. Нероздільний

граф сам є блоком. Так, на рис. 3.1 а вершина v є точкою
3
зчленування, а на рис. 3.1 б вершини v та v є точками
5
6
зчленування, а ребро (v , v ) є мостом.
5
6
Множина ребер C зв'язного графа G називається множиною

розрізу, якщо видалення ребер із графа, що належать множині C,

порушує зв’язність графа, а видалення власної підмножини

множини C залишає граф зв'язним.

36