Изменения

Пусть <tex>G</tex> - — обыкновенный <tex>(n, m)</tex> - граф. Тогда коэффициент при <tex>x^i</tex>, где <tex>1<=\leqslant i<=\leqslant n</tex> в [[Хроматический многочлен|хроматическом многочлене ]] <tex>P(G, x)</tex> равен <tex>\sum_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_sum \limits_{i=1}^{n}{\bigg(\sum_sum \limits_{j=0}^{m}{(-1)^jN(i, j)\bigg)x^i}}.</tex>

Применим для подстчёта коэффициентов один из широко применяемых принципов комбинаторного анализа - принцип включения-исключения.<br>Зафиксируем некоторый набор Пусть <tex>K</tex> — некоторый набор из <tex>x</tex> красок, где <tex>x</tex> - некоторое натуральное число. Отображение <tex>\phivarphi</tex> из множества вершин <tex>VGV</tex> в <tex>K</tex>, не являющееся раскраской графа <tex>G</tex>, будем называть его ''несобственной '' раскраской (. То есть, для того, чтобы отображение было несобственной раскраски обязательно существует ребро графараскраской, концы которого раскрашены в одинаковый цвет)концов хотя бы одного ребра должен совпадать. ''Собственной'' раскраской будем называть раскраску графа. Конечно, число Всего собственных и несобственных <tex>x</tex> - раскрасок <tex>n</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> рёбер. Иными словами, это число <tex>(n, j, i)</tex> - подграфов графа <tex>G</tex>.<br> Из общего числа <tex>x^n</tex> собственных и несобственных раскрасок вычтем сначала число строго несобственных раскрасок тех остовных подграфов, у которых имеется точно имеющих ровно одно ребро. Если мы вычтем сумму <tex>\sum_sum \limits_{i}{N(i, 1)x^i} </tex>, то мы вычтем указанное число, но вычтем помимо указанного числа ещё и некоторую избыточную величину. Действительно, пусть рассмотрим два различных ребра графа <tex>e_1 = u_1v_1G</tex> и : <tex>e_2 = u_2v_2e_1</tex> - два различных ребра графа и <tex>Ge_2</tex>. Тогда в В число строго несобственных раскрасок остовного подграфа, содержащего точно одно только ребро <tex>e_1</tex>, попадут и тераскраски, у которых вершины концы <tex>u_2</tex> и <tex>v_2e_2</tex> имеют одинаковый цвет, а это - строго несобственные раскраски . То же самое верно и для остовного подграфа, содержащего точно два ребра только ребро <tex>e_1e_2</tex> и . Получается, что мы дважды вычтем число строго несобственных раскрасок для остовного подграфа <tex>e_2G</tex>. Более того, их число будет вычтено дважды - один раз для содержащего два ребра: <tex>e_1</tex> и один раз для <tex>e_2</tex>. Аналогично, будет вычтено число строго несобственных раскрасок остовных подграфов, содержащих точно 3, 4 и более рёбер, будет вычтено соответствующее число разс большим числом ребер.<br>Чтобы восстаносить баланс, мы добавим сумму  Попытаемся скомпенсировать двукратное вычитание добавлением <tex>\sum_sum \limits_{i}{N(i, 2)x^i}</tex>. При , однако при этом мы компенсируем двухкратное вычитание числа строго несобственных раскрасок, отвечающих остовным подграфам с двумя рёбрами, но снова возникает необходимость компенсации излишне добавленных чисел добавится излишек строго несобственных раскрасок для остовных подграфов с тремя, четырьмя, и более рёбрамиребрами. Подобную конструкцию можно рассчитать по [[Формула включения-исключения|формуле включения-исключения]].<br>Следовательно, Воспользуемся формулой и получим число собственных раскрасок графа <tex>G</tex> . Оно равно <tex>x^n - \sum_sum \limits_{i}{N(i, 1)x^i } + \sum_sum \limits_{i}{N(i, 2)x^i } - \sum_sum \limits_{i}{N(i, 3)x^i } + ...</tex>. <br>Так как <tex>N(n, 0) = 1</tex>, отсюда вытекает то <tex>P(G, x) = \sum_sum \limits_{j=0}^{m}{\sum \sum_limits_{i=1}^{n}{(-1)^jN(i, j)x^i }} = \sum_sum \limits_{i=1}^{n}{\sum \sum_limits_{j=0}^{m}{(-1)^jN(i, j)x^i}}</tex>.

==См. также==*[[Формула Зыкова]]==ЛитератураИсточники информации==* Асанов М,. О., Баранский В. А., Расин В. В. - Дискретная математика - : Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. - СПб.: Издательство "Лань", 2010. - 368 с.: ил. - (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2