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

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

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

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

[math]\triangleright[/math]

Применим для подстчёта коэффициентов один из широко применяемых принципов комбинаторного анализа - принцип включения-исключения. Зафиксируем некоторый набор [math]K[/math] из [math]x[/math] красок, где [math]x[/math] - некоторое натуральное число. Отображение [math]\phi[/math] из [math]VG[/math] в [math]K[/math], не являющееся раскраской графа [math]G[/math], будем называть его несобственной раскраской (для несобственной раскраски обязательно существует ребро графа, концы которого раскрашены в одинаковый цвет). Конечно, число собственных и несобственных [math]x[/math] - раскрасок [math]n[/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](n, j, i)[/math] - подграфов графа [math]G[/math]. Из общего числа [math]x^n[/math] собственных и несобственных раскрасок вычтем сначала число строго несобственных раскрасок тех остовных подграфов, у которых имеется точно одно ребро. Если мы вычтем сумму [math]\sum_{i}N(i, 1)x^i[/math], то мы вычтем указанное число, но вычтем ещё и некоторую избыточную величину. Действительно, пусть [math]e_1 = u_1v_1[/math] и [math]e_2 = u_2v_2[/math] - два различных ребра графа [math]G[/math]. Тогда в число строго несобственных раскрасок остовного подграфа, содержащего точно одно ребро [math]e_1[/math], попадут и те, у которых вершины [math]u_2[/math] и [math]v_2[/math] имеют одинаковый цвет, а это - строго несобственные раскраски остовного подграфа, содержащего точно два ребра [math]e_1[/math] и [math]e_2[/math]. Более того, их число будет вычтено дважды - один раз для [math]e_1[/math] и один раз для [math]e_2[/math]. Аналогично, число строго несобственных раскрасок остовных подграфов, содержащих точно 3, 4 и более рёбер, будет вычтено соответствующее число раз. Чтобы восстаносить баланс, мы добавим сумму [math]\sum_{i}N(i, 2)x^i[/math]. При этом мы компенсируем двухкратное вычитание числа строго несобственных раскрасок, отвечающих остовным подграфам с двумя рёбрами, но снова возникает необходимость компенсации излишне добавленных чисел строго несобственных раскрасок для остовных подграфов с тремя, четырьмя, и более рёбрами. Следовательно, число собственных раскрасок графа [math]G[/math] равно [math]x^n - \sum_{i}N(i, 1)x^i + \sum_{i}N(i, 2)x^i - \sum_{i}N(i, 3)x^i + ...[/math]. Так как [math]N(n, 0) = 1[/math], отсюда вытекает [math]P(G, x) = \sum_{j=0}^{m}\sum_{i=1}^{n}(-1)^jN(i, j)x^i = \sum_{i=1}^{n}\sum_{j=0}^{m}(-1)^jN(i, j)x^i[/math].

[math]\triangleleft[/math]

Литература

• Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы