- 54 -
Граф называется неразделимым, если он связный и не имеет точек сочленения (например, граф на Рис. 11, а неразделим). Граф, имеющий хотя бы одну точку сочленения, является разделимым и называется сепарабельным. Он разбивается на блоки, каждый из котооых представляет собой максимальный неразделимый подграф (на Рис. 14, в показаны блоки B1,B2,B3 графа Рис. 14, б).
Каждое ребро графа, как и каждая вершина (за исключением точек сочленения), принадлежат только одному из его блоков. Более того, только одному блоку принадлежит и каждый простой цикл. Отсюда следует, что совокупность блоков графа представляет собой разбиение множеств ребер и простых циклов на непересекающиеся подмножества.
Рис. 14. Разделимые графы:
а - с точкой сочленения; б - с мостом; в - блоки B1 - B3 графа с мостом
В ряде приложений теории графов блоки можно рассматривать как компоненты. Это обычно допустимо, когда связи блоков посредством точки сочленения несущественны или когда существенные свойства графа связаны только с его простыми циклами (контурами). В таких случаях можно рассматривать несвязный граф как связный разделимый граф, который образуется путем такого объединения компонент, чтобы каждая из них была блоком (это всегда можно сделать, объединив, например, по одной вершине каждого блока в точку сочленения). Подобные операции используются при рассмотрении графов электрических цепей.
12. Деревья и лес.Особый интерес представляют связные ациклические графы, называемые деревьями. Дерево на множестве р вершин всегда содержит q = р - 1 ребер, т. е. минимальное количество ребер, необходимое для того, чтобы граф был связным. Действительно, две вершины связываются одним ребром, и для связи каждой последующей вершины с предыдущими требуется ребро, следовательно, для связи р вершин необходимо и достаточно р - 1 ребер.
При добавлении в дерево ребра образуется цикл, а при удалении хотя бы одного ребра дерево распадается на компоненты, каждая из которой представляет собой также дерево или изолированную вершину. Несвязный граф, компоненты которого являются
- 55 -
деревьями, называется лесом (лес из к деревьев, содержащий р вершин, имеет в точностир - к ребер). Сказанное иллюстрируется на примере дерева (Рис. 15, а), которое превращается в циклический граф добавлением ребра (Рис. 15, б) и распадается на лес из двух деревьев T1 и T2 при удалении ребра е (Рис. 15, в).
Рис. 15. Дерево (а), образование цикла при введении дополнительного ребра (б) и лес, который образуется после удаления ребра е (в).
Обычно деревья считаются существенно различными, если они не изоморфны. На Рис. 16 показаны все возможные различные деревья с шестью вершинами. С увеличением числа вершин количество различных деревьев резко возрастает (например, при р = 20 их насчитывается около миллиона). Среди различных деревьев выделяются два важных частных случая: последовательное дерево, представляющее собой простую цепь, и звездное дерево, в котором одна из вершин (центр) смежна со всеми остальными вершинами.
Рис. 16. Существенно различные деревья с шестью вершинами.
Рис. 17. Прадерево с корнем v0.
Рассматриваются также деревья с ориентированными ребрами (дугами). Ориентированное дерево называется прадеревом с корнем v0 , если существует путь между вершиной v0 любой другой его вершиной (Рис. 17). Ясно, что прадерево имеет единственный корень.
До сих пор рассматривались деревья как минимальные связные графы на множестве р вершин. Важное значение имеет и другая точка зрения, когда деревья или лес являются частями некоторого графа, т. е. образуются из его ребер. Любая связная совокупность ребер, не содержащая контуров, вместе с инцидентными им вершинами образует дерево графа (Рис. 18, а). Если такое дерево является суграфом (содержит все вершины графа), то оно называется покрывающим деревом или остовом (Рис. 18, б). Так как петля
- 56 -
представляет собой простейший цикл, состоящий из единственного ребра, то она не может входить в состав любого дерева графа.
Ребра графа, которые принадлежат его дереву, называют ветвями. Если дерево покрывает граф, то множество ребер графа разбивается на два подмножества: подмножество ветвей и подмножество ребер дополнения дерева, называемых хордами. При этом связный (р, q) - граф содержит v = р - 1 ветвей и σ = q - р + 1 хорд. Если граф несвязный, то совокупность, остовов R его компонент образует покрывающий лес. В этом случае ν = р - R и σ = q - р + R.