Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

2. Связность. Компоненты связности
Определение. Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. (Для орграфа то же).
Подграф наз. собственным, если он отличен от самого графа.
Говорят, что вершина w орграфа D (графа G) достижима из верш. v, если либо w=v, либо существует путь (маршрут) из v в w.
Граф (орграф) наз связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v и w.
Орграф наз односторонне связным, если для любых двух его вершин по крайней мере одна достижима из другой.
Псевдографом, ассоциированным с ориентированным псевдографом D=(V,X) наз. псевдограф G=(V,X₀), в котором X₀ получается из X заменой всех упорядоченных пар (v,w) на неупорядоченные {v,w}.

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

Матрицы достижимости и связности. Пусть A(D) – матрица смежности ориентированного псевдографа D=(V,X) (или псевдографа G=(V,X)), где V={v₁,…, v_n}. Обозначим через A^k=[a^(k)_ij] k-ю степень матрицы смежности A(D).

Утверждение. Элемент a^(k)_ij матрицы A^k ориентированного псевдографа D=(V,X) (псевдографа G=(V,X)) равен числу всех путей (маршрутов) длины k из v_i в v_j.
Для k=1 очевидно в силу построения матрицы A(D).
Пусть это справедливо для n=k-1. Т.е. в матрице A^k-1 в i-той строке на l-том месте стоит число, означающее кол-во маршрутов из v_i в v_l длины k1. Столбец под номером j матрицы A содержит числа, означающие кол-во дуг (ребер) из v_l в v_j (l-номер строки). Тогда скалярное произведение i-той строки матрицы A^k-1 на j-тый столбец матрицы A равен сумме произведений. Каждое произведение означает кол-во путей из v_i в v_j, проходящих через v_l на предпоследнем шаге. В сумме получается общее кол-во.