Компонента сильной связности графа | это... Что такое Компонента сильной связности графа? (original) (raw)

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

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

Орграф называется сильно связным (strongly connected), если любые две его вершины сильно связаны. Две пары вершин s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Сильно связными компонентами орграфа называются его максимально сильно связные подграфы.

Содержание

• 1 Определения
• 2 Алгоритмы
• 3 Пример
• 4 Ссылки
• 5 Литература

Определения

Орграф, не принадлежащий к классу сильно связных графов, содержит некоторый набор сильно связных компонент, и некоторый набор ориентированных ребер, идущих от одной компоненты к другой.

Любая вершина орграфа сильно связана сама с собой.

Алгоритмы

Простейший алгоритм решения задачи о поиске сильно связных компонент в орграфе работает следующим образом:

1. При помощи транзитивного замыкания проверяем, достижима ли t из s, и s из t, для всех пар s и t.

2. Затем определяем такой неориентированный граф, в котором для каждой такой пары содержится ребро.

3. Поиск компонент связности такого неориентированного графа даст нам компоненты сильной связности нашего орграфа.

Очевидно основное время работы данного алгоритма приходится на реализацию транзитивного замыкания.

Также существует три алгоритма, решающих данную задачу за линейное время, то есть в V раз быстрее, чем приведенный выше алгоритм. Это алгоритмы Косарайю, Габова и Тарьяна.

Пример

На данном примере изображен орграф, для которого найдены все три компоненты сильной связности (одна компонента сильной связности — одна закрашенная область, обведенная пунктирной линией).

Ссылки

• Визуализатор алгоритмов поиска компонент сильной связности

Литература

• Роберт Седжвик. Алгоритмы на графах = Graph algorithms. — 3-е изд. — Россия, Санкт-Петербург: «ДиаСофтЮП», 2002. — С. 496. — ISBN 5-93772-054-7

Wikimedia Foundation.2010.

Полезное

Смотреть что такое "Компонента сильной связности графа" в других словарях:

• Компонента сильной связности в орграфе — Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s.… … Википедия
• Компонента связности графа — Несвязный граф с тремя компонентами связности Компонента связности графа некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества … Википедия
• Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
• Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия
• Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
• Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
• Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
• Инцидентность — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
• Мультиграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
• Подграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия