Формула Зыкова — различия между версиями
Roman (обсуждение | вклад) |
Vsklamm (обсуждение | вклад) |
||
(не показаны 2 промежуточные версии 1 участника) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
+ | |id=def_1 | ||
|definition= | |definition= | ||
'''Независимым множеством''' (англ. ''Independent set'') в графе <tex>G = (V, E)</tex> называется непустое множество <tex>S \subset V: \forall v,u \in S\</tex> ребро <tex>(v,u) \notin E</tex>. | '''Независимым множеством''' (англ. ''Independent set'') в графе <tex>G = (V, E)</tex> называется непустое множество <tex>S \subset V: \forall v,u \in S\</tex> ребро <tex>(v,u) \notin E</tex>. | ||
Строка 10: | Строка 11: | ||
<tex>P(G,x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}</tex>, где <tex>pt(G,i)</tex> — число способов разбить вершины <tex>G</tex> на <tex>i</tex> независимых множеств, <tex>n = |V|</tex>, а <tex> x^{\underline i} = x \cdot (x - 1) \cdot \ldots \cdot (x - i + 1)</tex> {{---}} нисходящая факториальная степень. | <tex>P(G,x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}</tex>, где <tex>pt(G,i)</tex> — число способов разбить вершины <tex>G</tex> на <tex>i</tex> независимых множеств, <tex>n = |V|</tex>, а <tex> x^{\underline i} = x \cdot (x - 1) \cdot \ldots \cdot (x - i + 1)</tex> {{---}} нисходящая факториальная степень. | ||
|proof= | |proof= | ||
− | В правильной раскраске вершины, имеющие одинаковый цвет, не смежны, поэтому все такие вершины могут быть объединены в одно независимое множество | + | В правильной раскраске вершины, имеющие одинаковый цвет, не смежны, поэтому все такие вершины могут быть объединены в одно независимое множество. Перебрав все возможные разбиения на независимые множества с последующей их всевозможной покраской <tex>x</tex> доступными цветами получим искомое число способов раскраски графа <tex>G</tex> в <tex>x</tex> цветов. |
+ | |||
+ | Теперь проделаем это более формально. Подсчитаем число раскрасок графа <tex>G</tex>, в которых используется точно <tex>i</tex> цветов, для этого его нужно разбить на <tex>i</tex> независимых множеств и вершины в каждом таком классе покрасить в один из <tex>i</tex> цветов, отличный от всех других множеств, так как мы не делаем никаких предположений о связи между классами. | ||
+ | |||
+ | Рассмотрим случай, где <tex>1 \leqslant i \leqslant x</tex>. Чтобы получить такую раскраску зафиксируем какое-нибудь разбиение множества вершин графа <tex>G</tex> на <tex>i</tex> независимых множеств, затем берем один из классов в разбиении и | ||
раскрашиваем его в один из <tex>x</tex> цветов, потом берем следующий класс и окрашиваем его вершины в одинаковый цвет любой из <tex>x - 1</tex> оставшихся красок и т.д. Всего таких способов разбиения существует <tex>pt(G,i)</tex>. | раскрашиваем его в один из <tex>x</tex> цветов, потом берем следующий класс и окрашиваем его вершины в одинаковый цвет любой из <tex>x - 1</tex> оставшихся красок и т.д. Всего таких способов разбиения существует <tex>pt(G,i)</tex>. | ||
Следовательно, перебрав все возможные разбиения на <tex>i</tex> независимых множеств, получим, что число интересующих нас раскрасок графа <tex>G</tex> равно <tex>pt(G,i) \cdot x \cdot (x - 1) \cdot \ldots \cdot (x - i + 1) = pt(G,i) \cdot x^{\underline i}</tex>. | Следовательно, перебрав все возможные разбиения на <tex>i</tex> независимых множеств, получим, что число интересующих нас раскрасок графа <tex>G</tex> равно <tex>pt(G,i) \cdot x \cdot (x - 1) \cdot \ldots \cdot (x - i + 1) = pt(G,i) \cdot x^{\underline i}</tex>. | ||
− | Заметим теперь, что при <tex>i > x</tex> число <tex>x</tex>-раскрасок, в которых используется точно <tex>i</tex> цветов, равно <tex>0</tex> и при этом <tex>x^{\underline i}</tex> тоже равно <tex>0</tex>. Суммирование по <tex>i</tex> от <tex>1</tex> до <tex>n</tex> даст полное число способов. | + | |
+ | Заметим теперь, что при <tex>i > x</tex> число <tex>x</tex>-раскрасок, в которых используется точно <tex>i</tex> цветов, равно <tex>0</tex> и при этом <tex>x^{\underline i}</tex> тоже равно <tex>0</tex>. | ||
+ | |||
+ | Суммирование по <tex>i</tex> от <tex>1</tex> до <tex>n</tex> даст полное число способов. | ||
+ | }} | ||
'''Примечание''': в такой формулировке задача о поиске хроматического многочлена сводится к отысканию количества способов разбить граф на независимые множества, что в свою очередь также [[Примеры_NP-полных_языков#NP-полнота поиска максимального независимого множества | не разрешимо за полиномиальное время]]. | '''Примечание''': в такой формулировке задача о поиске хроматического многочлена сводится к отысканию количества способов разбить граф на независимые множества, что в свою очередь также [[Примеры_NP-полных_языков#NP-полнота поиска максимального независимого множества | не разрешимо за полиномиальное время]]. | ||
− | |||
==См. также== | ==См. также== | ||
*[[Формула Уитни]] | *[[Формула Уитни]] |
Версия 18:58, 27 октября 2018
Определение: |
Независимым множеством (англ. Independent set) в графе | называется непустое множество ребро .
Теорема (Зыкова): |
Для хроматического многочлена графа верна формула:
, где — число способов разбить вершины на независимых множеств, , а — нисходящая факториальная степень. |
Доказательство: |
В правильной раскраске вершины, имеющие одинаковый цвет, не смежны, поэтому все такие вершины могут быть объединены в одно независимое множество. Перебрав все возможные разбиения на независимые множества с последующей их всевозможной покраской доступными цветами получим искомое число способов раскраски графа в цветов.Теперь проделаем это более формально. Подсчитаем число раскрасок графа , в которых используется точно цветов, для этого его нужно разбить на независимых множеств и вершины в каждом таком классе покрасить в один из цветов, отличный от всех других множеств, так как мы не делаем никаких предположений о связи между классами.Рассмотрим случай, где . Чтобы получить такую раскраску зафиксируем какое-нибудь разбиение множества вершин графа на независимых множеств, затем берем один из классов в разбиении и раскрашиваем его в один из цветов, потом берем следующий класс и окрашиваем его вершины в одинаковый цвет любой из оставшихся красок и т.д. Всего таких способов разбиения существует . Следовательно, перебрав все возможные разбиения на независимых множеств, получим, что число интересующих нас раскрасок графа равно .Заметим теперь, что при Суммирование по число -раскрасок, в которых используется точно цветов, равно и при этом тоже равно . от до даст полное число способов. |
Примечание: в такой формулировке задача о поиске хроматического многочлена сводится к отысканию количества способов разбить граф на независимые множества, что в свою очередь также не разрешимо за полиномиальное время.
См. также
Источники информации
- Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: Графы, матроиды, алгоритмы. — Ижевск: НИЦ «РХД», 2001. С. 140-141. — ISBN 5-93972-076-5