Знаходження точок сполучення зв'язного неорієнтованого графа та перевырка його на двозв'язність

Точкою сполучення неорієнтованого графа називається вершина, при видаленні якої, разом з усіма суміжними її ребрами, збільшується кількість компонент зв'язності графа. Відповідно, для зв'язного графа точкою сполучення називається вершина, при видаленні якої граф перестає бути зв'язним. Наприклад, точками сполучення для графа, який зображено на малюнку що міститься нижче, є вершини і . Якщо видалити вершину , то граф, який складається з однієї компоненти зв'язності, розбивається на два підграфи і . Якщо видалити вершину , то граф розбивається на підграфи і . Але якщо видалити будь-яку іншу його вершину, то в цьому випадку, розбити зв'язну компоненту з якої складається даний граф на кілька частин, не вдасться. Зв'язний граф, який не має точок сполучення, називається двозв'язним.

Точки сполучення неорієнтованого графа

Графічне представлення алгоритму пошуку точок сполучення в неорієнтованому графі

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

Наведемо простий алгоритм знаходження всіх точок сполучення зв'язного неорієнтованого графа, який базується на використанні методу обходу в глибину. Відмітимо, що при відсутності цих точок граф, очевидно, буде двозв'язним, тобто цей алгоритм також можна розглядати як тест який дозволяє визначити чи заданий граф є двозв'язним.

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

Далі, для кожної вершини обчислюється число , рівне мінімальному серед чисел  нащадків вершини , включаючи і саму вершину  та її предків, для яких існує зворотне ребро, що поєднює їх з нащадками вершини . Але, виходячи з того, що число , для всіх вершин , обчислюється при обході дерева у зворотному порядку, то при обчисленні  для вершини  уже підраховані дані числа для всіх її нащадків. В такому випадку,  обчислюється як мінімум серед наступних чисел: глибина обходу  вершини ; глибина обходу всіх вершин, для яких існує зворотне ребро, що веде у вершину  всіх дочірніх ввершини  по відношенню до вершини .

Після цього, точки сполучення неорієнтованого графа визначаються згідно з наступними правилами:

  1. Корінь дерева пошуку в глибину буде точкою сполучення тоді і тільки тоді, коли він має дві або більше дочірні вершини (вершина , вперше виявлена з  при обході графа в глибину називаєтьсмя дочірньою для вершини ). Так як в дереві обходу, отриманому методом пошуку в глибину, немає поперечних ребер, то видалення такого кореня розіб'є дерево обходу на окремі піддерева, коренями яких будуть дочірні вершини по відношенню до кореня побудованого дерева. Для графа зображеного на рисунку, що міститься вище, вершина (корінь дерева) має тільки одну дочірню вершину , а тому вона не є точкою сполучення даного графа.
  2. Вершина , відмінна від кореня, буде точкою сполучення тоді і тільки тоді, коли для неї існує така дочірня вершина , що . В такому випадку видалення вершини  (і, звичайно, всіх інцидентних їй ребер) відокремить вершину  і всіх її нащадків від решти графа. Якщо ж , то існує шлях по ребрах дерева до нащадків вершини  і зворотне ребро від якого-небуть з цих нащадків до істинного предка вершини  (саме значенням глибини обходу  для цього предка дорівнює ). Тому в даному випадку видалення вершини  не відділить від графа  піддерево з коренем у вершині .

Знаходження точок сполучення зв'язного неорієнтованого графа — приклад:

Знайти всіх точок сполучення зв'язного неорієнтованого графа, що міститься на наступному малюнку.

Неорієнтований граф задачі

Для цього, як зазначалося вище, для заданого графа застосуємо алгоритм обходу в глибину. В результаті отримаємо наступне дерево обходу.

Дерево обходу в глибину заданого графа

На наступному кроці, переходимо до обчислення чисел  і здійснювати це будемо в зворотньому поядку, тобто з вершини номер «4». Очевидно, що для даної вершини . Після цього, переходимо до вершини під номером «8». Виходячи з того, що для даної вершини існує обернене ребро , то . Далі, переходимо до верштн «7», «6», «5», «3», «2» та «1», для яких дані числа обчислюються наступним чином:

Після обчислення всіх чисел , переходимо до визначення точок сполучення. Для цього переглядаємо кожну вершину дерева обходу в глибину. Отже, корінь дерева (вершина номер «1») є точкою сполучення, так як для неї існує дві дочірні вершини «2» та «4». Вершина номер «2» та «5» також є точками сполучення — для їх дочірніх вершин «5» та «6», виконуються нерівності  та відповідно.

Точки сполучення заданого неорієнтованого графа

Інші вершини заданого графа, такі як «3», «4», «6», «7» та «8» не є точками сполучення.

Блок-схема алгоритму знаходження точок сполучення зв'язного неорієнтованого графа

Точки сполучення неорієнтованого графа блок-схема

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар