81
правка
Изменения
м
Нет описания правки
Уитни
|statement=
Пусть <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 \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>
|proof=
Пусть <tex>K</tex> — некоторый набор из <tex>x</tex> красок. Отображение <tex>\varphi</tex> из множества вершин <tex>VGV</tex> в <tex>K</tex>, не являющееся раскраской графа <tex>G</tex>, будем называть его ''несобственной'' раскраской. То есть, для того, чтобы отображение было несобственной раскраской, цвет концов хотя бы одного ребра должен совпадать. ''Собственной'' раскраской будем называть раскраску графа. Всего собственных и несобственных <tex>x</tex>-раскрасок графа <tex>G</tex> — <tex>x^n</tex>.
Возьмём некоторую собственную или несобственную раскраску графа <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> отвечает нулевой остовный подграф.
