ОПРЕДЕЛЕНИЕ 22.Маршрутом (путем)в графе называется последовательность вида , где v – вершины, e – дуги, . Этот маршрут соединяет вершины и , его длина равна n.
Маршрут называется замкнутым (циклом), если .
Маршрут называется цепью, если в нем все дуги различные (при этом вершины могут повторяться).
Цепь, не являющаяся циклом, называется простой, если в ней нет повторяющихся вершин.
Цикл называется простым, если в нем все вершины (кроме первой и последней) различные.
Следующее утверждение очень простое.
ПРЕДЛОЖЕНИЕ.Если существует маршрут, соединяющий вершины и , то существует и простая цепь, соединяющая эти вершины.
Доказательство состоит в последовательном исключении циклов из маршрута.
Если такой маршрут существует, то говорят, что вершина достижимаиз вершины . Две вершины графа называются взаимно достижимыми, если каждая из них достижима из другой. Для неориентированных графов понятия достижимости и взаимной достижимости совпадают. Взаимная достижимость означает, что в графе есть цикл, содержащий эти вершины.
Бинарное отношение взаимной достижимости на множестве вершин графа, как легко проверить, является рефлексивным, симметричным и транзитивным, т.е. отношением эквивалентности. Как следует из теоремы 3, множество вершин графа распадается на классы эквивалентности.
ОПРЕДЕЛЕНИЕ 23.Классы эквивалентности множества вершин графа по отношению взаимной достижимости называются компонентами сильной связности. Для неориентированных графов слово «сильной» опускается.
Таким образом, компоненту сильной связности можно охарактеризовать следующими свойствами.
- Любые две вершины из этого множества взаимно достижимы.
- Множество вершин нельзя расширить с сохранением этого свойства.
Граф, у которого одна компонента сильной связности называется сильно связным (связным в случае неориентированных графов).
Для выделения в графе компонент сильной связности (или проверки сильной связности графа) удобно использовать матрицу достижимостиD. Элементами этой матрицы размеров p´p являются 0 и 1, причем Dij=1 тогда и только тогда, когда j-я вершина достижима из i-й. j-я и i-я вершины взаимно достижимы тогда и только тогда, когда Dij=Dji=1. Сильная связность графа равносильна тому, что матрица достижимости заполнена единицами.
Опишем алгоритм построения матрицы достижимостипо матрице смежности.
Каждая вершина достижима из самой себя, поэтому на главной диагонали матрицы D расположим 1. Далее последовательно просматриваем уже имеющиеся единицы в матрице D и добавляем единицы следующим образом. Если Dij=1, то в i-ю строку переносим единицы из матрицы смежности, расположенные в j-й строке. Для того, чтобы не просматривать одни и те же единицы по нескольку раз, просмотренные единицы целесообразно отмечать.