Изменения

Пусть <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}{\bigg(\sum \limits_{j=0}^{m}{(-1)^jN(i, j)\bigg)x^i}}.</tex>

<br>Пусть <tex>K</tex> - — некоторый набор из <tex>x</tex> красок. Отображение <tex>\phivarphi</tex> из множества вершин <tex>VGV</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> является строго несобственной раскраской его остовного подграфа. Cобственным Собственным раскраскам графа <tex>G</tex> отвечает нулевой остовный подграф.<br> Пусть <tex>N(i, j)</tex> - — число остовных подграфов графа <tex>G</tex>, имеющих <tex>i</tex> компонент связности и <tex>j</tex> рёбер. Из общего числа <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>. Аналогично будет вычтено число строго несобственных раскрасок остовных подграфов с большим числом ребер. Попытаемся скомпенсировать двукратное вычитание добавлением <tex>\sum \limits_{i}{N(i, 2)x^i}<br/tex>По принципу , однако при этом добавится излишек строго несобственных раскрасок для остовных подграфов с тремя, четырьмя и более ребрами. Подобную конструкцию можно рассчитать по [[Формула включения-исключения|формуле включения-исключения получаем, что ]]. Воспользуемся формулой и получим число собственных раскрасок графа <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