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

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

Коректността не е очевидна от тази дефиниция: защо получената функция не зависи от реда на отстраняване на ръба? Ако обаче дефиницията е правилна, [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].