Связность в графах

Рассмотрим вопрос о связности в графах. Пусть G(X) – неори­ентированный граф. Две вершины х_i и x_j называются связными, если существует цепь S с концами х_i и x_j. Если S проходит через некото­рую вершину x_k более одного раза, то можно удалить цикл в верши­не x_k из цепи S. Отсюда следует, что вершины, связанные цепью, связаны элементарной цепью.

Неориентированный граф называется связным, если любая па­ра его вершин связана. Отношение связности для вершин графа есть отношение эквивалентности
(x_i ~ x_j, х_j ~ х_k Û x_i ~ х_k).

Компонентой связ­ности неориентирован­ного графа G(X) называ­ется подграф Н_А(А) графа G(X) с множеством вер­шин А Ì X и множеством ребер в G(X), инцидент­ных только вершинам из А, причем ни одна вершина x_i Î А не смежна с вершинами из множества Х \ А (рис. 3.12).

Рис. 3.12. Граф с двумя компонентами связности

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

Компонентой сильной связности ориентированного графа G(X) называется подграф Н_А(А) графа G(Х) (подчиняющийся опре­делению сильно связного графа) с множеством вершин А Ì Х и мно­жеством дуг, имеющих начало и конец в А, причем ни одна из вер­шин х_i Î А и х_j Î X \ А не смежны между собой (рис. 3.13).

Рис. 3.13. Ориентированный граф с двумя компонентами сильной связности

Очевидно, что ориентированный граф G(X) сильно связан то­гда и только тогда, когда он имеет одну компоненту связности.

На практике широко используются такие виды графов, как де­ревья и прадеревья.

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

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

Рис. 3.14. Дерево

Лесом называется несвязный граф, каждая компонента связно­сти которого является деревом.

Прадеревом называется ориентированный граф G(X) с корнем х₀ Î X, если в каждую вершину х_i ¹ х₀ (х_i Î X) заходит ровно одна дуга, а в корень х₀ не заходит ни одна дуга. Прадерево не содержит контуров (рис.3.15).

Рис. 3.15. Прадерево