Связность графа. Компоненты связности. Матрица связности

Определение: Граф (орграф) называется связным(сильно связным), если для любых двух его вершин u,v существует маршрут (путь), соединяющий u,v (из u в v).

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

Определение: Псевдографом,ассоциированнымс ориентированнымпсевдографом Д(V, X), называется псевдограф G(V, X₀), в котором X₀ получается из X заменой всех упорядоченных пар (u,v) на неупорядоченные

Определение: Орграф называется слабосвязным, если связным является ассоциированный с ним псевдограф.

Определение: Граф (орграф), не являющийся связным (сильно связным), называется несвязным.

Определение: Компонентойсвязности (сильной связности) графа, G (орграфа Д), называют его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (орграфа Д).

Количество компонент связности (сильной связности) будем обозначать через p(G) (p(Д))

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

Определение: Вершина графа, удаление которой увеличивает число компонент связности, называется разделяющей (или точкой сочленения).

Утверждение. Если Д’ орграф, полученный в результате удаления нескольких вершин из орграфа Д, то А(Д’) получается из А(Д) в результате удаления строк и столбцов, соответствующих удаленным вершинам.

Замечание. Аналогичное утверждение справедливо и для произвольных псевдографов.

Пусть Д=(V,X) орграф, V={v₁,…,v_n} – множество вершин.

Определение: Матрицейдостижимости орграфа Д называется квадратная матрица T(Д)=[t_ij] порядка n, у которой

Определение: Матрицейсильнойсвязности орграфа Д называется квадратная матрица S(Д)=[s_ij] порядка n, у которой

Определение: Матрицейсвязности графа G называется квадратная матрица S(G)=[s_ij] порядка n, у которой

Утверждение 1. Пусть дан граф G= (V,X) V={v₁,…,v_n} Пусть А – матрица смежности. Тогда

S(G)= sign(E+A+A²+…+A^n-1)=E A ….

где Е – единичная матрица порядка n.

Утверждение 2. Пусть дан орграф Д= (V,X) V={v₁,…,v_n} А – матрица смежности. Тогда

1) Т(Д)= sign(E+A+A²+…+A^n-1)=E A ….

2) S(Д)= Т(Д) [Т(Д)]^T, где [Т(Д)]^T – матрица транспонированная Т(Д).