Хроматичен полином

Коментар: Ако добавим ръбове към някаква произволна графика последователно, без да променяме нейните върхове, тогава на някаква стъпка получаваме пълна графика. По същия начин получаваме пълна графика, ако намалим броя на върховете в произволен граф, като ги идентифицираме, без да променяме броя на ръбовете.

Следствие: Хроматичният полином на всяка графика [math] G [/ math] е равен на сумата от хроматичните полиноми на определен брой пълни графики, броят на върховете в които е не повече от графиката [math] G [/ математика] .

Хроматичен полином на пълна графика [редактиране]

[математика] P (K_, x) = x (x-1). (xn + 1) = x ^> [/ math], тъй като първият връх на пълната графика [math] K _ [/ math] може да бъде оцветен във всеки от [math] x [/ math] цветове, а вторият - във всеки от останалите [math] x-1 [/ math] цветове и др. Очевидно е, че ако [math] x [/ math] е по-малко от [math] n [/ math], то полиномът е [math] 0 [/math], тъй като един от факторите му е [math] 0 [/ math] .

Хроматичен полином на нулева графика [редактиране]

[math] P (O_, x) = x ^ [/ math], тъй като всеки от [math] n [/ math] върховете на нулевата графика [math] O _ [/ math] може да бъде независимо оцветен във всеки от [math] x [/ math] цветове.
Забележка: Нулевата графика [math] O _ [/ math] може също да бъде обозначена с [math] \ overline> [/ math] (допълнителна графика за пълната графика [math] K _ [/ math]).

Хроматичен полином на проста верига [редактиране]

Нека [math] T_n [/ math] е проста верига, състояща се от [math] n [/ math] върхове. Помислете за процеса на оцветяване на проста верига: първият връх може да бъде оцветен в един от цветовете [math] x [/ math], вторият и следващите в един от цветовете [math] x - 1 [/ math] ( тоест, така че цветът да не съвпада с предишния пик). Тогава [math] P (T_n, x) = x (x - 1) ^ [/ math] .

Цикъл хроматичен полином [редактиране]

Нека докажем чрез индукция върху броя на върховете.
Индукционна база: разгледаме случая [math] n = 3 [/ math]: [math] P (C_3, x) = x (x - 1) (x - 2) = (x ^ 3 - 3x ^ 2 + 3x - 1) - (x - 1) = (x - 1) ^ 3 + (-1) ^ 3 (x - 1) [/ math], което удовлетворява твърдението на теоремата.
Индукционна връзка: нека [math] P (C_k, x) = (x - 1) ^ k + (-1) ^ k (x - 1) [/ math] .
Да разгледаме случая [math] n = k + 1 [/ math]. По теоремата за рекуррентната формула за хроматични полиноми: [math] P (C_, x) = P (C_ \ setminus e, x) - P (C_/e, x) [/ math] (където [math] e [/math] - всеки ръб [math] C _ [/ math]). Обърнете внимание, че графиката [math] C_/e [/ math] е изоморфна на [math] C_k [/ math], а графиката [math] C_ \ setminus e [/ math] е проста верига.

Хроматичен полином на колелото [редактиране]

Нека [math] W_n [/ math] е колело с [math] n [/ math] върхове. Избирайки и фиксирайки един от [math] x [/ math] цветовете във върха, свързан с всички останали, имаме опции [math] P (C_, x - 1) [/ math] за оцветяване на останалата графика. Тогава хроматичният полином на колелото [math] P_ (x) = x \ cdot P _> (x - 1) = x ((x - 2) ^ - (-1) ^ (x - 2)) [/ math ] .

Хроматичен полином на дърво [редактиране]

[math] \ Rightarrow [/ math]

