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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:21:48Z

rollbackEdits.php mass rollback

194.26.192.187 в 05:24, 1 сентября 2022

2022-09-01T05:24:37Z

E DNK: Мы укладываем сегмент в грань из множества Г(Si), а не |Г(Si)|, поскольку модуль - это мощность множества граней.

2021-04-17T12:24:12Z

Мы укладываем сегмент в грань из множества Г(Si), а не |Г(Si)|, поскольку модуль - это мощность множества граней.

93.175.2.87: /* Входные данные */

2020-03-11T19:35:50Z

‎Входные данные

93.175.2.171: Точки сочленения

2019-03-01T20:44:34Z

Точки сочленения

Анна: /* Доказательство корректности гамма-алгоритма */

2015-11-19T20:24:17Z

‎Доказательство корректности гамма-алгоритма

Анна: /* Общий шаг */

2015-11-19T20:19:52Z

‎Общий шаг

Анна: /* Инициализация */

2015-11-19T20:19:36Z

‎Инициализация

Анна: /* Входные данные */

2015-11-19T20:16:58Z

‎Входные данные

Анна: /* См. также */

2015-11-19T20:15:24Z

‎См. также

← Предыдущая		Версия 16:21, 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=Определить, является ли граф планарным, и, если да, произвести его плоскую укладку.		\|definition=Определить, является ли граф планарным, и, если да, произвести его плоскую укладку.

← Предыдущая		Версия 05:24, 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=Определить, является ли граф планарным, и, если да, произвести его плоскую укладку.		\|definition=Определить, является ли граф планарным, и, если да, произвести его плоскую укладку.

@@ Строка 56: / Строка 56: @@
 Пусть грань <tex>\Gamma</tex> '''вмещает''' сегмент <tex>S</tex>, если номера всех контактных вершин <tex>S</tex> принадлежат этой грани, <tex>S \subset \Gamma</tex>. Очевидно, таких граней может быть несколько. Множество таких граней обозначим <tex>\Gamma(S)</tex>, а их число {{---}} <tex>|\Gamma(S)|</tex>.
-Итак, рассмотрим все сегменты <tex>S_{i}</tex> и для каждого определим число <tex>|\Gamma(S_{i})|</tex>. Если найдется такой номер <tex>i</tex>, что <tex>|\Gamma(S_{i})| = 0</tex>, то граф не планарен, алгоритм завершает работу. Иначе выбираем такой сегмент <tex>S_{i}</tex>, для которого число <tex>|\Gamma(S_{i})|</tex> минимально. Если таких сегментов несколько, можно выбрать любой из них. Найдем в этом сегменте цепь между двумя контактными вершинами и уложим ее в любую грань из множества <tex>|\Gamma(S_{i})|</tex>, совместив контактные вершины сегмента с соответствующими вершинами грани. Выбранная грань разобьется на две. Выбранный сегмент после того, как из него взяли цепь, либо исчезнет, либо распадется на меньшие части, в которых будут новые контактные вершины, ведущие к вершинам обновленного <tex>G_{plane}</tex>.
+Итак, рассмотрим все сегменты <tex>S_{i}</tex> и для каждого определим число <tex>|\Gamma(S_{i})|</tex>. Если найдется такой номер <tex>i</tex>, что <tex>|\Gamma(S_{i})| = 0</tex>, то граф не планарен, алгоритм завершает работу. Иначе выбираем такой сегмент <tex>S_{i}</tex>, для которого число <tex>|\Gamma(S_{i})|</tex> минимально. Если таких сегментов несколько, можно выбрать любой из них. Найдем в этом сегменте цепь между двумя контактными вершинами и уложим ее в любую грань из множества <tex>\Gamma(S_{i})</tex>, совместив контактные вершины сегмента с соответствующими вершинами грани. Выбранная грань разобьется на две. Выбранный сегмент после того, как из него взяли цепь, либо исчезнет, либо распадется на меньшие части, в которых будут новые контактные вершины, ведущие к вершинам обновленного <tex>G_{plane}</tex>.
 В примере для любого <tex>i</tex>: <tex>S_{i} \subset \{\Gamma_{1}, \Gamma_{2}\}</tex>, то есть <tex>|\Gamma(S_{i})| = 2</tex>. Следовательно, можем выбрать любой <tex>S_{i}</tex>. Пусть это будет сегмент <tex>S_{1}</tex>. В нем есть цепь <tex>\{1, 4\}</tex>. Вставим эту цепь в грань <tex>\Gamma_{1}</tex>, например, и этот сегмент исчезнет. После укладки цепи граф <tex>G</tex> и сегменты будут выглядеть так (рис. 4):

