Раскраска графа - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:25:33Z

rollbackEdits.php mass rollback

103.251.167.21 в 05:01, 1 сентября 2022

2022-09-01T05:01:47Z

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

2015-11-08T13:47:00Z

Roman в 12:00, 8 ноября 2015

2015-11-08T12:00:53Z

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

2015-11-08T08:13:18Z

Martoon в 11:55, 6 января 2014

2014-01-06T11:55:11Z

Martoon: /* Хроматическое число */

2013-12-10T13:51:21Z

‎Хроматическое число

Igor buzhinsky: /* Раскраска графа */

2012-06-04T23:20:34Z

‎Раскраска графа

Русин Никита в 14:44, 5 апреля 2012

2012-04-05T14:44:13Z

Igor buzhinsky: /* Хроматические числа различных графов */

2012-02-06T06:53:20Z

‎Хроматические числа различных графов

← Предыдущая		Версия 16:25, 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 Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|definition= '''Правильной раскраской''' (англ. ''Regular coloring'') графа <tex>G(V,E)</tex> называется такое отображение <tex>\varphi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1 \ldots c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\varphi(u)\ne\varphi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.		\|definition= '''Правильной раскраской''' (англ. ''Regular coloring'') графа <tex>G(V,E)</tex> называется такое отображение <tex>\varphi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1 \ldots c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\varphi(u)\ne\varphi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.

← Предыдущая		Версия 05:01, 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 Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|definition= '''Правильной раскраской''' (англ. ''Regular coloring'') графа <tex>G(V,E)</tex> называется такое отображение <tex>\varphi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1 \ldots c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\varphi(u)\ne\varphi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.		\|definition= '''Правильной раскраской''' (англ. ''Regular coloring'') графа <tex>G(V,E)</tex> называется такое отображение <tex>\varphi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1 \ldots c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\varphi(u)\ne\varphi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.

@@ Строка 1: / Строка 1: @@
 {{Определение
-|definition= '''Правильной раскраской''' (англ. ''Regular coloring'') графа <tex>G(V,E)</tex> называется такое отображение <tex>\varphi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1...c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\varphi(u)\ne\varphi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.
+|definition= '''Правильной раскраской''' (англ. ''Regular coloring'') графа <tex>G(V,E)</tex> называется такое отображение <tex>\varphi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1 \ldots c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\varphi(u)\ne\varphi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.
 }}
 [[Файл:Paint.png|200px|thumb|center|Пример раскраски графа из четырех вершин.]]
@@ Строка 38: / Строка 38: @@
 ==Связь хроматического числа и хроматического многочлена==
-*Минимальное натуральное число, на котором хроматический многочлен для данного графа принимает натуральное значение, является хроматическим числом для данного графа. Поэтому если известен хроматический многочлен, то хроматическое число можно определить последовательной подстановкой.
+*Минимальное натуральное число, на котором хроматический многочлен для данного графа принимает натуральное значение, является хроматическим числом для данного графа. Поэтому если известен хроматический многочлен, то хроматическое число можно определить последовательной подстановкой. Однако задача о нахождении хроматического многочлена также не разрешима за полиномиальное время.
 *В обратную сторону, т.е. если известно хроматическое число, построить хроматический многочлен не получится. Так как оно не дает почти никакой информации о структуре графа.
@@ Строка 45: / Строка 45: @@
 ==Источники информации==
-. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
+* Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
-. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''
+* Харари Ф. {{---}} Теория графов. '''ISBN 978-5-397-00622-4'''
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Раскраски графов]]

@@ Строка 34: / Строка 34: @@
 {{main|Хроматический многочлен}}
 {{Определение
-|definition=Хроматический многочлен (англ. ''Chromatic polynomial'') <tex>P(G, t)</tex> {{---}} число способов раскрасить граф <tex>G</tex> в <tex>t</tex> цветов.
+|definition='''Хроматический многочлен''' (англ. ''Chromatic polynomial'') <tex>P(G, t)</tex> {{---}} число способов раскрасить граф <tex>G</tex> в <tex>t</tex> цветов.
 }}
 ==Примечания==
 <references/>

