Полином на Тута

Полином на Тута - най-общата характеристика, описваща комбинаторните свойства на графика.

Коректността не е очевидна от тази дефиниция: защо получената функция не зависи от реда на отстраняване на ръба? Ако обаче дефиницията е правилна, [math] T_G [/ math] очевидно е полином в две променливи с неотрицателни целочислени коефициенти. Ще докажем верността, като свържем полинома на Tut с друг полином - полином на ранга на Уитни (Уитни ранг полином).

Сега дефинираме самия полином на ранга:

Експонентите във формулата на полинома на ранга също имат някакво значение. [Math] \ rho (E) - \ rho (A) [/ math] е равно на [math] c (G (A)) - c (G) [/ math], т.е. увеличаване на броя на свързаните компоненти поради прехода към набора от ръбове [math] A [/ math]. Ще обозначим тази стойност с [math] \ rho ^ (A) [/ math] и ще я наречем числото важно за [math] A [/ math] ръбове. (Важно е да ги добавите към [math] A [/ math], за да получите толкова компоненти за свързване, колкото са били първоначално).
Стойността [математика] | A | - \ rho (A) [/ math] ще бъде наречен номер ненужни ръбове: това е колко ръбове могат да бъдат изпуснати от множеството [math] A [/ math] без промяна на броя на свързаните компоненти. Ще обозначим тази стойност с [math] \ overline (A) [/ math] .

След това доказваме следната техническа лема:

Свиването на ръба [math] e [/ math] в никакъв случай не променя броя на свързаните компоненти, следователно [math] \ rho ^ (A ') = \ rho ^ _ (A) [/ math]. Ако [math] e [/ math] не е цикъл, тогава свиването също не променя броя на допълнителните ръбове, откъдето [math] \ overline (A ') = \ overline> (A) [/ math] .
Ако [math] e [/ math] не е мост, тогава премахването на ръба [math] e [/ math] не променя броя на свързаните компоненти, откъдето [math] \ rho (A) = \ rho _2 (A ) [/ math] и [math] \ rho (E) = \ rho _2 (E \ backslash) [/ math]. Замествайки тези равенства във формулите за [math] \ rho ^ [/ math] и [math] \ overline [/ math], получаваме [math] \ rho ^ (A ') = \ rho ^ _ (A) [/ math] и [math] \ overline (A ') = \ overline> (A) [/ math], както се изисква.
Ако [math] e [/ math] е мост, тогава графиката [math] G (A ') [/ math] има един компонент по-малко свързаност от [math] G (A) [/ math], откъдето [math] \ rho ^ (A ') = \ rho ^ (A) - 1 [/ math]. В този случай ръбът [math] e [/ math] няма да бъде излишен [math] A '[/ math], следователно [math] \ overline (A') = \ overline (A) [/ math] .
Ако [math] e [/ math] е цикъл, тогава елиминирането му не променя броя на свързаните компоненти, следователно [math] \ rho ^ (A ') = \ rho ^ (A) [/ math]. По същата причина [math] e [/ math] е излишен, откъдето [math] \ overline (A ') = 1 + \ overline (A) [/ math] .

Сега всъщност ще докажем връзката на полинома на Тут с полинома на ранга, откъдето ще следва и правилността на дефиницията за полинома на Тут:

Ако графиката [math] G [/ math] е празна, тогава единственото подмножество на [math] E [/ math] е празният набор, за който няма важни и ненужни ръбове. Следователно, [math] \ rho ^ * (\ emptyset) = \ overline (\ emptyset) = 0 [/ math] и [math] R_G (u, v) = 1 = T_G (u + 1, v + 1) [/математика] .

