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

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

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

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

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

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

Вершина 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] не увійшла ні до однієї компоненти.

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