Деревья, их характеристика, каркасы (остовы)

Определение: Дерево – есть связный граф, не имеющий циклов. Лес – Множество деревьев.

Определение: Ребро е в графе G называется циклическим, если оно принадлежит какому-либо циклу графа G, и ациклическим в противном случае. Граф G ацикличен, если каждое его ребро ациклично. (G – не имеет циклов.)

Замечание: при удалении из связного графа циклического ребра граф остается связным, при удалении ациклического ребра – несвязным. Каждая компонента связности леса, есть дерево. Пусть G – есть связанный граф, тогда Следствие утверждения эквивалентны. 1) Граф G – есть дерево. 2) Граф G – не имеет циклов. 3) Граф G не имеет циклических ребер. 4) Все ребра графа G – ацикличны. 5) Граф G – ацикличен.

Характеристические свойства деревьев

Теорема: для ∀ (p,q) графа G следующие утверждения эквивалентны: 1) Граф G – есть дерево. 2) Любая пара вершин в G соединена единственной цепью. 3) Граф G – связен и q-p+1 = 0 4) Граф G – ацикличен и q-p+1 = 0 5.1) Граф G – ацикличен, 5.2) Если любую пару несмежных вершин G соединить ребром е, то получившийся Граф G+ будет иметь в точности один простой цикл.

Доказательство (1 →2): пусть граф G – есть дерево. Т.к. граф G- связен, то всякие u,v в G соединимы простой цепью z. Эта цепь единственна, ибо при наличии другой цепи z’ между u и v получим, что граф G имеет цикл, которого в дереве быть не может.

(2→3): Т.к. любая пара вершин в G соединима единственной простой цепью, то граф G — связен. Равенство q-p+1 = 0 докажем индукцией по числу p вершин в G. Базис: p=1. Т.к. граф состоит из единственной вершины, то q-p+1=0-1+1 = 0 Предположение: пусть (q-p+1=0) справедливо для всех графов с числом вершин

Итак: 1) граф G – ацикличен. 2) Если любую пару несмежных вершин в G соединить ребром е, то получившийся граф G+ будет иметь в точности один простой цикл. (5→1): пусть выполнены условия (5). Граф G связен, ибо, если граф G несвязен, то добавляя к G ребро е между двумя компонентами связности получим ацикличный граф, не имеющий циклов. Противоречие с условием (5) ⇒ граф G связен и ацикличен, т.е. G – есть дерево.

Следствие 1: Связный (p,q) – граф G есть дерево ⇔ q-p+1 = 0. Доказательство следует из того, что по теореме условия (1) и (3) – эквивалентны. Следствие 2: Пусть (p,q) – граф G – связен. Тогда G имеет единственный простой цикл ⇔ q-p+1 = 1. (Необходимость)⇒: Пусть связный (p,q) – граф G удовлетворяет условию q – p + 1=0, следовательно граф G имеет циклическое ребро е. Удалим из G это циклическое ребро е, входящее в некоторый простой цикл С. Получившийся связный граф G’ = G – имеет р вершин и q-1 ребер. Тогда (q-1)-p+1=(q-p+1)-1=0 ⇒ граф G’ есть дерево. Восстановим удаленное ребро е в G’ и получим связный граф G, который имеет единственный простой цикл виде условий 1 и 5 теоремы. (Достаточность)⇐: пусть теперь связный (p,q) – граф G имеет единственный простой цикл С. Удалим из G его циклическое ребро е, лежащее в С. Полученный связный граф G’ = G – не имеет простых циклов, ибо если G’ имеет простой цикл С’, то G имеет 2 простых цикла C и C’, отличающихся ребром е: цикл С имеет ребро е, а цикл С’ нет. Следовательно, граф G’ есть дерево с тем же числом вершин р. Для дерева G’ число q-1-p+1=0, откуда q-p+1=1

Замечание: выберем в дереве T произвольную вершину V (корень дерева) и построим от нее граф T вниз. Получаем изображение для T, в котором вершины группируются по ярусам.

Каркасы и хорды в связном графе

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

Замечание: Каркас графа G можно получить последовательно стирая (выбрасывая) из G его циклические ребра. Каркас графа G содержит все ациклические ребра в G.

Замечание: Каркас в графе G можно получить также последовательным добавлением ребер в G произвольно взятому начальному ребру G, проделывая операцию добавления каждого нового ребра, избегая появления цикла (пока это возможно). Получившееся дерево есть каркас. Если граф G является нагруженным (каждому ребру приписано какое-либо неотрицательное число – его вес), то наименьший каркас (каркас с наименьшей суммой весов ребер каркаса) может быть найден последовательным добавлением ребер в G наименьшего веса, избегая появления циклов вплоть до дерева, которое является наименьшим каркасом.

Определение: Если K=(V,E0) есть каркас для графа G=(V,E), то хорда есть произвольное ребро из E-E0.

Замечание: множество хорд есть семейство удаленных в процессе построения каркаса K циклических ребер. Каждая хорда соответствует некоторому простому циклу в G.

Утверждение: Число хорд в связанном (p,q) — графе G=(V,E) равно q-p+1. Доказательство: Пусть (p,q’) — граф K=(V,E0) есть каркас связного (p,q) графа G=(V,E). Т.к. каркас K – есть дерево, то q’-p+1=0. Поэтому число хорд в графе G равно v=|E| (число ребер) — |E0| = q –q’ = q – q’ + (q’ – p + 1) = q – p + 1. Доказано.

Замечание: Каркас К имеет число ребер q’ = q — v = q‘ – (q – p +1) = p-1

Чтобы сделать две вершины в связном графе G несвязными, достаточно удалить из G множество хорд и одно ребро, принадлежащее одной из двух этих вершин на пути между ними.

Замечание: множество хорд графа G с принадлежащими им простыми циклами в G составляют фундаментальную систему циклов в G. ФСЦ может быть построена также последовательным добавлением каждой хорды к каркасу графа G и указанием единственного цикла, который через эту хорду проходит.