Теорема Фари - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:11:02Z

rollbackEdits.php mass rollback

185.220.100.252 в 06:14, 1 сентября 2022

2022-09-01T06:14:07Z

Shersh в 19:09, 4 октября 2014

2014-10-04T19:09:30Z

Shersh: /* Ссылки */

2014-09-01T13:43:43Z

‎Ссылки

Valery в 15:57, 18 ноября 2013

2013-11-18T15:57:35Z

Valery в 15:41, 18 ноября 2013

2013-11-18T15:41:58Z

Valery в 15:39, 18 ноября 2013

2013-11-18T15:39:15Z

Valery в 13:57, 18 ноября 2013

2013-11-18T13:57:34Z

Valery в 13:56, 18 ноября 2013

2013-11-18T13:56:36Z

Valery в 13:46, 18 ноября 2013

2013-11-18T13:46:48Z

← Предыдущая		Версия 16:11, 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 Майкл Наки].
−	\|}
−
	Теорема была независимо доказана Клаусом Вагнером (Klaus Wagner) в 1936ом году и Иштваном Фари (István Fáry) в 1948ом году. Иногда ее называют теоремой Фари-Вагнера.		Теорема была независимо доказана Клаусом Вагнером (Klaus Wagner) в 1936ом году и Иштваном Фари (István Fáry) в 1948ом году. Иногда ее называют теоремой Фари-Вагнера.

← Предыдущая		Версия 06:14, 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 Майкл Наки].
		+	\|}
		+
	Теорема была независимо доказана Клаусом Вагнером (Klaus Wagner) в 1936ом году и Иштваном Фари (István Fáry) в 1948ом году. Иногда ее называют теоремой Фари-Вагнера.		Теорема была независимо доказана Клаусом Вагнером (Klaus Wagner) в 1936ом году и Иштваном Фари (István Fáry) в 1948ом году. Иногда ее называют теоремой Фари-Вагнера.

@@ Строка 24: / Строка 24: @@
 База индукции, когда <tex>|V|=3</tex>, выполняется тривиальным образом.