Първо, покажете, че хроматичният полином на всяко дърво [math] T [/ math] с [math] n [/ math] върхове е [math] x (x-1) ^ [/ math]. Доказателство чрез индукция на числото [math] n [/ math]. За [math] n = 1 [/ math] и [math] n = 2 [/ math], резултатът е очевиден. Да предположим [math] P (T ', x) = x (x-1) ^ [/ math] за всяко дърво [math] T' [/ math] с броя на върховете, равен на [math] n-1 [/ математика]. Нека [math] uv [/ math] е ръб на дървото [math] T [/ math], така че [math] v [/ math] да е висящ връх. Хроматичният полином на дървото [math] T [/ math] без ръб [math] uv [/ math] е [math] P (T/uv, x) = x (x-1) ^ [/ math] от нашия предположение. Върхът [math] v [/ math] може да бъде оцветен с метода [math] x-1 [/ math], тъй като цветът му трябва да се различава само от цвета на върха [math] u [/ math]. Общо: [math] P (T, x) = (x-1) P (T/uv, x) = x (x-1) ^ [/ math] .
[математика] \ Leftarrow [/ математика]
И обратно, нека [math] G [/ math] е графика с [math] P (G, x) = x (x-1) ^ [/ math]. Тогава следните две твърдения са верни:

  1. Графиката [math] G [/ math] е свързана, защото ако имаше два или повече свързани компонента, тогава [math] P (G, x) [/ math] ще се дели на [math] x ^ 2 [/ math ] без остатък.
  2. В графиката [math] G [/ math] броят на ребрата е равен на [math] n-1 [/ math], тъй като според една от теоремите за коефициентите на хроматичния полином (Коефициенти на хроматичния полином, Теорема 4), броят на ребрата в графиката съответства на коефициента при [math] x ^ [/ math], взет със знак минус. В нашия случай е удобно да се търси този коефициент с помощта на бином на Нютон:
    [математика] = x \ ляво (x ^ -x ^ + x ^ -. + (- 1) ^ \ дясно) = x ^ - (n-1) x ^ +. + (- 1) ^ x> [/ math]
От тези две твърдения (свързаност и [math] n-1 [/ math] edge) следва, че графиката [math] G [/ math] е дърво (вж. Дърво, еквивалентни дефиниции, твърдения 1 и 3).

Нека използваме повтарящата се формула:
[math] P (G, x) = P (G_, x) + P (G_, x) [/ math],
където [math] G _ [/ math] е графиката, получена от [math] G [/ math] чрез добавяне на ръба [math] uv [/ math], който отсъства в [math] G [/ math], и [ math] G _ [/ math] е графика, получена от [math] G [/ math] чрез сливане на върховете [math] u [/ math] и [math] v [/ math] в едно и премахване на множеството ръбове, които възникват в този случай. Прилагайки отново повтарящата се формула, хроматичният полином може да бъде представен като сбор от хроматичните полиноми на пълни графики, т.е.
[math] P (G, x) =, x) + a_P (K_, x) + a_P (K_, x) + \ ldots = x ^> + a_x ^> + a_x ^> + \ ldots> [/ math]

Тази формула показва, че хроматичният полином има водещ коефициент, равен на [math] 1 [/ math] .

Индукция по броя на върховете.
Индукционна база:
Теоремата е вярна за графика [math] G [/ math] на един връх, тъй като [math] P (G, x) = x [/ math] .
Индукционна връзка ([математика] n \ до n + 1) [/ математика]:
Да предположим, че теоремата е вярна за всички графики на [math] n [/ math] върхове. Помислете за графики на върха [math] n + 1 [/ math]. Ще докажем индукционния преход чрез индукция върху броя на ръбовете на графиката [math] G [/ math]. Ако [math] G [/ math] не съдържа ръбове, т.е. [math] G [/ math] е [math] O _ [/ math], тогава неговият хроматичен полином [math] P (G, x) = x ^ [/ math] има доказуемо свойство. Сега да предположим, че теоремата е вярна за всички [math] (n + 1, m) [/ math] -графа. Вземете [math] (n + 1, m + 1) [/ math] -graph [math] G _ [/ math] и неговия ръб [math] uv [/ math]. Нека обозначим с [math] G [/ math] графиката, получена от [math] G _ [/ math] чрез изтриване на ръба [math] uv [/ math] ([math] G = G_-uv [/ math]), и чрез [math] G _ [/ math] - графиката, получена от [math] G _ [/ math] чрез обединяване на върховете [math] u [/ math] и [math] v [/ math]. Тогава от рекурентната формула следва:
[math] P (G_, x) = P (G, x) -P (G_, x) [/ math]. Тъй като [math] G [/ math] е [math] (n + 1, m) [/ math] -graph, а в [math] G _ [/ math] - [math] n [/ math] върхове, тогава за [math] G [/ math] и [math] G _ [/ math] теоремата е вярна:
[math] -a_x ^ + a_x ^ -a_x ^ + \ ldots> [/ math],
[math], x) = x ^ -b_x ^ + b_x ^ + \ ldots> [/ math],
където [math] a _ [/ math], [math] a _ [/ math]… [math] a _ [/ math], [math] b _ [/ math], [math] b _ [/ math] ... [math] b_ [/ math] - някои неотрицателни цели числа. От тези равенства получаваме:
[math] P (G_, x) = x ^ - (a_ + 1) x ^ + (a_ + b_) x ^ + \ ldots [/ math] .

Вижда се, че в този получен полином коефициентите образуват променлива последователност.