Гамильтоновы графы - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:22:36Z

rollbackEdits.php mass rollback

185.220.101.186 в 05:09, 1 сентября 2022

2022-09-01T05:09:39Z

91.245.38.252: /* Достаточные условия гамильтоновости графа */

2022-04-09T04:40:32Z

‎Достаточные условия гамильтоновости графа

91.245.38.252: /* Необходимые, но недостаточные условия гамильтоновости графа */

2022-04-09T04:39:20Z

‎Необходимые, но недостаточные условия гамильтоновости графа

188.134.81.244: Замена d (из предыдущей части решения) на d' (в текущей)

2021-12-20T22:22:44Z

Замена d (из предыдущей части решения) на d' (в текущей)

46.188.121.32: В этом разделе ничего не оптимизируется: выше находили самый дешевый гам. цикл, а здесь находим любой гам. путь, то есть другая задача.

2020-10-13T06:11:49Z

В этом разделе ничего не оптимизируется: выше находили самый дешевый гам. цикл, а здесь находим любой гам. путь, то есть другая задача.

93.185.30.49: Исправление опечаток

2019-01-31T11:28:47Z

Исправление опечаток

91.144.140.113: /* Основные определения */

2018-02-27T12:34:51Z

‎Основные определения

KokorinIlya: /* Основные определения */

2017-11-29T10:33:55Z

‎Основные определения

93.175.2.216: /* Оптимизация решения методом динамического программирования */

2016-06-19T15:03:32Z

‎Оптимизация решения методом динамического программирования

← Предыдущая		Версия 16:22, 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 Майкл Наки].
−	\|}
−
	[[Файл:Hamiltonial.png\|300px\|thumb\|right\|Граф додекаэдра с выделенным циклом Гамильтона]]		[[Файл:Hamiltonial.png\|300px\|thumb\|right\|Граф додекаэдра с выделенным циклом Гамильтона]]
	==Основные определения==		==Основные определения==

← Предыдущая		Версия 05:09, 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 Майкл Наки].
		+	\|}
		+
	[[Файл:Hamiltonial.png\|300px\|thumb\|right\|Граф додекаэдра с выделенным циклом Гамильтона]]		[[Файл:Hamiltonial.png\|300px\|thumb\|right\|Граф додекаэдра с выделенным циклом Гамильтона]]
	==Основные определения==		==Основные определения==

← Предыдущая		Версия 04:40, 9 апреля 2022
Строка 25:		Строка 25:
	Очевидно, что любой гамильтонов граф также и полугамильтонов.		Очевидно, что любой гамильтонов граф также и полугамильтонов.

−	==~~Необходимые, но недостаточные~~ условия гамильтоновости графа==	+	==Достаточные условия гамильтоновости графа==

@@ Строка 25: / Строка 25: @@
 Очевидно, что любой гамильтонов граф также и полугамильтонов.
-==Достаточные условия гамильтоновости графа==
+==Необходимые, но недостаточные условия гамильтоновости графа==
@@ Строка 88: / Строка 88: @@
 то граф <tex> G </tex> [[Гамильтоновы графы|гамильтонов]].
 }}
 == Задача о коммивояжере ==

@@ Строка 147: / Строка 147: @@
 d'[mask] = \left\{\begin{array}{llcl}
 mask &;\ |mask| = 1 \\
