Теорема Фари — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 50 промежуточных версий 3 участников)
Строка 1: Строка 1:
Теорема была независимо доказана Клаусом Вагнером в 1936 года, Иштваном Фари в 1948ом году и Штейном в 1951ом году.
+
Теорема была независимо доказана Клаусом Вагнером (Klaus Wagner) в 1936ом году и Иштваном Фари (István Fáry) в 1948ом году. Иногда ее называют теоремой Фари-Вагнера.
  
==Определения==
 
 
{{Определение
 
{{Определение
 
|id=def1
 
|id=def1
|definition=Триангуляция графа представление графа на плоскости в таком виде, что каждая его грань ограничена тремя ребрами (является треугольником).
+
|definition='''Триангуляция графа''' (англ. ''triangulation'') {{---}} представление [[Укладка графа на плоскости#defplanar | планарного графа]] на плоскости в таком виде, что каждая его грань ограничена тремя ребрами (является треугольником).
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|id=def1
+
|id=def2
|definition=Разделяющий треугольник цикл длины 3 в графе G, внутри и снаружи которого находятся вершины графа.
+
|definition='''Разделяющий треугольник''' (англ. ''separating triangle'') {{---}} цикл длины <tex>3</tex> в графе <tex>G</tex>, внутри и снаружи которого находятся вершины графа.
 
}}
 
}}
  
Разделяющий треугольник представлен на рисунке 1.
+
Разделяющий треугольник изображён ниже. Относительно него существует три вида вершин: внешние, внутренние и лежащие на самом треугольнике.
  
 +
[[File:Fary1.png|250px|Рисунок 1]]
  
==Теорема==
 
  
 
{{Теорема
 
{{Теорема
 
|about=Фари
 
|about=Фари
|statement= Любой планарный граф имеет представление на плоскости, в котором все его ребра будут прямыми.
+
|statement=Любой планарный граф имеет плоское представление, в котором все ребра представлены в виде отрезков прямых.
 
|proof=
 
|proof=
Докажем теорему для плоской триангуляции графа G. Ее можно достичь, добавив в G необходимое количество ребер. Применим индукцию по числу вершин V(G). Предположим, что графы с числом вершин, меньшим V, мы можем нарисовать требуемым образом.
 
База: V=3 — тривиально
 
Переход: V>=4
 
  
Рассмотрим ребро vw. Если в G нет разделяющих треугольников, то vw – любое. Иначе vw – ребро, инцидентное вершине, находящейся внутри самого глубокого разделяющего треуголька в G. Тогда vw граница двух граней vwp & vwq. Картинка 2. Если vw не в разделяющем треугольнике p & q – любые общие соседи v и w.  
+
Докажем теорему для плоской триангуляции графа <tex>G</tex>. Ее можно достичь, добавив в <tex>G</tex> необходимое количество ребер. Применим индукцию по числу вершин <tex>|V|</tex>.
Пусть (vp, vw, vq, vx_1, vx_2 vx_k) & (wq, wv, wp, wy_1, wy_2 … wy_l) обход по часовой стрелке ребер, исходящих соостветсвенно из v и w.
+
 
Пусть G' – планарная триангуляция, полученная из G стягиванием ребра vw в вершину s. Заменим пары параллельных ребер vq & wq на sq и vp & wp на sp. Получим вершину s, из которой исходят ребра (sp, sy_1, sy_2 … sy_l, sq, sx_1, sx_2 sx_k) по часовой стрелке. Картинка 3.
+
База индукции, когда <tex>|V|=3</tex>, выполняется тривиальным образом.
Мы получили граф G', с меньшим числом вершин = V - 1 то есть его можно уложить на плоскости требуемым образом: все ребра прямые (и сохранен обход по часовой стрелке ребер инцидентных s).
+
Предположим, что графы с любым числом вершин меньше <tex>|V| \geqslant 4</tex>, мы можем нарисовать требуемым образом.
Для любого E>0 обозначим C_E(s) круг радиуса E, с вершиной s  в центре.  
+
Рассмотрим ребро <tex>vw</tex>, [[Матрица инцидентности графа#definc | инцидентное]] внутренней вершине глубочайшего разделяющего треугольника, то есть такого, который не содержит внутри себя других разделяющих треугольников. Если в графе нет разделяющих треугольников, то возьмём любое ребро. Тогда <tex>vw</tex> {{---}} граница двух граней <tex>vwp</tex> и <tex>vwq</tex>.  
Для каждого соседа t вершины s в графе G' обозначим R_E(t) область, содержащую множество всех окрытых отрезков от t до каждой точки из C_E(s).  
+
 
 +
[[File:Fary2.png|250px|Рисунок 2]]
 +
 
 +
Так как мы взяли вершины внутри самого глубого разделяющего треугольника, то у вершин <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> {{---}} по часовой стрелке.
 +
 +
[[File:Fary3.png|250px|Рисунок 3]]
 +
 
 +
Мы получили граф <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>.  
  
Возьмем E равным минимуму из всех расстояний от вершины s до инцидентных ей вершин и до отрезков, проходящих мимо нее . Картинка 4.2
+
Возьмем <tex>\varepsilon</tex> равным минимуму из всех расстояний от вершины <tex>s</tex> до инцидентных ей вершин и до отрезков, проходящих мимо нее.
Тогда получим, что все соседи t вершины s находятся снаружи C_E(s) и только ребра G', пересекающие R_E(t), являются инцидентными s. Картинка 4.1
 
 
   
 
   
Проведем линию L через вершину s так, чтобы вершина p лежла с одной ее стороны, а q с другой (иначе L наложится на ребра sp & sq. ), и L никакое из ребер {sx_i : 1<i<k} и {sy_i : 1<i<l} не лежало на ней.  
+
[[File:Fary5.png|250px|Рисунок 4]]
Ребра sq & sq разбивают C_E(s) на две дуги: первая пересекает ребра {sx_i : 1<i<k}, а вторая ребра {sy_i : 1<i<l}.  
+
 
L пересекает C_E(s) в двух точках. Расположим v & w в этих точках: v на дуге, пересекающей {sx_i : 1<i<k}, а w с другой стороны. Картинка 5.
+
Тогда получим, что все соседи <tex>t</tex> вершины <tex>s</tex> находятся снаружи <tex>C_{\varepsilon}(s)</tex> и только ребра <tex>G'</tex>, инцидентные <tex>s</tex>, могут пересекать <tex>R_{\varepsilon}(t)</tex>.
Удалим s и инцидентные ей ребра, нарисуем прямые ребра G, инцидентные v и w. Картинка 6.
+
 
Получим, что vw лежит на L. Так как p и q лежат с разных сторон L, ребра, инцидентные v и w, не пересекаются.  
+
[[File:Fary4.png|250px|Рисунок 5]]
По выбору E, ребра, инцидентные v и w, не пересекают и другие ребра G. Таким образом желаемая укладка графа G достигнута.  
+
 
Теперь мы можем удалить триангуляцию графа, оставив в графе лишь исходные (уже прямые) ребра.  
+
Проведем линию <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> с другой стороны.
 +
 
 +
[[File:Fary6.png|250px|Рисунок 6]]
 +
 
 +
Удалим <tex>s</tex> и инцидентные ей ребра, нарисуем прямые ребра <tex>G</tex>, инцидентные <tex>v</tex> и <tex>w</tex>.  
 +
 
 +
[[File:Fary7.png|250px|Рисунок 7]]
 +
 
 +
Получим, что <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> достигнута.  
 +
Теперь мы можем удалить добавленные нами ребра, оставив в графе лишь исходные (уже прямые) ребра.  
 
}}
 
}}
 +
 +
==См. также==
 +
* [[Теорема Понтрягина-Куратовского]]
 +
* [[Укладка графа на плоскости]]
 +
 +
==Источники информации==
 +
* [[wikipedia:Fáry's_theorem | Wikipedia {{---}} Fáry's theorem ]]
 +
* [http://arxiv.org/abs/cs/0505047 Доказательство теоремы Фари]
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Укладки графов ]]

Текущая версия на 19:11, 4 сентября 2022

Теорема была независимо доказана Клаусом Вагнером (Klaus Wagner) в 1936ом году и Иштваном Фари (István Fáry) в 1948ом году. Иногда ее называют теоремой Фари-Вагнера.


Определение:
Триангуляция графа (англ. triangulation) — представление планарного графа на плоскости в таком виде, что каждая его грань ограничена тремя ребрами (является треугольником).


Определение:
Разделяющий треугольник (англ. separating triangle) — цикл длины [math]3[/math] в графе [math]G[/math], внутри и снаружи которого находятся вершины графа.


Разделяющий треугольник изображён ниже. Относительно него существует три вида вершин: внешние, внутренние и лежащие на самом треугольнике.

Рисунок 1


Теорема (Фари):
Любой планарный граф имеет плоское представление, в котором все ребра представлены в виде отрезков прямых.
Доказательство:
[math]\triangleright[/math]

Докажем теорему для плоской триангуляции графа [math]G[/math]. Ее можно достичь, добавив в [math]G[/math] необходимое количество ребер. Применим индукцию по числу вершин [math]|V|[/math].

База индукции, когда [math]|V|=3[/math], выполняется тривиальным образом. Предположим, что графы с любым числом вершин меньше [math]|V| \geqslant 4[/math], мы можем нарисовать требуемым образом. Рассмотрим ребро [math]vw[/math], инцидентное внутренней вершине глубочайшего разделяющего треугольника, то есть такого, который не содержит внутри себя других разделяющих треугольников. Если в графе нет разделяющих треугольников, то возьмём любое ребро. Тогда [math]vw[/math] — граница двух граней [math]vwp[/math] и [math]vwq[/math].

Рисунок 2

Так как мы взяли вершины внутри самого глубого разделяющего треугольника, то у вершин [math]v[/math] и [math]w[/math] может быть только два общих соседа [math]p[/math] и [math]q[/math]. Пусть [math](vp, vw, vq, vx_1, vx_2 ... vx_k)[/math] и [math](wq, wv, wp, wy_1, wy_2 ... wy_m)[/math] — обход по часовой стрелке ребер, исходящих соостветсвенно из [math]v[/math] и [math]w[/math]. Пусть [math]G'[/math] — граф, полученный из [math]G[/math] стягиванием ребра [math]vw[/math] в вершину [math]s[/math]. Заменим пары параллельных ребер [math]vq[/math] и [math]wq[/math] на [math]sq[/math] и [math]vp, wp[/math] на [math]sp[/math]. Получим вершину [math]s[/math], из которой исходят ребра [math](sp, sy_1, sy_2 ... sy_m, sq, sx_1, sx_2 ... sx_k)[/math] — по часовой стрелке.

Рисунок 3

Мы получили граф [math]G'[/math], с меньшим числом вершин равным [math]V - 1[/math], то есть его можно уложить на плоскости требуемым образом: все ребра прямые (и сохранен обход по часовой стрелке ребер, инцидентных [math]s[/math]). Для любого [math]\varepsilon \gt 0[/math] обозначим [math]C_{\varepsilon}(s)[/math] — круг радиуса [math]\varepsilon[/math], с вершиной [math]s[/math] в центре. Для каждого соседа [math]t[/math] вершины [math]s[/math] в графе [math]G'[/math] обозначим [math]R_{\varepsilon}(t)[/math] объединение всех отрезков, проведённых из [math]t[/math] в [math]C_{\varepsilon}(s)[/math].

Возьмем [math]\varepsilon[/math] равным минимуму из всех расстояний от вершины [math]s[/math] до инцидентных ей вершин и до отрезков, проходящих мимо нее.

Рисунок 4

Тогда получим, что все соседи [math]t[/math] вершины [math]s[/math] находятся снаружи [math]C_{\varepsilon}(s)[/math] и только ребра [math]G'[/math], инцидентные [math]s[/math], могут пересекать [math]R_{\varepsilon}(t)[/math].

Рисунок 5

Проведем линию [math]L[/math] через вершину [math]s[/math] так, чтобы вершина [math]p[/math] лежала с одной ее стороны, а [math]q[/math] — с другой (такая линия существует, иначе рёбра [math]sp[/math] и [math]sq[/math] накладывались бы друг на друга) и никакое из ребер [math]\{sx_i : 1 \lt i \lt k\}[/math] и [math]\{sy_i : 1 \lt i \lt m\}[/math] не лежало на [math]L[/math]. Ребра [math]sq[/math] и [math]sq[/math] разбивают [math]C_{\varepsilon}(s)[/math] на две дуги: первая пересекает ребра [math]\{sx_i : 1 \lt i \lt k\}[/math], а вторая — ребра [math]\{sy_i : 1 \lt i \lt m\}[/math]. [math]L[/math] пересекает [math]C_{\varepsilon}(s)[/math] в двух точках. Расположим [math]v[/math] и [math]w[/math] в этих точках: [math]v[/math] на дуге, пересекающей [math]\{sx_i : 1 \lt i \lt k\}[/math], а [math]w[/math] с другой стороны.

Рисунок 6

Удалим [math]s[/math] и инцидентные ей ребра, нарисуем прямые ребра [math]G[/math], инцидентные [math]v[/math] и [math]w[/math].

Рисунок 7

Получим, что [math]vw[/math] лежит на [math]L[/math]. Так как [math]p[/math] и [math]q[/math] лежат с разных сторон [math]L[/math], ребра, инцидентные [math]v[/math] и [math]w[/math], не пересекаются. По выбору [math]\varepsilon[/math], ребра, инцидентные [math]v[/math] и [math]w[/math], не пересекают и другие ребра [math]G[/math]. Таким образом желаемая укладка графа [math]G[/math] достигнута.

Теперь мы можем удалить добавленные нами ребра, оставив в графе лишь исходные (уже прямые) ребра.
[math]\triangleleft[/math]

См. также

Источники информации