3.05.1. Деревья и остовы. Критерии дерева

Деревом Называется связный граф без циклов. Произвольный (не обязательно связный) граф без циклов называется Лесом. Понятно, что лес состоит из деревьев, которые являются для него компонентами связности.

Лемма. В любом дереве порядка имеется по крайней мере две концевые вершины.

Доказательство. Рассмотрим в дереве простую цепь максимальной длины. Это не цикл, так как в дереве вообще нет циклов. Пусть и — начало и конец данной цепи. Тогда и — концевые вершины. Действительно, предположим противное, что, например, не является концевой. Тогда смежна еще с какой-нибудь вершиной помимо — предыдущей в цепи. Если принадлежит цепи, то граф имеет цикл, что невозможно, так как он дерево. Если же не принадлежит цепи, то цепь можно удлинить, добавляя ребро и вершину . А это противоречит тому, что рассматриваемая цепь имеет максимальную длину. Таким образом, утверждение леммы верно.

Теорема. Пусть — -граф. Следующие утверждения равносильны:

A) — дерево;

B) любые две различные вершины графа Соединены единственной простой цепью;

C) — граф без циклов, но если любую пару несмежных вершин соединить ребром, то появится ровно один цикл;

D) — связный граф, но перестанет быть связным после удаления любого ребра;

E) — связный граф, причем .

Доказательство.

А) Þ b). Пусть и — две вершины дерева . По крайней мере одна простая цепь между и существует ввиду связности . Если бы существовала еще хотя бы одна, то объединив их мы получили бы замкнутый маршрут, содержащий цикл, что невозможно, так как — граф без циклов.

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

C) Þ d). — связный граф, иначе соединив ребром две вершины из разных компонент связности, мы не получили бы цикл, что противоречит с). Удалив любое ребро, мы получим несвязный граф, иначе бы удаленное ребро принадлежало циклу, что также противоречит с).

D) Þ a). Достаточно показать, что в нет циклов. Действительно, если бы был хотя бы один цикл, то удаление любого ребра из цикла нарушило бы связность графа .

A) Þ e). Индукция по . При единственным деревом является простая цепь , которая имеет ребро, и равенство очевидно.

Предположим, что утверждение d) верно для любого дерева порядка . Докажем что тогда оно верно и для дерева порядка . Рассмотрим такое дерево. Оно содержит концевую вершину (обозначим ее через), которая существует согласно лемме. Удалим V вместе с инцидентным ей концевым ребром. Полученный граф является деревом порядка и по индукционному предположению имеет ребро. Значит, исходное дерево порядка имело ребер. Тем самым и для исходного дерева требуемое соотношение верно.

E) Þ a). Индукция по . При утверждение а) (то, что — связный граф без циклов, если в нем две вершины и одно ребро) очевидно.

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

Теорема (Кэлли). Число неизоморфных помеченных деревьев порядка Равно .

< Предыдущая		Следующая >