@@ Строка 12: / Строка 12: @@
 # Граф содержит хотя бы один цикл.
 # Граф не имеет [[Мост, эквивалентные определения|мостов]].
 Если нарушено свойство 1, то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство 2, то граф {{---}} дерево и [[Укладка дерева|нарисовать его плоскую укладку]] тривиально.

@@ Строка 12: / Строка 12: @@
 # Граф содержит хотя бы один цикл.
 # Граф не имеет [[Мост, эквивалентные определения|мостов]].
 Если нарушено свойство 1, то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство 2, то граф {{---}} дерево и [[Укладка дерева|нарисовать его плоскую укладку]] тривиально.
@@ Строка 52: / Строка 53: @@
 |}
-Пусть в каком-то сегменте нет ни одной контактной вершины. В таком случае граф до выделения <tex>G_{plane}</tex> был несвязным, что противоречит условию. Пусть контактная вершина в сегменте только одна. Это значит, что в графе был мост, чего быть не может так же по условию. Таким образом, в каждом сегменте имеется не менее двух контактных вершин. Соответственно, в каждом сегменте есть цепь между любой парой контактных вершин.
+Пусть в каком-то сегменте нет ни одной контактной вершины. В таком случае граф до выделения <tex>G_{plane}</tex> был несвязным, что противоречит условию. Пусть контактная вершина в сегменте только одна. Это значит, что в графе был мост или точка сочленения, чего быть не может так же по условию. Таким образом, в каждом сегменте имеется не менее двух контактных вершин. Соответственно, в каждом сегменте есть цепь между любой парой контактных вершин.
 Пусть грань <tex>\Gamma</tex> '''вмещает''' сегмент <tex>S</tex>, если номера всех контактных вершин <tex>S</tex> принадлежат этой грани, <tex>S \subset \Gamma</tex>. Очевидно, таких граней может быть несколько. Множество таких граней обозначим <tex>\Gamma(S)</tex>, а их число {{---}} <tex>|\Gamma(S)|</tex>.

