81
правка
Изменения
Нет описания правки
Из общего числа <tex>x^n</tex> собственных и не собственных раскрасок вычтем число строго несобственных раскрасок остовных подграфов, имеющих ровно одно ребро. Если мы вычтем сумму <tex> \sum \limits_{i}{N(i, 1)x^i} </tex>, то мы вычтем помимо указанного числа ещё и избыточную величину. Действительно, допустим <tex>e_1 = u_1v_1</tex> и <tex>e_2 = u_2v_2</tex> — два различных ребра графа <tex>G</tex>. Тогда в число строго несобственных раскрасок остовного подграфа, содержащего точно одно ребро <tex>e_1</tex>, попадут и те, у которых вершины <tex>e_1</tex> и <tex>e_2</tex>, а это в свою очередь строго несобственные раскраски остовного подграфа, содержащего ровно два ребра <tex>e_1</tex> и <tex>e_2</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>.
}}