-Предположим, что графы с любым числом вершин <tex>|V| \geqslant 4</tex>, мы можем нарисовать требуемым образом.
+Предположим, что графы с любым числом вершин меньше <tex>|V| \geqslant 4</tex>, мы можем нарисовать требуемым образом.
 Рассмотрим ребро <tex>vw</tex>, [[Матрица инцидентности графа#definc | инцидентное]] внутренней вершине глубочайшего разделяющего треугольника, то есть такого, который не содержит внутри себя других разделяющих треугольников. Если в графе нет разделяющих треугольников, то возьмём любое ребро. Тогда <tex>vw</tex> {{---}} граница двух граней <tex>vwp</tex> и <tex>vwq</tex>.

@@ Строка 66: / Строка 66: @@
 * [[Укладка графа на плоскости]]
-==Ссылки==
+==Источники информации==
 * [[wikipedia:Fáry's_theorem | Wikipedia {{---}} Fáry's theorem ]]
 * [http://arxiv.org/abs/cs/0505047 Доказательство теоремы Фари]

@@ Строка 21: / Строка 21: @@
 |proof=
-Докажем теорему для плоской триангуляции графа <tex>G</tex>. Ее можно достичь, добавив в <tex>G</tex> необходимое количество ребер. Применим индукцию по числу вершин <tex>V</tex>.
+Докажем теорему для плоской триангуляции графа <tex>G</tex>. Ее можно достичь, добавив в <tex>G</tex> необходимое количество ребер. Применим индукцию по числу вершин <tex>|V|</tex>.
-База индукции, когда <tex>V=3</tex>, выполняется тривиальным образом.
+База индукции, когда <tex>|V|=3</tex>, выполняется тривиальным образом.
-Предположим, что графы с любым числом вершин <tex>V \geqslant 4</tex>, мы можем нарисовать требуемым образом.
+Предположим, что графы с любым числом вершин <tex>|V| \geqslant 4</tex>, мы можем нарисовать требуемым образом.
-Рассмотрим ребро <tex>vw</tex>, инцидентное внутренней вершине глубочайшего разделяющего треугольника, то есть такого, который не содержит внутри себя других разделяющих треугольников. Если в графе нет разделяющих треугольников, то возьмём любое ребро. Тогда <tex>vw</tex> {{---}} граница двух граней <tex>vwp</tex> и <tex>vwq</tex>.
+Рассмотрим ребро <tex>vw</tex>, [[Матрица инцидентности графа#definc | инцидентное]] внутренней вершине глубочайшего разделяющего треугольника, то есть такого, который не содержит внутри себя других разделяющих треугольников. Если в графе нет разделяющих треугольников, то возьмём любое ребро. Тогда <tex>vw</tex> {{---}} граница двух граней <tex>vwp</tex> и <tex>vwq</tex>.
 [[File:Fary2.png|250px|Рисунок 2]]
@@ Строка 35: / Строка 35: @@
 [[File:Fary3.png|250px|Рисунок 3]]
-Мы получили граф <tex>G'</tex>, с меньшим числом вершин равным <tex>V - 1</tex>, то есть его можно уложить на плоскости требуемым образом: все ребра прямые (и сохранен обход по часовой стрелке ребер инцидентных <tex>s</tex>).
+Мы получили граф <tex>G'</tex>, с меньшим числом вершин равным <tex>V - 1</tex>, то есть его можно уложить на плоскости требуемым образом: все ребра прямые (и сохранен обход по часовой стрелке ребер, инцидентных <tex>s</tex>).
 Для любого <tex>\varepsilon > 0</tex> обозначим <tex>C_{\varepsilon}(s)</tex> {{---}} круг радиуса <tex>\varepsilon</tex>, с вершиной <tex>s</tex>  в центре.
 Для каждого соседа <tex>t</tex> вершины <tex>s</tex> в графе <tex>G'</tex> обозначим <tex>R_{\varepsilon}(t)</tex> объединение всех отрезков, проведённых из <tex>t</tex> в <tex>C_{\varepsilon}(s)</tex>.

@@ Строка 3: / Строка 3: @@
 {{Определение
 |id=def1
-|definition='''Триангуляция графа''' {{---}} представление [[Укладка графа на плоскости#defplanar | планарного графа]] на плоскости в таком виде, что каждая его грань ограничена тремя ребрами (является треугольником).
+|definition='''Триангуляция графа''' (англ. ''triangulation'') {{---}} представление [[Укладка графа на плоскости#defplanar | планарного графа]] на плоскости в таком виде, что каждая его грань ограничена тремя ребрами (является треугольником).
 }}
 {{Определение
 |id=def2
-|definition='''Разделяющий треугольник''' {{---}} цикл длины <tex>3</tex> в графе <tex>G</tex>, внутри и снаружи которого находятся вершины графа.
+|definition='''Разделяющий треугольник''' (англ. ''separating triangle'') {{---}} цикл длины <tex>3</tex> в графе <tex>G</tex>, внутри и снаружи которого находятся вершины графа.
 }}

@@ Строка 29: / Строка 29: @@
 [[File:Fary2.png|250px|Рисунок 2]]
-Так как мы взяли вершины внутри самого глубого разделяющего треугольника, то у вершин <tex>v</tex> и <tex>w</tex> может быть только два общих соседа <tex>p</tex> и <tex>q</tex>, причём <tex>p</tex> и <tex>q</tex> не соединены ребром.
+Так как мы взяли вершины внутри самого глубого разделяющего треугольника, то у вершин <tex>v</tex> и <tex>w</tex> может быть только два общих соседа <tex>p</tex> и <tex>q</tex>.
 Пусть <tex>(vp, vw, vq, vx_1, vx_2 ... vx_k)</tex> и <tex>(wq, wv, wp, wy_1, wy_2 ... wy_m)</tex> {{---}} обход по часовой стрелке ребер, исходящих соостветсвенно из <tex>v</tex> и <tex>w</tex>.
 Пусть <tex>G'</tex> {{---}} граф, полученный из <tex>G</tex> стягиванием ребра <tex>vw</tex> в вершину <tex>s</tex>. Заменим пары параллельных ребер <tex>vq</tex> и <tex>wq</tex> на <tex>sq</tex> и <tex>vp, wp</tex> на <tex>sp</tex>. Получим вершину <tex>s</tex>, из которой исходят ребра <tex>(sp, sy_1, sy_2 ... sy_m, sq, sx_1, sx_2 ... sx_k)</tex> {{---}} по часовой стрелке.

@@ Строка 62: / Строка 62: @@
 }}
-==Смотри также==
+==См. также==
 * [[Теорема Понтрягина-Куратовского]]
 * [[Укладка графа на плоскости]]

@@ Строка 59: / Строка 59: @@
 Получим, что <tex>vw</tex> лежит на <tex>L</tex>. Так как <tex>p</tex> и <tex>q</tex> лежат с разных сторон <tex>L</tex>, ребра, инцидентные <tex>v</tex> и <tex>w</tex>, не пересекаются.
 По выбору <tex>\varepsilon</tex>, ребра, инцидентные <tex>v</tex> и <tex>w</tex>, не пересекают и другие ребра <tex>G</tex>. Таким образом желаемая укладка графа <tex>G</tex> достигнута.
-Теперь мы можем удалить триангуляцию графа, оставив в графе лишь исходные (уже прямые) ребра.
+Теперь мы можем удалить добавленные нами ребра, оставив в графе лишь исходные (уже прямые) ребра.
 }}
 ==Ссылки==

@@ Строка 43: / Строка 43: @@
 [[File:Fary5.png|250px|Рисунок 4]]
-Тогда получим, что все соседи <tex>t</tex> вершины <tex>s</tex> находятся снаружи <tex>C_{\varepsilon}(s)</tex> и только ребра <tex>G'</tex>, пересекающие <tex>R_{\varepsilon}(t)</tex>, являются инцидентными <tex>s</tex>.
+Тогда получим, что все соседи <tex>t</tex> вершины <tex>s</tex> находятся снаружи <tex>C_{\varepsilon}(s)</tex> и только ребра <tex>G'</tex>, инцидентные <tex>s</tex>, могут пересекать <tex>R_{\varepsilon}(t)</tex>.
 [[File:Fary4.png|250px|Рисунок 5]]
-Проведем линию <tex>L</tex> через вершину <tex>s</tex> так, чтобы вершина <tex>p</tex> лежала с одной ее стороны, а <tex>q</tex> {{---}} с другой (иначе <tex>L</tex> наложится на ребра <tex>sp</tex> и <tex>sq</tex>) и никакое из ребер <tex>\{sx_i : 1 < i < k\}</tex> и <tex>\{sy_i : 1 < i < m\}</tex> не лежало на <tex>L</tex>.
+Проведем линию <tex>L</tex> через вершину <tex>s</tex> так, чтобы вершина <tex>p</tex> лежала с одной ее стороны, а <tex>q</tex> {{---}} с другой (такая линия существует, иначе рёбра <tex>sp</tex> и <tex>sq</tex> накладывались бы друг на друга) и никакое из ребер <tex>\{sx_i : 1 < i < k\}</tex> и <tex>\{sy_i : 1 < i < m\}</tex> не лежало на <tex>L</tex>.
 Ребра <tex>sq</tex> и <tex>sq</tex> разбивают <tex>C_{\varepsilon}(s)</tex> на две дуги: первая пересекает ребра <tex>\{sx_i : 1 < i < k\}</tex>, а вторая {{---}} ребра <tex>\{sy_i : 1 < i < m\}</tex>.
 <tex>L</tex> пересекает <tex>C_{\varepsilon}(s)</tex> в двух точках. Расположим <tex>v</tex> и <tex>w</tex> в этих точках: <tex>v</tex> на дуге, пересекающей <tex>\{sx_i : 1 < i < k\}</tex>, а <tex>w</tex> с другой стороны.