Формула Зыкова - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:41:28Z

rollbackEdits.php mass rollback

185.244.195.157 в 03:32, 1 сентября 2022

2022-09-01T03:32:31Z

94.241.200.200 в 21:49, 5 октября 2020

2020-10-05T21:49:06Z

Vsklamm в 15:58, 27 октября 2018

2018-10-27T15:58:09Z

Roman в 17:25, 8 ноября 2015

2015-11-08T17:25:02Z

Roman в 17:21, 8 ноября 2015

2015-11-08T17:21:27Z

Roman в 17:10, 8 ноября 2015

2015-11-08T17:10:37Z

Roman в 17:09, 8 ноября 2015

2015-11-08T17:09:09Z

Roman в 16:39, 8 ноября 2015

2015-11-08T16:39:54Z

Roman в 13:59, 8 ноября 2015

2015-11-08T13:59:33Z

← Предыдущая		Версия 16:41, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|id=def_1		\|id=def_1

← Предыдущая		Версия 03:32, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|id=def_1		\|id=def_1

@@ Строка 2: / Строка 2: @@
 |id=def_1
 |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>.
 }}
 {{Теорема

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition=
 '''Независимым множеством''' (англ. ''Independent set'') в графе <tex>G = (V, E)</tex> называется непустое множество <tex>S \subset V: \forall v,u \in S\</tex> ребро <tex>(v,u) \notin E</tex>.

@@ Строка 10: / Строка 10: @@
 <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=
-В правильной раскраске вершины, имеющие одинаковый цвет, не смежны, поэтому все такие вершины могут быть объединены в одно независимое множество, так как все они попарно не смежны. Перебрав все возможные разбиения на независимые множества с последующей их всевозможной покраской <tex>x</tex> доступными цветами получим искомое число способов раскраски графа <tex>G</tex> в <tex>x</tex> цветов.
+В правильной раскраске вершины, имеющие одинаковый цвет, не смежны, поэтому все такие вершины могут быть объединены в одно независимое множество. Перебрав все возможные разбиения на независимые множества с последующей их всевозможной покраской <tex>x</tex> доступными цветами получим искомое число способов раскраски графа <tex>G</tex> в <tex>x</tex> цветов.
 Теперь проделаем это более формально. Подсчитаем число раскрасок графа <tex>G</tex>, в которых используется точно <tex>i</tex> цветов, для этого его нужно разбить на <tex>i</tex> независимых множеств и вершины в каждом таком классе покрасить в один из <tex>i</tex> цветов, отличный от всех других множеств, так как мы не делаем никаких предположений о связи между классами.

@@ Строка 10: / Строка 10: @@
 <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=
-В правильной раскраске вершины, имеющие одинаковый цвет, не смежны, поэтому все такие вершины могут быть объединены в одно независимое множество, так как все они попарно не смежны. Перебрав все возможные разбиения на независимые множества с последующей их всевозможной покраской <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>G</tex> в <tex>x</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 > 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-полнота поиска максимального независимого множества | не разрешимо за полиномиальное время]].
 ==См. также==
 *[[Формула Уитни]]

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition=
-Независимым множеством (кокликой, англ. coclique) в графе <tex>G</tex> называется непустое множество <tex>S \subset V: \forall v,u \in S\</tex> ребро <tex>(v,u) \notin E</tex>.
+'''Независимым множеством''' (кокликой, англ. ''Coclique'') в графе <tex>G = (V, E)</tex> называется непустое множество <tex>S \subset V: \forall v,u \in S\</tex> ребро <tex>(v,u) \notin E</tex>.
 }}
 {{Теорема
@@ Строка 10: / Строка 10: @@
 <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>.
 |proof=
-Пусть в <tex>x</tex>-раскраске графа <tex>G</tex> используется точно <tex>i</tex> цветов.
+Подсчитаем число раскрасок графа <tex>G</tex>, в которых используется точно <tex>i</tex> цветов, где <tex>1 \leqslant i \leqslant x</tex>. Чтобы получить такую раскраску
-* <tex>1 \le i \le x</tex>
+сначала одним из <tex>pt(G,i)</tex> способов выбираем разбиение множества вершин графа <tex>G</tex> на <tex>i</tex> независимых множеств, затем берем один из классов в разбиении и
-Для получения такой раскраски сначала выберем одним из <tex>pt(G,i)</tex> способов разбиение графа <tex>G</tex> на <tex>i</tex> независимых множеств, а затем одним из <tex>{x\choose i} i! = x^{\underline i}</tex> способов <tex>i</tex> упорядоченных цветов из <tex>x</tex>.
+раскрашиваем его в один из <tex>x</tex> цветов, потом берем следующий класс и окрашиваем его вершины в одинаковый цвет любой из <tex>x - 1</tex> оставшихся красок и т.д.
-* <tex>i > x</tex>
+==Источники информации==
-Число <tex>x</tex>-раскрасок графа <tex>G</tex>, в которых используется точно <tex>i</tex> цветов, равно <tex>0</tex>, так же как и <tex>x^{\underline i}</tex>.
+* ''Асанов М. О., Баранский В. А., Расин В. В.'' Дискретная математика: Графы, матроиды, алгоритмы. {{---}} Ижевск: НИЦ «РХД», 2001. С. 140-141. {{---}}  '''ISBN 5-93972-076-5'''
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Раскраски графов]]