-\sum_{i \in [0..n-1] \& mask_i=1}\limits 2^i \cdot ((d[mask \oplus 2^i] \& M_i) \neq 0?1:0) &;\ |mask| > 1 \\
+\sum_{i \in [0..n-1] \& mask_i=1}\limits 2^i \cdot ((d'[mask \oplus 2^i] \& M_i) \neq 0?1:0) &;\ |mask| > 1 \\
 &;\ otherwise\\
 \end{array}\right.
 </tex>
-Особое внимание следует уделить выражению <tex>d[mask \oplus 2^i] \& M_i</tex> . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве <tex>mask</tex> без вершины <tex>i</tex>, а вторая — подмножество вершин, связанных с <tex>i</tex> ребром. Если эти множества пересекаются хотя бы по одной вершине (их <tex>\&</tex> не равен <tex>0</tex>), то, как нетрудно понять, в <tex>mask</tex> существует гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.
+Особое внимание следует уделить выражению <tex>d'[mask \oplus 2^i] \& M_i</tex> . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве <tex>mask</tex> без вершины <tex>i</tex>, а вторая — подмножество вершин, связанных с <tex>i</tex> ребром. Если эти множества пересекаются хотя бы по одной вершине (их <tex>\&</tex> не равен <tex>0</tex>), то, как нетрудно понять, в <tex>mask</tex> существует гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.
-Окончательная проверка состоит в сравнении <tex>d[2^n - 1]</tex> c <tex>0</tex>.
+Окончательная проверка состоит в сравнении <tex>d'[2^n - 1]</tex> c <tex>0</tex>.
 Это решение использует <tex>O(2^n)</tex> памяти и имеет асимптотику <tex>O(2^nn)</tex>.

@@ Строка 126: / Строка 126: @@
 Для того, чтобы восстановить сам путь, воспользуемся соотношением <tex> d[i][mask] = w(i, j) + d[j][mask - 2^j] </tex>,  которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния <tex> i = 0 </tex>, <tex> mask = 2^n - 1</tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> mask = mask - 2^j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> mask = 0 </tex>.
-===== Оптимизация решения методом динамического программирования =====
+===== Поиск любого гамильтонова пути методом динамического программирования =====
 Пусть <tex>d[mask][i]</tex> содержит булево значение — существует ли в подмножестве <tex>mask</tex> гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.

@@ Строка 128: / Строка 128: @@
 ===== Оптимизация решения методом динамического программирования =====
-Пусть <tex>dp[mask][i]</tex> содержит булево значение — существует ли в подмножества <tex>mask</tex> гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.
+Пусть <tex>d[mask][i]</tex> содержит булево значение — существует ли в подмножестве <tex>mask</tex> гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.
 Сама динамика будет такая: <br>
@@ Строка 141: / Строка 141: @@
 Это решение требует <tex>O(2^nn)</tex> памяти и <tex>O(2^nn^2)</tex> времени. Эту оценку можно улучшить, если изменить динамику следующим образом.
-Пусть теперь <tex>d'[mask]</tex> хранит маску подмножества всех вершин, для которых существует гамильтонов путь в подмножестве <tex>mask</tex>, заканчивающихся в этой вершине. Другими словами, сожмем предыдущую динамику: <tex>d'[mask]</tex> будет равно <tex>\sum_{i \in [0..n-1]}\limits d[mask][i] \cdot 2 ^i </tex>. Для графа <tex>G</tex> выпишем <tex>n</tex> масок <tex>M_i</tex>, для каждой вершины задающие множество вершин, которые связаны ребром в данной вершиной. То есть <tex>M_i = \sum_{j \in [0..n-1]}\limits 2^j \cdot ((i, j) \in E ? 1:0) </tex>.
+Пусть теперь <tex>d'[mask]</tex> хранит маску подмножества всех вершин, для которых существует гамильтонов путь в подмножестве <tex>mask</tex>, заканчивающихся в этой вершине. Другими словами, сожмем предыдущую динамику: <tex>d'[mask]</tex> будет равно <tex>\sum_{i \in [0..n-1]}\limits d[mask][i] \cdot 2 ^i </tex>. Для графа <tex>G</tex> выпишем <tex>n</tex> масок <tex>M_i</tex>, для каждой вершины задающие множество вершин, которые связаны ребром с данной вершиной. То есть <tex>M_i = \sum_{j \in [0..n-1]}\limits 2^j \cdot ((i, j) \in E ? 1:0) </tex>.
 Тогда динамика перепишется следующим образом: <br>

@@ Строка 3: / Строка 3: @@
 {{Определение
 |definition =
-'''Гамильтоновым путём''' (англ. ''Hamiltonian path'') называется простой путь, приходящий через каждую вершину графа ровно один раз.
+'''Гамильтоновым путём''' (англ. ''Hamiltonian path'') называется простой путь, проходящий через каждую вершину графа ровно один раз.
 }}