Формула Уитни

Теорема (Уитни):

Пусть [math]G[/math] — обыкновенный [math](n, m)[/math] - граф. Тогда коэффициент при [math]x^i[/math], где [math]1\leqslant i\leqslant n[/math] в хроматическом многочлене [math]P(G, x)[/math] равен [math]\sum \limits_{j=0}^{m}{(-1)^jN(i, j)}[/math], где [math]N(i, j)[/math] — число остовных подграфов графа [math]G[/math], имеющих [math]i[/math] компонент связности и [math]j[/math] рёбер, т.е. [math]P(G, x) = \sum \limits_{i=1}^{n}{(\sum \limits_{j=0}^{m}{(-1)^jN(i, j))x^i}}.[/math]

Доказательство:

[math]\triangleright[/math]

Пусть [math]K[/math] — некоторый набор из [math]x[/math] красок. Отображение [math]\varphi[/math] из [math]VG[/math] в [math]K[/math], не являющееся раскраской графа [math]G[/math], будем называть его несобственной раскраской. То есть, для того, чтобы отображение было несобственной раскраской, цвет концов хотя бы одного ребра должен совпадать. Собственной раскраской будем называть раскраску графа. Всего собственных и несобственных [math]x[/math]-раскрасок графа [math]G[/math] — [math]x^n[/math]. Возьмём некоторую собственную или несобственную раскраску графа [math]G[/math]. Удалим из графа каждое ребро, концы которого раскрашены в разный цвет. Получим остовный подграф [math]H[/math], в котором каждое ребро соединяет вершины одинакового цвета. Исходную собственную или несобственную раскраску будем называть строго несобственной раскраской остовного подграфа [math]H[/math]. Каждой компоненте связности графа [math]H[/math] соответствует точно один цвет — цвет её вершин. Если остовный подграф [math]H[/math] имеет [math]i[/math] компонент связности, то существует [math]x^i[/math] различных строго несобственных раскрасок, отвечающих остовному подграфу [math]H[/math]. Каждая собственная или несобственная раскраска графа [math]G[/math] является строго несобственной раскраской его остовного подграфа. Собственным раскраскам графа [math]G[/math] отвечает нулевой остовный подграф. Пусть [math]N(i, j)[/math] — число остовных подграфов графа [math]G[/math], имеющих [math]i[/math] компонент связности и [math]j[/math] рёбер. Из общего числа [math]x^n[/math] собственных и несобственных раскрасок вычтем число строго несобственных раскрасок остовных подграфов, имеющих ровно одно ребро. Если мы вычтем сумму [math] \sum \limits_{i}{N(i, 1)x^i} [/math], то мы вычтем помимо указанного числа ещё и некоторую избыточную величину. Действительно, рассмотрим два различных ребра графа [math]G[/math]: [math]e_1[/math] и [math]e_2[/math]. В число строго несобственных раскрасок остовного подграфа, содержащего только ребро [math]e_1[/math] попадут раскраски, у которых концы [math]e_2[/math] имеют одинаковый цвет. То же самое верно и для остовного подграфа, содержащего только ребро [math]e_2[/math]. Получается, что мы дважды вычтем число строго несобственных раскрасок для остовного подграфа [math]G[/math], содержащего два ребра: [math]e_1[/math] и [math]e_2[/math]. Аналогично будет вычтено число строго несобственных раскрасок остовных подграфов с большим числом ребер. Попытаемся скомпенсировать двукратное вычитание добавлением [math]\sum \limits_{i}{N(i, 2)x^i}[/math], однако при этом добавится излишек строго несобственных раскрасок для остовных подграфов с тремя, четырьмя и более ребрами. Подобную конструкцию можно рассчитать по формуле включения-исключения. Воспользуемся формулой и получим число собственных раскрасок графа [math]G[/math]. Оно равно [math]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} + ...[/math] Так как [math]N(n, 0) = 1[/math], то [math]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}}[/math].

[math]\triangleleft[/math]

См. также

• Формула Зыкова

Источники информации

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