1. Деревья. Характеризация дерева.

Деревом называется связный граф, не содержащий циклов. Любой граф без циклов называется ациклическим (или лесом). Таким образом, компонентами леса являются деревья. Существует несколько вариантов определения дерева; некоторые из них отражены в следующей теореме.

Теорема 10.1. Для (n, m)--графа G следующие утверждения эквивалентны:

1) G — дерево;

2) G — связный граф и m = n – 1;

3) G — ациклический граф и m = n – 1;

4) любые две несовпадающие вершины графа G соединяет единственная простая цепь;

5) G — ациклический граф, обладающий тем свойством, что если, какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.

 1) 2) Воспользуемся индукцией по n. При n = 1 утверждение тривиально. Пусть n > 1, e  EG. В дереве G нет циклов, следовательно, согласно утверждению 4.5, граф G – e имеет ровно две компоненты T₁ и T₂, каждая из которых есть дерево. Пусть дерево T_i является (n_i, m_i)-графом, i = 1, 2. По индуктивному предположению верно равенство

m_i = n_i – 1 (1)

Далее имеем m = m₁ + m₂ + 1 = (n₁ – 1) + (n₂ – 1) + 1 = (n₁ + n₂ ) – 1 = n – 1.

2) 3) Граф G связен и m = n – 1. Нужно доказать, что в G нет циклов. Пусть, напротив, в графе G есть цикл и пусть e — ребро этого цикла. Тогда граф G – e связен (по утверждению 4.5) и имеет n – 2 ребра, что противоречит теореме 4.6. Следовательно, G — ациклический граф.

3) 4) Пусть k — число компонент графа G. Пусть, далее, компонента T_i является (n_i, m_i)-графом. Так как T_i — дерево, то верно равенство (1). Теперь имеем n – 1 = m = m₁ + m₂ +…+ m_k = (n₁ – 1) + (n₂ – 1) +…+ (n_k – 1) = (n₁ + n₂ + …+ n_k) – k = n – k, т. е. k = 1. Итак, G — связный граф и потому любые несовпадающие вершины и соединены в нем простой цепью. Если бы в G были две несовпадающие простые (u, v)-цепи, то согласно утверждению 4.1в их объединение содержало бы цикл. Следовательно, каждые две вершины соединены единственной простой цепью.

4) 5) Пара несовпадающих вершин, принадлежащих одному циклу, соединена по меньшей мере двумя простыми цепями. Следовательно, граф G ациклический. Пусть u и v — две его несмежные вершины. Присоединим к графу G ребро e = uv. В G есть простая (u, v)-цепь, которая в G + e дополняется до цикла. В силу утверждения 4.1г этот цикл единственный (иначе в G после выбрасывания e из G + e оставался бы цикл).

5) 1) Нужно доказать, что граф G связен. Если бы вершины u и v принадлежали разным компонентам графа G, то граф G + uv не имел бы циклов, что противоречит утверждению 5 теоремы. Итак, G связен и потому является деревом. 

Следствие 10.2. В любом дереве порядка n  2 имеется не менее двух концевых вершин.

 Пусть d₁, d₂, …, d_n — степенная последовательность дерева. Тогда d₁ + d₂ +…+ d_n = 2n – 2 (лемма о рукопожатиях) и все d_i > 0. Следовательно, хотя бы два числа из последовательности степеней вершин равны 1. 

Теорема 10.3. Центр любого дерева состоит из одной или из двух смежных вершин.

 Доказательство проведем индукцией по числу вершин дерева. Очевидно, что концевые вершины дерева T являются центральными только для T = K₁ или T = K₂. Пусть T — дерево порядка n > 2. Удалив из T все концевые вершины, получим дерево T’, в котором по предположению индукции центр состоит из одной или из двух смежных вершин. Заметим, что для любой вершины дерева ее эксцентриситет всегда равен расстоянию до некоторой висячей вершины. Тогда эксцентриситет каждой вершины в T’ на единицу меньше ее эксцентриситета в дереве T. Следовательно, центры деревьев T и T’ совпадают. 

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

Следствие 10.4. Число ребер произвольного (n, m)- графа G, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно , где — число компонент связности графа G.

 Если (n₁, m₁)-граф H является одной из компонент графа G, то для превращения ее в остовное дерево нужно удалить m₁ – (n₁ – 1) подходящих ребер. Суммируя по всем k компонентам, получим требуемое. 

Число (G) = m – n + k называется цикломатическим числом графа G. Очевидно следствие

Следствие 10.5. а) граф является лесом тогда и только тогда, когда (G) = 0; б) граф G имеет единственный цикл тогда и только тогда, когда (G) = 1; с) граф, в котором число ребер не меньше, чем число вершин, m  n, содержит цикл.

Очевидно, что число остовов в K_n равно числу помеченных деревьев порядка n. В 1897 г. А. Кэли показал, что число помеченных деревьев порядка n равно n^n–2.