1632
правки
Изменения
м
Рассмотрим Докажем по индукции по количеству вершин.<br>'''База индукции''': рассмотрим случай <tex>n = 3</tex>: <tex>P(C_3, x) = x(x - 1)(x - 2) = (x ^3 - 3x^2 + 3x - 1)- (x^2 - x1) = (x - 1)^3 + (-1)^3(x - 1)</tex>, что удовлетворяет формулировке теоремы.<br>Пусть '''Индукционный переход''': пусть <tex>P(С_kC_k, x) = (x - 1)^k + (-1)^k(x - 1)</tex>.<br>Рассмотрим случай <tex>n = k + 1</tex>. По теореме о [[#.D0.A0.D0.B5.D0.BA.D1.83.D1.80.D1.80.D0.B5.D0.BD.D1.82.D0.BD.D1.8B.D0.B5_.D1.84.D0.BE.D1.80.D0.BC.D1.83.D0.BB.D1.8B_.D0.B4.D0.BB.D1.8F_.D1.85.D1.80.D0.BE.D0.BC.D0.B0.D1.82.D0.B8.D1.87.D0.B5.D1.81.D0.BA.D0.B8.D1.85_.D0.BC.D0.BD.D0.BE.D0.B3.D0.BE.D1.87.D0.BB.D0.B5.D0.BD.D0.BE.D0.B2Рекуррентные_формулы_для_хроматических_многочленов|рекурентной рекуррентной формуле для хроматических многочленов]]: <tex>P(C_{k + 1}, x ) = P(C_{k + 1} \setminus e, x) - P(C_{k + 1} / e, x)</tex> (где <tex>e</tex> — любое ребро <tex>C_{k + 1}</tex>).Заметим, что граф <tex>C_{k + 1} / e</tex> изоморфен <tex>C_k</tex>. Заметим, что а граф <tex>C_{k + 1} \setminus e</tex> является [[#.D0.A5.D1.80.D0.BE.D0.BC.D0.B0.D1.82.D0.B8.D1.87.D0.B5.D1.81.D0.BA.D0.B8.D0.B9_.D0.BC.D0.BD.D0.BE.D0.B3.D0.BE.D1.87.D0.BB.D0.B5.D0.BD_.D0.BF.D1.80.D0.BE.D1.81.D1.82.D0.BE.D0.B9_.D1.86.D0.B5.D0.BF.D0.B8Хроматический_многочлен_простой_цепи|простой цепью]].Тогда <tex>P(C_{k + 1}, x)=P(T_{k + 1}, x)-P(C_k, x)=x(x-1)^k-(x-1)^k-(-1)^k(x-1)=</tex><tex>(x-1)^{k+1}+(-1)^{k+1}(x-1)</tex>.
{{Определение|definition='''Колесо''' (англ. ''Wheel graph'') — граф с <tex>n</tex> вершинами (<tex>n \le 4</tex>), образованный соединением единственной вершины со всеми вершинами (<tex>n - 1</tex>)-цикла.}}Пусть <tex>W_n</tex> — [[Двойственный_граф_планарного_графа|колесо ]] с <tex>n</tex> вершинами. Выбрав и зафиксировав один из <tex>x</tex> цветов на вершине, связнной со всеми остальными, имеем <tex> P_{P(C_{n - 1}}(, x - 1) </tex> вариантов раскраски оставшегося графа. Тогда хроматичсекий хроматический многочлен колеса <tex>P_{W_n}(x) = x \cdot P_{C_{n - 1}}(x - 1) = x((x - 2)^{(n - 1)} - + (-1)^{(n- 1)}(x - 2))</tex>.
rollbackEdits.php mass rollback
{{Теорема
|statement=
Пусть <tex>u</tex> и <tex>v</tex> - — несмежные вершины графа <tex>G</tex>. Если <tex>G_1=G\cup uv</tex>, а <tex>G_2=G/uv</tex>, то <tex>P(G,x)=P(G_1,x)+P(G_2,x)</tex>.
|proof=
Рассмотрим все произвольные раскраски графа <tex>G</tex>. Рассмотрим те из них, при которых вершины <tex>u</tex> и <tex>v</tex> окрашены в разные цвета. Если добавить к графу <tex>G</tex> ребро <tex>uv</tex>, то они не изменятся, то есть останутся правильными. Рассмотрим раскраски, при которых <tex>u</tex> и <tex>v</tex> одного цвета. Все эти раскраски останутся правильными и для графа, полученного из <tex>G</tex> слиянием вершин <tex>u</tex> и <tex>v</tex>.
хроматический многочлен цикла
|statement=
Пусть <tex>C_n</tex> — цикл длины <tex>n</tex>. Тогда хроматичсекий хроматический многочлен цикла <tex>P(C_n, x) = (x - 1)^n + (-1)^n(x - 1)</tex>.
|proof=
}}
=== Хроматический многочлен колеса ===
=== Хроматический многочлен дерева ===
{{Теорема
* Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. - СПб.: Издательство "Лань", 2010. - 368 с.: ил. - (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
* Харари Ф. — Теория графов: Изд. 4-е. - М.: Книжный дом "ЛИБРОКОМ", 2009. - 296 с. ISBN 978-5-397-00622-4
* [[wikipedia:en:Chromatic_polynomial| Wikipedia {{---}} Chromatic_polynomialChromatic polynomial]]* [[wikipedia:ru:Хроматическое_число#.D0.A5.D1.80.D0.BE.D0.BC.D0.B0.D1.82.D0.B8.D1.87.D0.B5.D1.81.D0.BA.D0.B8.D0.B9_.D0.BC.D0.BD.D0.BE.D0.B3.D0.BE.D1.87.D0.BB.D0.B5.D0.BDХроматический_многочлен| Wikipedia {{---}} Хроматический многочлен]]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]
