29. Маршруты, циклы, цепи. Достижимость и связность (матрицы достижимости, контрдостижимости, связности).

Пусть G=<M,R> - граф. Последовательность a₁,u₁,a₂,u₂,…,u_n,a_n+1, где , называется маршрутом, соединяющим вершины a₁ и a_n+1, если u_i=(a_i,a_i+1). Число n дуг в маршруте называется его длиной.

Пусть G – неорграф. Маршрут (a₁,a_n+1) называется цепью, если все ребра [a₁,a₂],…,[a_n,a_n+1] различны, и простой цепью, если все его вершины, кроме, возможно, первой и последней, различны. Маршрут называется циклическим, если a₁=a_n+1. Циклическая цепь называется циклом, а циклическая простая цепь – простым циклом.

Пусть G – орграф. Маршрут называется путем, если все его дуги различны. Путь называется контуром, если a₁=a_n+1. Граф, не имеющий контура, называется бесконтурным. Вершина b называется достижимой из вершины a, если существует (a,b) – путь.

Неорграф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Граф G называется связным, если соответствующий ему неорграф F(G) тоже является связным. Граф G называется сильно связным, если для каждой пары различных вершин a и b существуют (a,b)-маршрут и (b,a)-маршрут. Аналогично определяются понятия связности и сильной связности для мультиграфов.

Всякий максимальный по включению (сильно) связный подграф данного графа называется его (сильной) связной компонентой или (сильной) компонентой связности.

Теорема: Любой граф представляется в виде объединения непересекающихся связных (сильных) компонент. Разложение графа на связные (сильные) компоненты определяется однозначно.

Теорема: Если A_G – матрица смежности графа G, то (i,j)-й элемент матрицы есть число (a_i,a_j)-маршрутов длины k.

Следствие: 1) В графе G мощности n тогда и только тогда существует (a_i,a_j)-маршрут (a_i≠a_j), когда (i,j)-й элемент матрицы не равен нулю.

2) В графе G мощности n тогда и только тогда существует цикл, содержащей вершину a_i, когда (i,i)-й элемент матрицы не равен нулю.

Образуем из матрицы (b_ij)=E+A_G+A_G²+…+A_G^n-1 матрицу C=(c_ij) порядка n по следующему правилу: . Матрица С называется матрицей связности, если G – неорграф, и матрицей достижимости, если G-орграф.

Определим матрицу контрдостижимости Q=(q_ij): . Причем Q=C^T.

Рассмотрим матрицу сильных компонент S=C*Q, где операция * означает поэлементное произведение матриц С и Q: s_ij=c_ij•q_ij. Таким образом, матрица S является матрицей отношения эквивалентности E: выполнимо a_iEa_j тогда и только тогда, когда a_i и a_j находятся в одной сильной компоненте.