Теоремы о деревьях

Теоремы о соответствиях между неографами о орграфами.

Однако необходимые условия для существования в графе s гамильтоновых маршрутов и циклов до настоящего времени еще не найдены, хотя предложены многочисленные критерии достаточности существования гамильтоновых циклов в графе s.

§ Связный граф s с вершинами |V| › 3 есть гамильтонов, если степень произвольной его вершины degV_i ³ |V| / 2

§ Если для любой пары V и V несмежных вершин графа s с числом вершин |V| ³ 3 выполняется неравенство deg V_i + deg V_j ³ |V|, то граф s - гамильтонов.

§ Утверждение. В турнире (орграф, основанием которого является полный граф) существует гамильтонов путь.

__

§ Каждому орграфу s ₁= ‹V, U › можно одновременно сопоставить неограф s ₂ = ‹V,U › (обратное, очевидно, не всегда верно).

§ Каждому неографу s = ‹V,U› можно сопоставить 3^|U|*2^|V| различных орграфов.

Пример. Пусть

s = ‹ M=2, U =1 ›

ему соответствует 12 орграфов.

6. Для графа T = ‹ V, U › следующие утверждения эквивалентны.

§ Т – дерево, если он связный неограф без циклов.

§ Т – дерево, если любые две вершины в графе Т соединены единственной простой цепью.

§ Т – дерево, если граф связен и имеет |V| - 1 ребер.

§ Т – дерево, если граф не содержит циклов и имеет |V| -1 ребер.

§ Т – дерево, если граф не содержит циклов, но добавление ребра между любыми двумя несмежными вершинами приводит к появлению одного цикла.

§ Т – дерево, если граф связен, но утрачивает это свойство после удаления любого ребра.

Замечание. Эта теорема устанавливает эквивалентность различных свойств дерева, каждое из которых может служить его определением.

Матричные теоремы о покрывающих деревьях.

Теорема Трента:

Число остовых деревьев связного мультиграфа(½ s ½ ³ 2) есть любой главный минор квадратичной матрицы ½ V½ *½ V½, по главной диагонали которой расположены степени вершин, а элементы позиций i,j и ij равны взятому со знаком минус числу ребер, связывающих вершины V_i и V_j.

Пример:

Рассмотрим мультираф.

Матрица Трента

	V1	V2	V3	V4	V5
V1		-1	-2
V2	-1		-1	-1	-1
V3	-2	-1	-4	-1	-1
V4		-1	-1		-3
V5		-1		-3

3 –2 0 0

-2 4 –1 0

₂₂= 0 –1 5 –3 = 76

0 0 –3 4

Это означает, что на исходном графе 76 покрывающих деревьев.

Теорема Кирхгофа (частный случай теоремы Трента, здесь рассматривается простой граф):

_Число остовых деревьев в связном графе s порядка ½ V½ › 2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа В(s).

-1, если V_i и V_J смежны

А_к= 0, если V_i и V_J не смежны и V_i = V_J

degV_i, если V_i › V_J

Замечание:

В матрице Трента и Кирхгофа сумма элементов в любой строке и в любом столбце равна нулю.

Теорема Кэли (1897)(частный случай матричной теоремы Кирхгофа, когда граф s

является полным):

_Число помеченных деревьев порядка ½ V½ равно½ V½ ½ ^{V½ -2}

Замечания:

13. Теорему Кэли легко доказать с помощью дерева a (Т); множество символов М={a _I(T)} длины ½ V½ -2 можно рассматривать как множество картежей из элементов- номеров вершин, т.е.

½ М½ =½ V*V*…*V½ =½ V½ ½ ^{V½ -2}

½ V½ -2 раз

Пример:

Для графа К₅(полный граф с пятью вершинами) число покрывающих деревьев равно

М= 5^5-2 =125

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

15. Число неизоморфных корневых покрывающих деревьев T_n c ½ V½ =n вершинами определяется не перечисляющимся рядом:

T(x)=S T_nxⁿ

Этот ряд удовлетворяет функциональному уравнению:

T(x)= x exp S T(x²)

16. Число неизолированных покрывающих деревьев (необязательно корневых) t_n определяется перечисляющимся рядом

t(x)=S t_ixⁱ

Можно представить и в виде перечисляющегося ряда для корневых деревьев:

t(x)= T(x)- 0,5*[T²(x)- T(x²)]

Очевидно, что функциональные уравнения для Т(х) и t(x) позволяют вычислять T_n

и t_n для конкретных значений n

Пример:

Для полного графа s _4,6(К₄) число покрывающих деревьев равно 4^4-2=16

Представим их

Дата добавления: 2014-01-06