Нека графиката [math] G [/ math] не е празна. Нека докажем, че връзките на Tutt (от дефиницията на полинома на Tutt) важат за ранг полином. Изберете някакъв ръб [math] e \ в E [/ math] и разделете всички подмножества [math] E [/ math] на двойки от формата [math] (A, A ') [/ math], където [math] e \ не \ в A [/ math] и [math] A '= A \ cup [/ math]. Тогава
[математика] R_G (u, v) = \ сума \ граници_> (u ^ v ^ (A)> + u ^ v ^ (A ')>) [/ math]

След това нека разгледаме няколко случая:

Нека [math] G [/ math] е дърво с [math] n [/ math] върхове. Тогава [math] T_G (x, y) = x ^ [/ math]. Този факт може лесно да се покаже чрез индукция: в едно дърво всеки ръб е мост, след свиване на който получаваме отново дърво с [math] n - 1 [/ math] върхове.

Нека обозначим с [math] S_n [/ math] набора от обхващащи дървета [math] T [/ math] на графиката [math] G [/ math]. Казваме, че ръбът [math] p \ in T [/ math] вътрешно активни (англ. вътрешно активни) в [math] T [/ math] ако [math] p \ prec q [/ math] за всички [math] q \ in E \ backslash t [/ math] така, че [math] T \ backslash p \ cup \ в S_n [/ math]. По същия начин казваме, че ръбът [math] p \ in T [/ math] външно активен (англ. външно активен) в [math] T [/ math], ако [math] p \ prec q [/ math] за всички [math] q \ in E \ backslash T [/ math] така, че [math] T \ backslash q \ cup

\ в S_n [/ math]. Стойността на вътрешната (външна) активност е броят на вътрешно (външно) активни елементи в [math] T [/ math]; тези количества ще бъдат обозначени съответно с [math] i (T) [/ math] и [math] e (T) [/ math].

Също така даваме, без доказателство, теорема, която свързва полинома на Тут и концепцията за обхващащо дърво:

Обозначаване: За простота, означете полинома на Tutt за пълната графика с [math] G _> (x, y) [/ math] с [math] F_n (x, y) [/ math]. Тогава важи следната теорема:

Поправяме обхващащо дърво [math] T \ в S_n [/ math]. Помислете за ръба [math] (0, k) \ в T [/ math], който разделя [math] T [/ math] на поддървета [math] T '[/ math] и [math] T' '[/ math ] и връх 0 се намира в [math] T '' [/ math]. Нека [math] a = | \ | [/ math]. След това доказваме следните две твърдения:

[math] i (T) = i (T ') + \ delta _ [/ math], където [math] \ delta _ [/ math] е символът Kronecker
[math] e (T) = e (T ') + e (T' ') + a [/ math]

Ясно е, че ръбът [math] (j_1, j_2) \ в T [/ math] не може да бъде вътрешно активен, защото [math] (0, j_1) \ prec (j_1, j_2) [/ math], [math] (0, j_2) \ prec (j_1, j_2) [/ math] и [math] T \ backslash (j_1, j_2) \ cup \ in S_n [/ math], [math] T \ backslash (j_1, j_2) \ cup \ in S_n [/ math]. Също така ръбът [math] (0, k) \ в T [/ math] е вътрешно активен в [math] T [/ math] [math] \ Leftrightarrow [/ math] [math] a = 0 [/ math], защото ако в T '' [/ math] има връх [math] j \ такъв, че [math] j \ lt k [/ math], тогава [math] (0, j) \ prec (0, k) [/math] и [math] T \ backslash (0, k) \ cup \ in S_n [/ math]. По този начин се доказва равенството (1).

Помислете [math] (j_1, j_2) [/ math], където [math] j_1 \ in T '[/ math], [math] j \ gt 0 [/ math] и [math] j_2 \ in T' '[/математика]. Тогава [math] (j_1, j_2) [/ math] не може да бъде външно активен, защото [math] (0, k) \ prec (j_1, j_2) [/ math] и [math] T \ backslash (j_1, j_2) \ cup \ in S_n [/ math]. По същия начин, нека [math] j \ в T '[[math], тогава ръбът [math] (0, j) [/ math] е външно активен [math] \ Leftrightarrow [/ math] [math] j \ lt k [/ математика]. По този начин ние също доказахме равенство (2).
Сега необходимата идентичност за полинома на Тут на пълна графика може да бъде получена чрез заместване на равенства (1) и (2) в [math] F_n (x, y) = \ sum \ limit_ x ^ y ^ [/ math] и сумиране над всички двойки поддървета [math] T ', T' '[/ math] и всички ръбове от тип [math] (0, k) [/ math] .

За доказателство използваме индукция върху броя на ръбовете. Тъй като за празна графика [математика] | E | = \ rho (E) = 0 [/ math] и [math] T_G = 1 [/ math], тогава индукционната база е вярна. Нека докажем прехода.

По този начин всички случаи са анализирани и теоремата е доказана.

Нека използваме универсалното свойство на полинома на Тут за функцията [math] P_G (k) = \ frac> [/ math]. Нека проверим състоянието на теоремата.
Нека ръбът [math] e [/ math] да бъде мост. След това наборът от върхове [math] V [/ math] се разделя на две несъединени подмножества: [math] V_1 [/ math] и [math] V_2 [/ math]. Нека обозначим с [math] G_1 [/ math] и [math] G_2 [/ math] съответните подграфи. Техните цветове не са свързани помежду си, така че [math] \ chi_ (k) = \ chi_ (k) \ cdot \ chi_ (k) [/ math]. Освен това, правилното оцветяване [math] G/e [/ math] се получава от правилното оцветяване [math] G_1 [/ math] и [math] G_2 [/ math], където цветовете на залепените върхове съвпадат. Можете да вземете всяко правилно оцветяване [math] G_1 [/ math], за което има [math] \ chi_ (k) [/ math], а от правилното оцветяване [math] G_2 [/ math] само фракцията [math ] \ frac [/ math], където се изисква цветът на върха, който трябва да се постави. Така че [math] \ chi _ (k) = \ frac \ chi _ (k) \ chi _ (k) [/ math]. Освен това, чрез повтарящото се свойство на хроматичния полином [математика] \ chi _ (k) = \ chi _ (k) - \ chi _ (k) = (1 - \ frac) \ chi _ (k) \ cdot \ chi _ (k) = (k - 1) \ chi _ (k) [/ math]. Следователно, [math] P_G (k) = \ frac (k) >> = \ frac (k) >> = \ frac P_ (k) [/ math], тоест първото условие е изпълнено за [math] x_0 = \ frac [/ math] .
Нека ръбът [math] e [/ math] да бъде цикъл. Тогава няма правилни оцветявания, т.е. [math] P_G (k) = 0 [/ math]. Така че второто условие е изпълнено за [math] y_0 = 0 [/ math]. Нека ръбът [math] e [/ math] не е нито мост, нито цикъл. Отново, поради повтарящото се свойство на хроматичния полином [math] \ chi _ (k) = \ chi _ (k) + \ chi _ (k) [/ math]. Разделяйки се на [math] k ^ [/ math], получаваме [math] P_G (k) = - \ frac P_ (k) + P_ (k) [/ math]. Следователно, третата връзка е валидна за [math] a = \ frac, b = 1 [/ math] .

Според универсалното свойство на полинома на Тут получаваме [math] P_G (k) = (- \ frac) ^ T_G (1 - k, 0) [/ math]. Следователно, [math] \ chi _G (k) = (-1) ^ k ^ T_G (1 - k, 0) [/ math]. Тъй като [математика] \ rho (E) = | V | - c (G) [/ math], получаваме [math] \ chi _G (k) = (-1) ^ k ^ T_G (1 - k, 0) [/ math] .

Имайте предвид, че [math] \ overline (A) = 0 [/ math] тогава и само ако [math] G (A) [/ math] не съдържа цикли и [math] \ rho ^ * (A) = 0 [/math] тогава и само ако [math] G (A) [/ math] има същия брой свързани компоненти като [math] G [/ math] .
След това използваме теоремата за връзката с полинома на ранга:

[math] T_G (1, 1) = R_G (0, 0) [/ math]. Като се има предвид, че [math] 0 ^ 0 = 1 [/ math] и [math] 0 ^ k = 0 [/ math] за [math] k \ gt 0 [/ math], само тези термини, където [math] \ rho ^ * (A) = 0 [/ math] и [math] \ overline (A) = 0 [/ math]. Това означава, че [math] G (A) [/ math] не съдържа цикли и съдържа същия брой свързани компоненти като [math] G [/ math], тоест това е обхващаща гора. Като сумираме мерните единици за всяка обхващаща гора, получаваме броя на обхванатите гори.
[math] T_G (1, 2) = R_G (0, 1) [/ math]. Тук обобщаваме мерните единици за тези [math] A [/ math], където [math] \ rho ^ * (A) = 0 [/ math], тоест за подграфи със същия брой свързани компоненти като [math] G [/ математика] .
[math] T_G (2, 1) = R_G (1, 0) [/ math]. Тук обобщаваме мерните единици за тези [math] A [/ math], където [math] \ overline (A) = 0 [/ math], тоест за ациклични подграфи.