Уитни
|statement=
Пусть <tex>G</tex> - — обыкновенный <tex>(n, m)</tex> - граф. Тогда коэффициент при <tex>x^i</tex>, где <tex>1\le leqslant i\le leqslant n</tex> в [[Хроматический многочлен|хроматическом многочлене]] <tex>P(G, x)</tex> равен <tex>\sum \limits_{j=0}^{m}{(-1)^jN(i, j)}</tex>, где <tex>N(i, j)</tex> - — число остовных подграфов графа <tex>G</tex>, имеющих <tex>i</tex> компонент связности и <tex>j</tex> рёбер, т.е. <tex>P(G, x) = \sum \limits_{i=1}^{n}{(\sum \limits_{j=0}^{m}{(-1)^jN(i, j))x^i}}.</tex>
|proof=
<br>Пусть <tex>K</tex> — некоторый набор из <tex>x</tex> красок. Отображение <tex>\phivarphi</tex> из <tex>VG</tex> в <tex>K</tex>, не являющееся раскраской графа <tex>G</tex>, будем называть его ''несобственной'' раскраской. То есть, для того, чтобы отображение было несобственной раскраской, цвет концов хотя бы одного ребра должен совпадать. ''Собственной'' раскраской будем называть раскраску графа. Всего собственных и несобственных <tex>x</tex>-раскрасок графа <tex>G</tex> — <tex>x^n</tex>.<br> Возьмём некоторую собственную или несобственную раскраску графа <tex>G</tex>. Удалим из графа каждое ребро, концы которого раскрашены в разный цвет. Получим остовный подграф <tex>H</tex>, в котором каждое ребро соединяет вершины одинакового цвета. Исходную собственную или несобственную раскраску будем называть ''строго несобственной'' раскраской остовного подграфа <tex>H</tex>. Каждой компоненте связности графа <tex>H</tex> соответствует точно один цвет - — цвет её вершин. Если остовный подграф <tex>H</tex> имеет <tex>i</tex> компонент связности, то есть существует <tex>x^i</tex> различных строго несобственных раскрасок, отвечающих остовному подграфу <tex>H</tex>.<br>Каждая собственная или несобственная раскраска графа <tex>G</tex> является строго несобственной раскраской его остовного подграфа. Собственным раскраскам графа <tex>G</tex> отвечает нулевой остовный подграф.<br> Пусть <tex>N(i, j)</tex> — число остовных подграфов графа <tex>G</tex>, имеющих <tex>i</tex> компонент связности и <tex>j</tex> рёбер.<br> Из общего числа <tex>x^n</tex> собственных и не собственных несобственных раскрасок вычтем число строго несобственных раскрасок остовных подграфов, имеющих ровно одно ребро. Если мы вычтем сумму <tex> \sum \limits_{i}{N(i, 1)x^i} </tex>, то мы вычтем помимо указанного числа ещё и некоторую избыточную величину. Действительно, рассмотрим два различных ребра графа <tex>G</tex>: <tex>e_1</tex> и <tex>e_2</tex>. В число строго несобственные несобственных раскрасок остовного подграфа, содержащего только ребро <tex>e_1</tex> попадут раскраски , у которых концы <tex>e_2</tex> имеют одинаковый цвет. То же самое верно и для остовного подграфа, содержащего ровно два ребратолько ребро <tex>e_2</tex>. Более тогоПолучается, это число что мы дважды вычтем дважды. Подобным образом, число строго несобственных раскрасок остовных подграфовдля остовного подграфа <tex>G</tex>, содержащих точно три, четыре содержащего два ребра: <tex>e_1</tex> и более ребер <tex>e_2</tex>. Аналогично будет вычтено соответствующее число разстрого несобственных раскрасок остовных подграфов с большим числом ребер.<br/> Попытаемся скомпенсировать двукратное вычитание добавлением <tex>\sum \limits_{i}{N(i, 2)x^i}</tex>, однако при этом добавится излишек строго несобственных раскрасок для остовных подграфов с тремя, четырьмя и более ребрами. <br/>
Подобную конструкцию можно рассчитать по [[Формула включения-исключения|формуле включения-исключения]].
Воспользуемся формулой и получим число собственных раскрасок графа <tex>G</tex>. Оно равно <tex>x^n - \sum \limits_{i}{N(i, 1)x^i} + \sum \limits_{i}{N(i, 2)x^i} - \sum \limits_{i}{N(i, 3)x^i} + ...</tex><br>Так как <tex>N(n, 0) = 1</tex>, то <tex>P(G, x) = \sum \limits_{j=0}^{m}{\sum \limits_{i=1}^{n}{(-1)^jN(i, j)x^i}} = \sum \limits_{i=1}^{n}{\sum \limits_{j=0}^{m}{(-1)^jN(i, j)x^i}}</tex>.
}}
==См. также==*[[Формула Зыкова]]==ЛитератураИсточники информации==
* Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. - СПб.: Издательство "Лань", 2010. - 368 с.: ил. - (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов ]]
