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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ссылки)
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 3 участников)
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|id=def1
 
|id=def1
|definition='''Триангуляция графа''' {{---}} представление планарного графа на плоскости в таком виде, что каждая его грань ограничена тремя ребрами (является треугольником).
+
|definition='''Триангуляция графа''' (англ. ''triangulation'') {{---}} представление [[Укладка графа на плоскости#defplanar | планарного графа]] на плоскости в таком виде, что каждая его грань ограничена тремя ребрами (является треугольником).
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|id=def2
 
|id=def2
|definition='''Разделяющий треугольник''' {{---}} цикл длины <tex>3</tex> в графе <tex>G</tex>, внутри и снаружи которого находятся вершины графа.
+
|definition='''Разделяющий треугольник''' (англ. ''separating triangle'') {{---}} цикл длины <tex>3</tex> в графе <tex>G</tex>, внутри и снаружи которого находятся вершины графа.
 
}}
 
}}
  
Строка 21: Строка 21:
 
|proof=
 
|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]]
 
[[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>(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> {{---}} по часовой стрелке.
 
Пусть <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> {{---}} по часовой стрелке.
Строка 35: Строка 35:
 
[[File:Fary3.png|250px|Рисунок 3]]
 
[[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>\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>.  
+
Для каждого соседа <tex>t</tex> вершины <tex>s</tex> в графе <tex>G'</tex> обозначим <tex>R_{\varepsilon}(t)</tex> объединение всех отрезков, проведённых из <tex>t</tex> в <tex>C_{\varepsilon}(s)</tex>.  
  
 
Возьмем <tex>\varepsilon</tex> равным минимуму из всех расстояний от вершины <tex>s</tex> до инцидентных ей вершин и до отрезков, проходящих мимо нее.
 
Возьмем <tex>\varepsilon</tex> равным минимуму из всех расстояний от вершины <tex>s</tex> до инцидентных ей вершин и до отрезков, проходящих мимо нее.
Строка 43: Строка 43:
 
[[File:Fary5.png|250px|Рисунок 4]]
 
[[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]]
 
[[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>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> с другой стороны.
 
<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> с другой стороны.
Строка 59: Строка 59:
 
Получим, что <tex>vw</tex> лежит на <tex>L</tex>. Так как <tex>p</tex> и <tex>q</tex> лежат с разных сторон <tex>L</tex>, ребра, инцидентные <tex>v</tex> и <tex>w</tex>, не пересекаются.  
 
Получим, что <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> достигнута.  
 
По выбору <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 ]]
 
* [[wikipedia:Fáry's_theorem | Wikipedia {{---}} Fáry's theorem ]]
 
* [http://arxiv.org/abs/cs/0505047 Доказательство теоремы Фари]
 
* [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]

См. также

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