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

Определение: Ребро е в графе 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) справедливо для всех графов с числом вершин < p. Шаг: покажем, что (q-p+1=0) справедливо, для всех графов с числом вершин p. Пусть у связного графа G есть p вершин. Удалим e=(u,v) из G, сохранив его концы. Получившийся граф G’ = (G-e) несвязен, ибо если он связен, то между u и v в G’ и ⇒ в G есть простая цепь. Другая простая цепь в G между u и v есть ребро е. Противоречие в единственности простой цепи в G между u и v. Граф G’ несвязен и имеет в точности 2 компоненты связанности. Число вершин в каждой компоненте p1, p2 и число ребер q1,q2 причем p= p1+p2 и q=q1+q2+1. По предположению индукции qi-pj+1 =0, i=1,2.., тогда для графа G: q-p+1=(q1+q2+1) – (p1+p2)+1 = (q1-p1 +1) + (q2-p2 +1) = 0. Равенство q-p+1 = 0 доказано. Граф G связен и q-p+1=0. (3→4): Покажем, что G ацикличен. Допустим противное: граф G – цикличен, тогда G имеет простой цикл С длины n ≤ q (длина цикла = равна количеству ребер). Цикл С имеет n вершин и n ребер. Пусть U=(u1, u2,…,up-n) – есть оставшиеся вершины в G (т.е. вершины вне цикла C). Пусть v – вершина из цикла С. Т.к. граф G связен, то вершина v цикла С может быть соединена с любой вершиной ui из U. Пусть [u1,v],…,[un-p,v] – есть геодезические (т.е. цепи наименьшей длины). Ребра E’=(e1, e2,…,e_p-n), лежащие на этих геодезических цепях и принадлежащие вершинам u1, u2,…,u_p-n соответственно попарно различны, как принадлежащие различным вершинам.

Пусть G’ = C U E’. Т.к. G’ ⊆ G, то число ребер в G’ n+(p-n) ≤ q ⇒ p ≤ q ⇒ p-q ≤ 0 ⇒ q-p ≥ 0 ⇒ q-p+1 ≥ 1 противоречие с q-p+1 =0 ⇒ граф G ацикличен и q-p+1 = 0.

(4→5): Пусть граф G – ацикличен и q-p+1 = 0. Покажем сначала, что граф G – есть дерево. Т.к. граф G ацикличен, каждая его компонента связности есть дерево. Пусть G имеет k компонент связанности (т.е. деревьев Ti) (причем, Ti имеет pi вершин и qi ребер). Тогда граф G имеет p = ∑_i=1…kpi вершин и q = ∑_i=1…kqi ребер. Т.к. для каждого дерева Ti по (1→3) имеем qi – pi +1 = 0, то для графа G: ∑_i=1…k (qi — pi +1) = ∑_i=1…kqi — ∑_i=1…kpi + ∑_i=1…k1 = q – p + k = 0, что вместе с q – p + 1 = 0 дает k=1, т.е. граф G имеет одну компоненту связности (k=1) и потому граф G — дерево. Соединим в дереве G любую пару несмежных вершин u и v ребром e = (u,v). Ребро е вместе с единственной (по 1→2) простой цепью [u,v] в G дает единственный простой цикл в G+{e}.

Итак:
1) граф G – ацикличен.
2) Если любую пару несмежных вершин в G соединить ребром е, то получившийся граф G+{e} будет иметь в точности один простой цикл.
(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 – {e} имеет р вершин и q-1 ребер. Тогда (q-1)-p+1=(q-p+1)-1=0 ⇒ граф G’ есть дерево. Восстановим удаленное ребро е в G’ и получим связный граф G, который имеет единственный простой цикл виде условий 1 и 5 теоремы.
(Достаточность)⇐: пусть теперь связный (p,q) – граф G имеет единственный простой цикл С. Удалим из G его циклическое ребро е, лежащее в С. Полученный связный граф G’ = G – {e}не имеет простых циклов, ибо если 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 и указанием единственного цикла, который через эту хорду проходит.

Комментарии запрещены.