• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Компоненти сильної зв'язності графа

Поняття сильної зв'язності відноситься тільки|лише| до орграфів|.

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

Орграф називається зв'язковим, якщо зв'язна його підстава|основа,заснування|.

Вершина u досяжна з|із| вершини v, якщо існує маршрут з|із| v в u.

Орграф називається сильно зв'язковим, якщо будь-яка його вершина досяжна з|із| будь-якої вершини.

Граф називається таким, що орієнтується, якщо він є|з'являється,являється| підставою|основою,заснуванням| сильно зв'язного графа.

Приклад|зразок| 13.3. Знайти компоненти сильної зв'язності графа, зображеного|змальованого| на мал. 13.3.

Мал. 13.3

Рішення|розв'язання,вирішення,розв'язування|. Матриця суміжності графа має вигляд|вид|

.

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

.

Виділимо з|із| цієї матриці головний мінор максимального порядку|ладу|, що не містить|утримує| нулі. Якщо граф зв'язний, то в матриці будуть рядки, що не містять|утримують| нулів. Це рядки 2, 4, 6:

.

Мінор з|із| рядками і стовпцями з|із| цими номерами відповідає одній компоненті зв'язності:

.

Видалимо|знищимо,віддалимо| з|із| матриці рядки і стовпці з|із| цими номерами, Одержимо|отримаємо| мінор, відповідний другий компоненті зв'язності:

.

Отже, в графі дві компоненти сильної зв'язності: підграф з|із| вершинами 1, 3, 5 і підграф з|із| вершинами 2, 4, 6.

Мал. 13.4

На мал. 13.4 (а, би) показані обидві компоненти сильної зв'язності у вигляді окремих графів. Загальне|спільне| число ребер в компонентах менше розміру початкового|вихідного| графа. Дуга [2, 3] не увійшла ні до однієї компоненти.

Переглядів: 2146