Теоремы о деревьях.
Теоремы о соответствиях между неографами о орграфами.
Однако необходимые условия для существования в графе s гамильтоновых маршрутов и циклов до настоящего времени еще не найдены, хотя предложены многочисленные критерии достаточности существования гамильтоновых циклов в графе s .
§ Связный граф s с вершинами |V| › 3 есть гамильтонов, если степень произвольной его вершины degVi ³ |V| / 2
§ Если для любой пары V и V несмежных вершин графа s с числом вершин |V| ³ 3 выполняется неравенство deg Vi + deg Vj ³ |V|, то граф s - гамильтонов.
§ Утверждение. В турнире ( орграф, основанием которого является полный граф) существует гамильтонов путь.
__
§ Каждому орграфу s 1= ‹V, U › можно одновременно сопоставить неограф s 2 = ‹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 равны взятому со знаком минус числу ребер, связывающих вершины Vi и Vj.
Пример:
Рассмотрим мультираф.
Матрица Трента
| 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
22= 0 –1 5 –3 = 76
0 0 –3 4
Это означает, что на исходном графе 76 покрывающих деревьев.
Теорема Кирхгофа (частный случай теоремы Трента, здесь рассматривается простой граф):
_Число остовых деревьев в связном графе s порядка ½ V½ › 2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа В(s ).
-1, если Vi и VJ смежны
Ак= 0, если Vi и VJ не смежны и Vi = VJ
degVi, если Vi › VJ
Замечание:
В матрице Трента и Кирхгофа сумма элементов в любой строке и в любом столбце равна нулю.
Теорема Кэли (1897)(частный случай матричной теоремы Кирхгофа, когда граф s
является полным):
_Число помеченных деревьев порядка ½ V½ равно½ V½ ½ V½ -2
Замечания:
13. Теорему Кэли легко доказать с помощью дерева a (Т); множество символов М={a I(T)} длины ½ V½ -2 можно рассматривать как множество картежей из элементов- номеров вершин, т.е.
½ М½ =½ V*V*…*V½ =½ V½ ½ V½ -2
½ V½ -2 раз
Пример:
Для графа К5(полный граф с пятью вершинами) число покрывающих деревьев равно
М= 55-2 =125
14. Существенно различные (неизоморфные) покрывающие деревья подсчитывают комбинаторными методами с помощью генератрис (производящих функций)
15. Число неизоморфных корневых покрывающих деревьев Tn c ½ V½ =n вершинами определяется не перечисляющимся рядом:
T(x)=S Tnxn
Этот ряд удовлетворяет функциональному уравнению:
T(x)= x exp S T(x2)
16. Число неизолированных покрывающих деревьев (необязательно корневых) tn определяется перечисляющимся рядом
t(x)=S tixi
Можно представить и в виде перечисляющегося ряда для корневых деревьев:
t(x)= T(x)- 0,5*[T2(x)- T(x2)]
Очевидно, что функциональные уравнения для Т(х) и t(x) позволяют вычислять Tn
и tn для конкретных значений n
Пример:
Для полного графа s 4,6(К4) число покрывающих деревьев равно 44-2=16
Представим их