Читать «Математический аппарат инженера» онлайн - страница 34

- 54 -

Граф называется неразделимым, если он связный и не имеет точек сочленения (например, граф на Рис. 11, а неразделим). Граф, имеющий хотя бы одну точку сочленения, является разделимым и называется сепарабельным. Он разбивается на блоки, каждый из котооых представляет собой максимальный неразделимый подграф (на Рис. 14, в показаны блоки B₁,B₂,B₃ графа Рис. 14, б).

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

Рис. 14. Разделимые графы:

а - с точкой сочленения; б - с мостом; в - блоки B₁ - B₃ графа с мостом

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

12. Деревья и лес.Особый интерес представляют связные ациклические графы, называемые деревьями. Дерево на множестве р вершин всегда содержит q = р - 1 ребер, т. е. минимальное количество ребер, необходимое для того, чтобы граф был связным. Действительно, две вершины связываются одним ребром, и для связи каждой последующей вершины с предыдущими требуется ребро, следовательно, для связи р вершин необходимо и достаточно р - 1 ребер.

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

- 55 -

деревьями, называется лесом (лес из к деревьев, содержащий р вершин, имеет в точностир - к ребер). Сказанное иллюстрируется на примере дерева (Рис. 15, а), которое превращается в циклический граф добавлением ребра (Рис. 15, б) и распадается на лес из двух деревьев T₁ и T₂ при удалении ребра е (Рис. 15, в).

Рис. 15. Дерево (а), образование цикла при введении дополнительного ребра (б) и лес, который образуется после удаления ребра е (в).

Обычно деревья считаются существенно различными, если они не изоморфны. На Рис. 16 показаны все возможные различные деревья с шестью вершинами. С увеличением числа вершин количество различных деревьев резко возрастает (например, при р = 20 их насчитывается около миллиона). Среди различных деревьев выделяются два важных частных случая: последовательное дерево, представляющее собой простую цепь, и звездное дерево, в котором одна из вершин (центр) смежна со всеми остальными вершинами.