Связность графа

Понятие пути в графе порождает отношение достижимости: вершина u достижима из вершины v, если существует путь из v в u. Обозначение: v # u. Отношение достижимости является рефлексивним и транзитивным замыканием отношения смежности вершин. Нетрудно проверить, что для графов достижимость является отношением эквивалентности (но не для орграфов!). Следовательно, отношение # разбивает множество вершин графа на классы эквивалентности – взаимно достижимых вершин, которые называются компонентами связности графа. Граф, имеющий одну компоненту связности, называется односвязным.

Для орграфов отношение достижимости # является, вообще говоря, нерефлексивным и несимметричным, поэтому для орграфов нет единого понятия связности.

Ассоциированным графом (с орграфом) называется граф, полученный из данного орграфа заменой стрелок на линии.

1. Несвязным называется орграф, ассоциированный граф которого несвязен.

2. Слабо связным называется орграф, ассоциированный граф которого связен.

3. Односторонне связным (или полусвязным) называется орграф, в котором для любых вершин u, v выполняется u # v или v #u.

4. Сильно связным называется орграф, в котором для любых вершин u, v выполняется u # v и v #u.

Очевидно, что 4.Í 3. Í2.Í1.

Максимально сильно связный подграф называется сильно связной компонентой. Каждая вершина принадлежит только одной сильно связной компоненте – следовательно, сильная связность есть отношение эквивалентности. Фактор–множество вершин по этому отношению есть множество компонент сильной связности. Каждая такая компонента может соединяться с другой стрелками, обязательно направленными в одну сторону. Изображение компонент связности в виде вершин и соединяющих их стрелок называется графом конденсации данного орграфа (можно при этом убрать кратные стрелки, оставив только по одной).

Примеры