Основные определения и теоремы.

Неориентированный граф с числом вершин n> 1 называется деревом, если он связен и не содержит циклов.

Следующая теорема характеризует свойства деревьев, каждое из которых может служить определением дерева.

Теорема 1. Для графа G, имеющего n вершин (n> 1), равносильны следующие свойства:

1. G связен и не содержит циклов;

2. G не содержит циклов и имеет (n-1) ребро;

3. G связен и имеет (n-1) ребро

4. G не содержит циклов, но добавление ребра между любыми его вершинами приводит к образованию цикла;

5. G связен, и все его ребра являются перешейками;

6. Всякая пара вершин G соединена только одной цепью.

Доказательство этой теоремы можно провести, показав цепочку следствий 1→ 2→ 3→ 4→ 5→ 6→ 1.

Доказательство. Если граф G связен и не имеет циклов, то цикломатическое число ν =N-n+1=0, откуда N=n-1, т.е. G не содержит циклов и имеет (n-1) ребро (1→ 2).

Если G не имеет циклов, то ν =0, причем N=n-1, т.е. ν =N-n+P=0, откуда получаем P=1, т.е. G связен и имеет (n-1) ребро (2→ 3).

Если G связен и имеет (n-1) ребро, то ν =N-n+1, N=n-1. Отсюда ν =0, т.е. G не содержит циклов. Если добавить одно ребро, получим связной граф G’ с числом ребер N’=n. Цикломатическое число этого графа ν ’=n-n+1=1, т.е. G’ содержит один цикл(3→ 4).

Если G не содержит циклов, но добавление одного ребра ведет к образованию цикла, то G связен так как в противном случае в графе G должны существовать две вершины X_i и X_j, не соединенные никакой цепью и такие, что добавление ребра(X_i X_j) не привело бы к образованию цикла. Все ребра графа являются перешейками, т.к. удаление любого из них приводит к графу G’, для которого ν ’=N-n+P=0, причем N’=N-1. так как G связен и не содержит циклов, ν ’=N-n+1=0, откуда N=n-1, N’=n-2 и, следовательно, P=2.т.е. G’ не является связным (4→ 5).

Если G связен, то всякая пара его вершин соединена цепью. В силу того, что все ребра G являются перешейками, существует единственная цепь, соединяющая любую пару вершин X_i, X_j, т.к. в противном случае удаление ребра (X_i X_j) не нарушило бы связности графа G (5→ 6).

Если всякая пара вершин G соединена цепью, то G связен. Так как такая цепь единственная, G не содержит циклов: если бы G содержал циклы, то в нем нашлась бы пара вершин X_i, X_j, соединенная более чем одной цепью (6→ 1), что и требовалось доказать.

Ориентированное дерево называется прадеревом.

Несвязный граф, компонентами связности которого являются деревья, называется лесом.

В дальнейшем понадобится следующее определение: подграф G’(X’, U’) содержащий все вершины графа G(X, U), называется частичным графом.

Теорема 2. Граф G(X, U) тогда и только тогда содержит частичный граф, являющийся деревом, когда он связен.

Доказательство. Если граф G содержит частичный подграф-дерево, то, очевидно, он связен, т.к. на основе свойства 6 предыдущей теоремы каждая пара его вершин может быть соединена цепью.

Предположим теперь, что граф связен. Докажем, что он содержит частичный граф-дерево.

Если граф G не содержит циклов, то он сам является деревом по определению. Предположим, что G содержит цикл μ. Вычеркнем из μ любое ребро. Получившийся частичный граф G₁ , будет связным, т.к. удаление из цикла любого ребра не нарушает связности графа. Если G₁ – дерево, доказательство закончено. Если G₁ содержит циклы, то удаляем ребро любого из них и получаем подграф G₂ . Если G₂ не имеет циклов, то он есть дерево и доказательство закончено. Если G₂ содержит циклы, то удаляем ребро одного из них, и.т.д.

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