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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 8 промежуточных версий 6 участников)
Строка 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 \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>
+
Пусть <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=
 
|proof=
<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> является строго несобственной раскраской его остовного подграфа. Собственным раскраскам графа <tex>G</tex> отвечает нулевой остовный подграф.<br>Пусть <tex>N(i, j)</tex> — число остовных подграфов графа <tex>G</tex>, имеющих <tex>i</tex> компонент связности и <tex>j</tex> рёбер.<br>
+
 
Из общего числа <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>K</tex> — некоторый набор из <tex>x</tex> красок. Отображение <tex>\varphi</tex> из множества вершин  <tex>V</tex> в <tex>K</tex>, не являющееся раскраской графа <tex>G</tex>, будем называть его ''несобственной'' раскраской. То есть, для того, чтобы отображение было несобственной раскраской, цвет концов хотя бы одного ребра должен совпадать. ''Собственной'' раскраской будем называть раскраску графа. Всего собственных и несобственных <tex>x</tex>-раскрасок графа <tex>G</tex> — <tex>x^n</tex>.
Добавим сумму <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>.
+
Возьмём некоторую собственную или несобственную раскраску графа <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> отвечает нулевой остовный подграф.
 +
 
 +
Пусть <tex>N(i, j)</tex> — число остовных подграфов графа <tex>G</tex>, имеющих <tex>i</tex> компонент связности и <tex>j</tex> рёбер.
 +
 
 +
Из общего числа <tex>x^n</tex> собственных и несобственных раскрасок вычтем число строго несобственных раскрасок остовных подграфов, имеющих ровно одно ребро. Если мы вычтем сумму <tex> \sum \limits_{i}{N(i, 1)x^i} </tex>, то мы вычтем помимо указанного числа ещё и некоторую избыточную величину. Действительно, рассмотрим два различных ребра графа <tex>G</tex>: <tex>e_1</tex> и <tex>e_2</tex>. В число строго несобственных раскрасок остовного подграфа, содержащего только ребро <tex>e_1</tex> попадут раскраски, у которых концы <tex>e_2</tex> имеют одинаковый цвет. То же самое верно и для остовного подграфа, содержащего только ребро <tex>e_2</tex>. Получается, что мы дважды вычтем число строго несобственных раскрасок для остовного подграфа <tex>G</tex>, содержащего два ребра: <tex>e_1</tex> и <tex>e_2</tex>. Аналогично будет вычтено число строго несобственных раскрасок остовных подграфов с большим числом ребер.
 +
 
 +
Попытаемся скомпенсировать двукратное вычитание добавлением <tex>\sum \limits_{i}{N(i, 2)x^i}</tex>, однако при этом добавится излишек строго несобственных раскрасок для остовных подграфов с тремя, четырьмя и более ребрами.  
 +
Подобную конструкцию можно рассчитать по [[Формула включения-исключения|формуле включения-исключения]]. 
 +
Воспользуемся формулой и получим число собственных раскрасок графа <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>.
 
}}
 
}}
 
+
==См. также==
==Литература==
+
*[[Формула Зыкова]]
* Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
+
==Источники информации==
 +
* Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. - СПб.: Издательство "Лань", 2010. - 368 с.: ил. - (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Раскраски графов ]]
 
[[Категория: Раскраски графов ]]

Текущая версия на 19:36, 4 сентября 2022

Теорема (Уитни):
Пусть [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}{\bigg(\sum \limits_{j=0}^{m}{(-1)^jN(i, j)\bigg)x^i}}.[/math]
Доказательство:
[math]\triangleright[/math]

Пусть [math]K[/math] — некоторый набор из [math]x[/math] красок. Отображение [math]\varphi[/math] из множества вершин [math]V[/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