Зв’язок графа - Студопедія
Поняття шляху у графі породжуєвідношення досяжності : вершинаuдосяжна з вершиниv, якщо існує шлях зvуu. Позначення:v#u. Ставлення досяжності є рефлексивним та транзитивним замиканням відношення суміжності вершин. Неважко перевірити, що для графів досяжність є еквівалентністю (але не для орграфів!). Отже, відношення # розбиває безліч вершин графа на класи еквівалентності - взаємно досяжних вершин, які називаються компонентами зв'язності графа. Граф, що має одну компоненту зв'язності, називаєтьсяодносвязним.
Для орграфів ставлення досяжності # є, власне кажучи, нерефлексивним і несиметричним, для орграфів немає єдиного поняття зв'язності.
Асоційованим графом (з орграфом) називається граф, отриманий з цього орграфа заміною стрілок на лінії.
1.Незв'язним називається орграф, асоційований граф якого незв'язний.
2.Слабо зв'язковим називається орграф, асоційований граф якого зв'язаний.
3.Односторонне зв'язковим (або напівзв'язним) називається орграф, в якому для будь-яких вершин u, v виконується u # v або v # u.
4.Сильно зв'язним називається орграф, в якому для будь-яких вершин u, v виконується u#v і v#u.
Очевидно, що 4.3. 12.1.
Максимально зв'язний підграф називається сильно зв'язною компонентою. Кожна вершина належить лише одному сильно зв'язному компоненту – отже, сильна зв'язність є відношення еквівалентності. Фактор-множина вершин з цього відношення є безліч компонент сильної зв'язності. Кожна така компонента може з'єднуватися з іншою стрілками,обов'язково спрямованими в один бік. Зображення компонент зв'язності у вигляді вершин і стрілок, що їх з'єднують, називаєтьсяграфом конденсації даного орграфа (можна при цьому прибрати кратні стрілки, залишивши тільки по одній).
Приклади
Чи не знайшли те, що шукали? Скористайтеся пошуком:
Вимкніть adBlock! і оновіть сторінку (F5)дуже потрібно