Головна

Визначення зв'язності графа

  1. I. 4. Які типи хвиль існують в природі, техніці? Які хвилі називаються пружними? Дайте визначення поздовжніх і поперечних пружних хвиль.
  2. I. Визначення рівнянь лінійної регресії
  3. I. ПОСТАНОВКА ПРОБЛЕМИ І ВИЗНАЧЕННЯ МОВНИХ ЖАНРІВ 1 сторінка
  4. I. ПОСТАНОВКА ПРОБЛЕМИ І ВИЗНАЧЕННЯ МОВНИХ ЖАНРІВ 2 сторінка
  5. I. ПОСТАНОВКА ПРОБЛЕМИ І ВИЗНАЧЕННЯ МОВНИХ ЖАНРІВ 3 сторінка
  6. I. ПОСТАНОВКА ПРОБЛЕМИ І ВИЗНАЧЕННЯ МОВНИХ ЖАНРІВ 4 сторінка
  7. II етап - Запит котирувань і визначення переможця

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

Вирішимо задачу визначення зв'язності графа за допомогою елементів алгоритму Фаулкса.

Нехай дана матриця суміжності R неориентированного графа G (матриця R симетрична щодо головної діагоналі), що має n вершин. Необхідно визначити, чи є цей граф зв'язковим. У разі, якщо граф незв'язних, то потрібно виділити з нього все т зв'язкових подграфов G1, G2, ..., Gm таких, що, наприклад, з будь-якої вершини подграфа G1 можна знайти шлях або маршрут, що веде до будь-якої іншої вершини цього ж подграфа, але не можна знайти шлях або маршрут до жодної вершини, що не належить даному подграфа G1. Потрібно визначити, які вершини входять в кожен з подграфов.

На підставі матриці суміжності R отримаємо матрицю досяжності не більше ніж за один крок R1.

Потім, відповідно до алгоритму Фаулкса, знайдемо матрицю RN шляхом булевского перемноження матриць (RN = RN-1 A R1 ) До тих пір, поки не досягнемо RN = RN-1. отримана матриця RN є матрицею досяжності графа G. Вона дозволяє виявити зв'язкові підграфи і номера вершин, що входять в зв'язкові підграфи. Для цього необхідно в деякій i - Рядку матриці RN знайти елементи rNij = 1, i, j = 1, ...,n. номери стовпців j, де rij = 1, і будуть номерами вершин, що входять в зв'язний підграф, що включає в себе i-у вершину. Розглядаючи послідовно всі співпадаючі рядки матриці можна виявити всі т зв'язкових подграфов вихідного графа G.

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

Приклад.

Нехай задана матриця R1 досяжності не більше ніж за один крок неориентированного графа G , що має n = 8 вершин.

Необхідно перевірити граф на зв'язність і виявити всі зв'язкові підграфи.

1. Задамо початковий номер циклу обчислень: N = 1.

2. N = N +1 = 2.

3. Виробляємо множення R1 A R1 = R2

.

4. Перевіряємо умову рівності R2 и R1. Вони не рівні. Переходимо до п. 2.

2) N = 2 + 1 = 3.

3) Множення R2 A R1= R3.

.

4) Перевіряємо умову рівності матриць R2 и R3. Так як вони рівні, то це означає, що шлях довжиною 2 - максимальний в цій графі, і подальше множення матриці не має сенсу, так як ми будемо отримувати одну і ту ж матрицю. знайдена матриця R3 є матриця досяжності вихідного графа. Наявність нулів в отриманої матриці показує, що між відповідними елементами відсутня шлях любойдліни і, отже, даний граф - незв'язних.

5. Вибираємо початкову вершину для виявлення зв'язкових подграфов: i = 1.

6. У рядку i = 1 вибираємо всі елементи r31j , Рівні одиниці (j= 1, ...,n). r311 = r312 = r317 = r318 = 1. Номери стовпців, в яких r3ij = 1 - це номера вершин першого зв'язкового подграфа, що входить в даний граф. Тобто вершини 1, 2, 7, 8 утворюють зв'язний підграф G1 .

7. Визначаємо номер чергової вершини i = 1 + 1 = 2. Оскільки 2 ? 8, то на 8 (інакше на 9).

8. Перевіримо - чи входить дана вершина в знайдені зв'язкові підграфи. Якщо серед вершин знайдених зв'язкових подграфов є дана вершина, то на 7, інакше на 6.

Так як серед вершин зв'язного подграфа G1 є вершина j= 2, то повертаємося до п.7.

7) i = 2 + 1 = 3. Так як 3 ? 8, то на 8.

8) Серед вершин зв'язного графа G1 немає вершини j= 3. Повертаємося до п. 6.

6.) У рядку 3 вибираємо елементи, рівні одиниці: r333 = r336 = 1. Отже, у другій зв'язний підграф G2 входять вершини 3, 6.

7) Визначаємо номер чергової вершини i = 3 + 1 = 4 Так як 4 ? 8, то на 8.

8.) Серед вершин зв'язкових подграфов G1 и G2 немає вершини j = 4. Повертаємося до п. 6.

6.) У рядку 4 вибираємо елементи, рівні одиниці. r344 = r345 = 1. Отже, в третій зв'язний підграф G3 входять вершини 4, 5.

7) i = 4 + 1 = 5. Так як 4 ? 8, то на 8.

8) Серед вершин зв'язкових графів G1, G2, G3 є вершина j = 5. Переходимо до п.7.

Аналогічно перевіряються вершини j = 6, 7, 8. Вони входять в уже отримані вище підграфи.

9. Якщо перевірені всі вершини, то всі зв'язкові підграфи знайдені. Кінець.

Таким чином в результаті роботи алгоритму знайдені три зв'язкових подграфа:

G1 = {1, 2, 7, 8}; G2 = {3, 6}; G3 = {4, 5} (див. Рисунок 4.2)


.

Рис 4. 2.

 



Визначення гамільтонова шляху в графі | Визначення ейлерового шляху в графі

Робота 1. ДОСЛІДЖЕННЯ І ОПИС КІНЦЕВОГО АВТОМАТА | Методичні вказівки | Методичні вказівки | Лабораторні роботи з курсу: ДМ | Загальні відомості | Методичні вказівки | Вихідні дані (завжди апріорна інформація). | завдання | Методичні вказівки | Знаходження сильних компонент, базового і домінуючого множин |

© um.co.ua - учбові матеріали та реферати