Формула Уитни — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
Уитни
 
Уитни
 
|statement=
 
|statement=
−
Пусть <tex>G</tex> - обыкновенный <tex>(n, m)</tex> - граф. Тогда коэффициент при <tex>x^i</tex>, где <tex>1\le i\le n</tex> в хроматическом многочлене <tex>P(G, x)</tex> равен <tex>\sum_{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_{i=1}^{n}(\sum_{j=0}^{m}(-1)^jN(i, j))x^i.</tex>
+
Пусть <tex>G</tex> - обыкновенный <tex>(n, m)</tex> - граф. Тогда коэффициент при <tex>x^i</tex>, где <tex>1\le i\le 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}{(\sum \limits_{j=0}^{m}{(-1)^jN(i, j))x^i}}.</tex>
 
|proof=
 
|proof=
−
Применим для подстчёта коэффициентов один из широко применяемых принципов комбинаторного анализа - принцип включения-исключения.<br>Зафиксируем некоторый набор <tex>K</tex> из <tex>x</tex> красок, где <tex>x</tex> - некоторое натуральное число. Отображение <tex>\phi</tex> из <tex>VG</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_{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>u_2</tex> и <tex>v_2</tex> имеют одинаковый цвет, а это - строго несобственные раскраски остовного подграфа, содержащего точно два ребра <tex>e_1</tex> и <tex>e_2</tex>. Более того,  их число будет вычтено дважды - один раз для <tex>e_1</tex> и один раз для <tex>e_2</tex>. Аналогично, число строго несобственных раскрасок остовных подграфов, содержащих точно 3, 4 и более рёбер, будет вычтено соответствующее число раз.<br>Чтобы восстаносить баланс, мы добавим сумму <tex>\sum_{i}N(i, 2)x^i</tex>. При этом мы компенсируем двухкратное вычитание числа строго несобственных раскрасок, отвечающих остовным подграфам с двумя рёбрами, но снова возникает необходимость компенсации излишне добавленных чисел строго несобственных раскрасок для остовных подграфов с тремя, четырьмя, и более рёбрами.<br>Следовательно, число собственных раскрасок графа <tex>G</tex> равно <tex>x^n - \sum_{i}N(i, 1)x^i + \sum_{i}N(i, 2)x^i - \sum_{i}N(i, 3)x^i + ...</tex>. Так как <tex>N(n, 0) = 1</tex>, отсюда вытекает <tex>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</tex>.
+
<br>Пусть <tex>K</tex> - некоторый набор из <tex>x</tex> красок. Отображение <tex>\phi</tex> из <tex>VG</tex> в <tex>K</tex>, не являющееся раскраской графа <tex>G</tex>, будем называть его несобственной раскраской. Всего собственных и несобственных <tex>x</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> является строго несобственной раскраской его остовного подграфа. Cобственным раскраскам графа <tex>G</tex> отвечает нулевой остовный подграф.<br>Пусть <tex>N(i, j)</tex> - число остовных подграфов графа <tex>G</tex>, имеющих <tex>i</tex> компонент связности и <tex>j</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>.
 
}}
 
}}
  

Версия 10:41, 15 января 2011

Теорема (Уитни):
Пусть [math]G[/math] - обыкновенный [math](n, m)[/math] - граф. Тогда коэффициент при [math]x^i[/math], где [math]1\le i\le 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]\phi[/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] является строго несобственной раскраской его остовного подграфа. Cобственным раскраскам графа [math]G[/math] отвечает нулевой остовный подграф.
Пусть [math]N(i, j)[/math] - число остовных подграфов графа [math]G[/math], имеющих [math]i[/math] компонент связности и [math]j[/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]

Литература

  • Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Формула_Уитни&oldid=6799»