@@ Строка 143: / Строка 143: @@
 |statement=Если результатом некоторого шага работы гамма-алгоритма является частичная укладка <tex>G'</tex> планарного графа <tex>G</tex> такая, что <tex>|\Gamma(S)| \geqslant 2</tex> для любого сегмента <tex>S</tex> относительно <tex>G'</tex>, то <tex>A(G')</tex> {{---}} [[Двудольные графы и раскраска в 2 цвета|двудольный граф]].
-|proof=Докажем от противного. Пусть <tex>A(G')</tex> {{---}} не двудольный. Тогда по [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B2%D1%83%D0%B4%D0%BE%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D1%84%D1%8B_%D0%B8_%D1%80%D0%B0%D1%81%D0%BA%D1%80%D0%B0%D1%81%D0%BA%D0%B0_%D0%B2_2_%D1%86%D0%B2%D0%B5%D1%82%D0%B0#.D0.A2.D0.B5.D0.BE.D1.80.D0.B5.D0.BC.D0.B0_.D0.9A.D0.B5.D0.BD.D0.B8.D0.B3.D0.B0 теореме Кенинга] в нем есть цикл нечетной длины. Этому циклу соответствует некоторая последовательность сегментов  <tex>S_{1}, S_{2}, \cdots S_{2m+1}, S_{1}</tex> относительно <tex>G'</tex>, в которой каждые соседние сегменты конфликтующие по определению. По лемме 1 <tex>\Gamma(S_{i}) = \{\Gamma_{1}, \Gamma_{2}\}, i \in \{1 \cdots 2m+1\}</tex>. Так как <tex>G'</tex> {{---}} частичная укладка графа, то все сегменты <tex>S_{1}, S_{2}, \cdots S_{2m+1}</tex> могут быть уложены. А так как соседние сегменты этой последовательности конфликтующие, то они должны быть уложены в разные грани, что невозможно, так как число сегментов в последовательности нечетное. Получили противоречие. Следовательно, <tex>A(G')</tex> {{---}} двудольный.
+|proof=Докажем от противного. Пусть <tex>A(G')</tex> {{---}} не двудольный. Тогда по [[Двудольные графы и раскраска в 2 цвета#Теорема Кенига|теореме Кенинга]] в нем есть цикл нечетной длины. Этому циклу соответствует некоторая последовательность сегментов  <tex>S_{1}, S_{2}, \cdots S_{2m+1}, S_{1}</tex> относительно <tex>G'</tex>, в которой каждые соседние сегменты конфликтующие по определению. По лемме 1 <tex>\Gamma(S_{i}) = \{\Gamma_{1}, \Gamma_{2}\}, i \in \{1 \cdots 2m+1\}</tex>. Так как <tex>G'</tex> {{---}} частичная укладка графа, то все сегменты <tex>S_{1}, S_{2}, \cdots S_{2m+1}</tex> могут быть уложены. А так как соседние сегменты этой последовательности конфликтующие, то они должны быть уложены в разные грани, что невозможно, так как число сегментов в последовательности нечетное. Получили противоречие. Следовательно, <tex>A(G')</tex> {{---}} двудольный.
 }}

@@ Строка 40: / Строка 40: @@
 === Общий шаг ===
-Второй этап - общий шаг.
+Второй этап {{---}} общий шаг.
 Построим множество '''сегментов'''. Каждый сегмент <tex>S</tex> относительно уже построенного <tex>G_{plane}</tex> представляет собой одно из двух:

@@ Строка 28: / Строка 28: @@
 === Инициализация ===
-Первый этап - '''инициализация''' алгоритма.
+Первый этап {{---}} '''инициализация''' алгоритма.
 В графе <tex>G</tex> выбирается [[Использование обхода в глубину для поиска цикла|любой простой цикл]] и производится его укладка на плоскость. Пусть в примере это будет цикл <tex>\{1, 2, 3, 4, 5, 6\}</tex>. После его укладки получаем две грани: <tex>\Gamma_{1}</tex> и <tex>\Gamma_{2}</tex> (рис. 2).

@@ Строка 13: / Строка 13: @@
 # Граф не имеет [[Мост, эквивалентные определения|мостов]].
-Если нарушено свойство 1, то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство 2, то граф {{---}} дерево и нарисовать его плоскую укладку тривиально.
+Если нарушено свойство 1, то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство 2, то граф {{---}} дерево и [[Укладка дерева|нарисовать его плоскую укладку]] тривиально.
 Более подробно рассмотрим случай, когда в графе <tex>G</tex> нарушено свойство 3. Сначала все мосты нужно убрать, далее произвести отдельную укладку всех компонент следующим образом: уложим одну компоненту связности, а следующую компоненту, связанную с первой в графе <tex>G</tex> мостом, будем рисовать в той грани, в которой лежит вершина, принадлежащая мосту. Иначе может сложиться ситуация, когда концевая вершина моста будет находиться внутри плоского графа, а следующая компонента {{---}} снаружи. Таким образом мы сможем соединить мостом нужные вершины. Далее будем так поступать с каждой новой компонентой.

@@ Строка 172: / Строка 172: @@
 ==См. также==
 * [[Теорема Понтрягина-Куратовского|Теорема Понтрягина-Куратовского]]
 == Источники информации ==