Деревья.

Граф, не содержащий цикла, называют ациклическим или лесом.

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

Т-ма1: Граф – это лес тогда, когда каждое ребро графа – мост.

Док-во:Если G – лес, то в нем нет циклов, следовательно ни одно ребро не входит в цикл, и тогда по лемме все ребра – мосты.

Т-ма 2:Дерево с n-вершинами содержит (n-1) ребер.

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

След.1Пусть в лесе n-вершинами, m-ребер и k-компонент связности, тогда m=n-k.

Док-во: Пусть в i-той компоненте связности леса -вершин и -ребер. Тогда , по теореме2 посчитаем общее число ребер леса. m= ∑(ni-1)=n-k.

След.2Если в лесе число ребер на единицу меньше числа вершин, то этот лес – дерево.

Док-во: следует и сл. 1

Утвер.: Лес – дерево тогда, когда число его ребер на единицу меньше числа его вершин.

След.3В дереве, которое содержит по меньшей мере 2 вершины, не менее двух висячих вершин (вершины степени 1 – листья)

Док-во:Пусть в дереве вершин, тогда оно содержит m=n-1 ребер, в лемме о рукопожатиях Будем считать, что вершины упорядочены по возрастанию степени покажем что: deg (v1)= deg (v2)=1. Если предположить противное, то получим противоречие deg (v1)>1, deg (v2)>=2

. За счет этого док-ся что есть 2 висяч. вершины минимум.

Т-ма 3:Пусть в связном графе число ребер на единицу меньше числа вершин, тогда этот граф дерево.

Док-во: Пусть в G имеется n-вершин, и m=n-1 ребер, по теореме в простом графе m>=n-k, где k-число компонент связности, для G k=1 и имеет место равенство m=n-1 след-но этот граф простой, т. к. в противном случае, удалив все петли и кратные ребра, мы уменьшили бы m не изменив при этом n и k, что привело бы к нарушению нер-ва.

Удаление каждого ребра G приведет к нарушению нер-ва m>=n-k, если при этом не изменится n и k, то по определению любое ребро G-мост и в силу этого G-ациклический граф, поскольку при этом, по условию G связный, то он дерево.

Т-ма 4:Граф – дерево тогда и только тогда, когда любые две вершины соединены одной цепью

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

Т-ма 5: Лес является деревом тогда, когда добавление любого ребра приводит к образованию ровно одного цикла.

Док-во: Пусть ациклич. граф связен, тогда по теореме 4, любые 2 вершины u и v связаны одной простой цепью, и добавление ребра uv приводит к образованию цикла, причем только одного, т. к. если бы их образовывалось хотя бы 2, то объединяя эти циклы, можно было бы получить один, не содержащий uv, а это противоречит ациклич. графа.

Если при добавлении uv обр-ся цикл, то удаляя из него uv получим цепь, связывающую u и v, а это значит u и v связанные, как и любые 2 другие вершины, т. е. граф связен и является деревом.

Т-ма Кэли: Число помеченных деревьев с n-вершинами равно n в степени n-2

Т-ма: У любого связного графа подграф, который явл. остовным деревом

Кодирование деревьев:

Код Прюфера – это сопоставленные дереву набор (a1,a2…a(n-2)), набор упорядоченный, n-кол-во вершин дерева.

Алгоритм кодирования1) i=0;2) Пусть vi- висячая вершина дерева с наименьшей меткой, тогда ai метка смежной с ней вершиной. 3) удалим vi и инцидентное ей ребро. 4) если в дереве осталось > 2-х вершин i++ и к шагу 2, иначе стоп.