Рассмотрим вопрос о связности в графах. Пусть G(X) – неориентированный граф. Две вершины хi и xj называются связными, если существует цепь S с концами хi и xj. Если S проходит через некоторую вершину xk более одного раза, то можно удалить цикл в вершине xk из цепи S. Отсюда следует, что вершины, связанные цепью, связаны элементарной цепью.
Неориентированный граф называется связным, если любая пара его вершин связана. Отношение связности для вершин графа есть отношение эквивалентности
(xi ~ xj, хj ~ хk Û xi ~ хk).
Компонентой связности неориентированного графа G(X) называется подграф НА(А) графа G(X) с множеством вершин А Ì X и множеством ребер в G(X), инцидентных только вершинам из А, причем ни одна вершина xi Î А не смежна с вершинами из множества Х \ А (рис. 3.12).
Рис. 3.12. Граф с двумя компонентами связности
Ориентированный граф называется сильно связным, если для любой пары вершин найдется путь, соединяющий их.
Компонентой сильной связности ориентированного графа G(X) называется подграф НА(А) графа G(Х) (подчиняющийся определению сильно связного графа) с множеством вершин А Ì Х и множеством дуг, имеющих начало и конец в А, причем ни одна из вершин хi Î А и хj Î X \ А не смежны между собой (рис. 3.13).
|
|
Рис. 3.13. Ориентированный граф с двумя компонентами сильной связности
Очевидно, что ориентированный граф G(X) сильно связан тогда и только тогда, когда он имеет одну компоненту связности.
На практике широко используются такие виды графов, как деревья и прадеревья.
Деревом называется конечный связный неориентированный граф, состоящий, по крайней мере, из двух вершин и не содержащий циклов. Такой граф не имеет петель и кратных ребер (рис. 3.14).
Ветвями дерева называются ребра графа, входящие в дерево. Хордами дерева называются ребра, входящие в граф, дополнительный к данному дереву. Лагранжевым деревом называется дерево, все ветви которого имеют общую вершину.
Рис. 3.14. Дерево
Лесом называется несвязный граф, каждая компонента связности которого является деревом.
Прадеревом называется ориентированный граф G(X) с корнем х0 Î X, если в каждую вершину хi ¹ х0 (хi Î X) заходит ровно одна дуга, а в корень х0 не заходит ни одна дуга. Прадерево не содержит контуров (рис.3.15).
Рис. 3.15. Прадерево