@@ Строка 1: / Строка 1: @@
 {{Определение
-|definition= '''Правильной раскраской''' (англ. regular coloring) графа <tex>G(V,E)</tex> называется такое отображение <tex>\phi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1...c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\phi(u)\ne\phi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.
+|definition= '''Правильной раскраской''' (англ. ''Regular coloring'') графа <tex>G(V,E)</tex> называется такое отображение <tex>\varphi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1...c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\varphi(u)\ne\varphi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.
 }}
 [[Файл:Paint.png|200px|thumb|center|Пример раскраски графа из четырех вершин.]]
@@ Строка 9: / Строка 9: @@
 Первоначально раскраски графов были нужны для составления географических карт<ref name="4problem"> [http://ru.wikipedia.org/wiki/Проблема_четырёх_красок Проблема четырёх красок]</ref>. Сегодня же они (в частности раскраска с использованием минимального количества цветов) используются, например, для составления расписаний, распределения регистров в микропроцессорах, распараллеливания численных методов.<ref name="pract">[http://ru.wikipedia.org/wiki/Практическое_применение_раскраски_графов Практическое применение раскраски графов]</ref>
-== Хроматическое число ==
+==Хроматические числа различных графов==
 {{Определение
 |id= chromatic_number_difinition
-|definition= '''Хроматическим числом''' (англ. chromatic number) <tex>\chi(G)</tex> графа <tex>G(V,E)</tex> называется такое минимальное число <tex>t</tex>, для которого существует <tex>t</tex>-раскраска графа.
+|definition= '''Хроматическим числом''' (англ. ''Chromatic number'') <tex>\chi(G)</tex> графа <tex>G(V,E)</tex> называется такое минимальное число <tex>t</tex>, для которого существует <tex>t</tex>-раскраска графа.
 }}
-== Хроматические числа различных графов ==
+* <tex>1</tex>-хроматические графы {{---}} это нулевые(не имеющие ребер) графы и только они. <tex>\chi(O_{n}) = 1</tex>.
-) <tex>\chi(K_{n}) = n</tex> {{---}} хроматическое число полного графа равно <tex>n</tex>.
+* <tex>\chi(K_{n}) = n</tex> {{---}} хроматическое число полного графа равно <tex>n</tex>.
-) <tex>\chi(C_{n}) =
+* <tex>\chi(C_{n}) =
     \begin{cases}
 \text{, if $n$ is even;}\\
@@ Строка 27: / Строка 26: @@
 </tex>
-) <tex>G</tex> - дерево, тогда <tex>\chi(G) = 2</tex>
+* <tex>G = (V, E)</tex> {{---}} двудольный граф, тогда <tex>\chi(G) = 2</tex>
-Задача о нахождении <tex>\chi(G)</tex> не разрешима за полиномиальное время.
+Задача о нахождении <tex>\chi(G)</tex> [[NP-полнота_задачи_о_раскраске_графа | не разрешима за полиномиальное время]].
-== Хроматический многочлен ==
+==Хроматический многочлен==
 {{main|Хроматический многочлен}}
 {{Определение
-|definition=Хроматический многочлен (англ. chromatic polynomial) <tex>P(G, t)</tex> {{---}} число способов раскрасить граф <tex>G</tex> в <tex>t</tex> цветов.
+|definition=Хроматический многочлен (англ. ''Chromatic polynomial'') <tex>P(G, t)</tex> {{---}} число способов раскрасить граф <tex>G</tex> в <tex>t</tex> цветов.
 }}
-== Источники ==
+==Источники информации==
 . Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
 . Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Раскраски графов]]

@@ Строка 4: / Строка 4: @@
 |definition= '''Правильной раскраской графа''' <tex>G(V,E)</tex> называется такое отображение <tex>\phi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1...c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\phi(u)\ne\phi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.
 }}
-[[Файл:Paint.png|200px]]<br>
+[[Файл:Paint.png|200px|thumb|center|Пример раскраски графа из четырех вершин.]]
 Раскраской графа чаще всего называют именно правильную раскраску.
 <br clear = "all">
 == Хроматическое число ==
 {{Определение

@@ Строка 14: / Строка 14: @@
 ) <tex>1</tex>-хроматические графы - это нулевые графы и только они. <tex>\chi(O_{n}) = 1</tex>.
-) <tex>\chi(K_{n}) = n</tex> - хроматическое число полного графа равно <tex>n</tex>.
+) <tex>\chi(K_{n}) = n</tex> {{---}} хроматическое число полного графа равно <tex>n</tex>.
 ) <tex>\chi(C_{n}) =