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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 20: Строка 20:
 
|statement= Любой планарный граф имеет представление на плоскости, в котором все его ребра будут прямыми.
 
|statement= Любой планарный граф имеет представление на плоскости, в котором все его ребра будут прямыми.
 
|proof=
 
|proof=
[[File:Fary2.png|thumb|250px|Рисунок 2]]
+
 
[[File:Fary3.png|thumb|250px|Рисунок 3]]
 
[[File:Fary5.png|thumb|250px|Рисунок 4]]
 
[[File:Fary4.png|thumb|250px|Рисунок 5]]
 
[[File:Fary6.png|thumb|250px|Рисунок 6]]
 
[[File:Fary7.png|thumb|250px|Рисунок 7]]
 
 
Докажем теорему для плоской триангуляции графа G. Ее можно достичь, добавив в G необходимое количество ребер. Применим индукцию по числу вершин V(G). Предположим, что графы с числом вершин, меньшим V, мы можем нарисовать требуемым образом.  
 
Докажем теорему для плоской триангуляции графа G. Ее можно достичь, добавив в G необходимое количество ребер. Применим индукцию по числу вершин V(G). Предположим, что графы с числом вершин, меньшим V, мы можем нарисовать требуемым образом.  
 
База: V=3 — тривиально
 
База: V=3 — тривиально
 
Переход: V>=4  
 
Переход: V>=4  
 
Рассмотрим ребро vw. Если в G нет разделяющих треугольников, то vw – любое. Иначе vw – ребро, инцидентное вершине, находящейся внутри самого глубокого разделяющего треуголька в G. Тогда vw – граница двух граней vwp & vwq.  
 
Рассмотрим ребро vw. Если в G нет разделяющих треугольников, то vw – любое. Иначе vw – ребро, инцидентное вершине, находящейся внутри самого глубокого разделяющего треуголька в G. Тогда vw – граница двух граней vwp & vwq.  
 +
[[File:Fary2.png|thumb|250px]
 
Если vw не в разделяющем треугольнике p & q – любые общие соседи v и w.  
 
Если vw не в разделяющем треугольнике p & q – любые общие соседи v и w.  
 
Пусть (vp, vw, vq, vx_1, vx_2 … vx_k) & (wq, wv, wp, wy_1, wy_2 … wy_l) – обход по часовой стрелке ребер, исходящих соостветсвенно из v и w.
 
Пусть (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) – по часовой стрелке.  
 
Пусть 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) – по часовой стрелке.  
 +
[[File:Fary3.png|thumb|250px]]
 
Мы получили граф G', с меньшим числом вершин = V - 1  — то есть его можно уложить на плоскости требуемым образом: все ребра прямые (и сохранен обход по часовой стрелке ребер инцидентных s).
 
Мы получили граф G', с меньшим числом вершин = V - 1  — то есть его можно уложить на плоскости требуемым образом: все ребра прямые (и сохранен обход по часовой стрелке ребер инцидентных s).
 
Для любого E>0 обозначим C_E(s) — круг радиуса E, с вершиной s  в центре.  
 
Для любого E>0 обозначим C_E(s) — круг радиуса E, с вершиной s  в центре.  
Строка 38: Строка 35:
  
 
Возьмем E равным минимуму из всех расстояний от вершины s до инцидентных ей вершин и до отрезков, проходящих мимо нее .  
 
Возьмем E равным минимуму из всех расстояний от вершины s до инцидентных ей вершин и до отрезков, проходящих мимо нее .  
 +
[[File:Fary5.png|thumb|250px]]
 
Тогда получим, что все соседи t вершины s находятся снаружи C_E(s) и только ребра G', пересекающие R_E(t), являются инцидентными s.  
 
Тогда получим, что все соседи t вершины s находятся снаружи C_E(s) и только ребра G', пересекающие R_E(t), являются инцидентными s.  
+
[[File:Fary4.png|thumb|250px]]
 
Проведем линию L через вершину s так, чтобы вершина p лежла с одной ее стороны, а q — с другой (иначе L наложится на ребра sp & sq. ), и L никакое из ребер {sx_i : 1<i<k} и {sy_i : 1<i<l} не лежало на ней.  
 
Проведем линию L через вершину s так, чтобы вершина p лежла с одной ее стороны, а q — с другой (иначе L наложится на ребра sp & sq. ), и L никакое из ребер {sx_i : 1<i<k} и {sy_i : 1<i<l} не лежало на ней.  
 
Ребра sq & sq разбивают C_E(s) на две дуги: первая пересекает ребра {sx_i : 1<i<k}, а вторая — ребра {sy_i : 1<i<l}.  
 
Ребра 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 с другой стороны.
 
L пересекает C_E(s) в двух точках. Расположим v & w в этих точках: v на дуге, пересекающей {sx_i : 1<i<k}, а w с другой стороны.
 +
[[File:Fary6.png|thumb|250px]]
 
Удалим s и инцидентные ей ребра, нарисуем прямые ребра G, инцидентные v и w.  
 
Удалим s и инцидентные ей ребра, нарисуем прямые ребра G, инцидентные v и w.  
 +
[[File:Fary7.png|thumb|250px]]
 
Получим, что vw лежит на L. Так как p и q лежат с разных сторон L, ребра, инцидентные v и w, не пересекаются.  
 
Получим, что vw лежит на L. Так как p и q лежат с разных сторон L, ребра, инцидентные v и w, не пересекаются.  
 
По выбору E, ребра, инцидентные v и w, не пересекают и другие ребра G. Таким образом желаемая укладка графа G достигнута.  
 
По выбору E, ребра, инцидентные v и w, не пересекают и другие ребра G. Таким образом желаемая укладка графа G достигнута.  
 
Теперь мы можем удалить триангуляцию графа, оставив в графе лишь исходные (уже прямые) ребра.  
 
Теперь мы можем удалить триангуляцию графа, оставив в графе лишь исходные (уже прямые) ребра.  
 
}}
 
}}

Версия 23:52, 11 ноября 2013

Теорема была независимо доказана Клаусом Вагнером в 1936 года, Иштваном Фари в 1948ом году и Штейном в 1951ом году.


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


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


Разделяющий треугольник изображён ниже.

Рисунок 1


{{Теорема |about=Фари |statement= Любой планарный граф имеет представление на плоскости, в котором все его ребра будут прямыми. |proof=

Докажем теорему для плоской триангуляции графа G. Ее можно достичь, добавив в G необходимое количество ребер. Применим индукцию по числу вершин V(G). Предположим, что графы с числом вершин, меньшим V, мы можем нарисовать требуемым образом. База: V=3 — тривиально Переход: V>=4 Рассмотрим ребро vw. Если в G нет разделяющих треугольников, то vw – любое. Иначе vw – ребро, инцидентное вершине, находящейся внутри самого глубокого разделяющего треуголька в G. Тогда vw – граница двух граней vwp & vwq. [[File:Fary2.png|thumb|250px] Если vw не в разделяющем треугольнике p & q – любые общие соседи v и w. Пусть (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) – по часовой стрелке.

Fary3.png

Мы получили граф G', с меньшим числом вершин = V - 1 — то есть его можно уложить на плоскости требуемым образом: все ребра прямые (и сохранен обход по часовой стрелке ребер инцидентных s). Для любого E>0 обозначим C_E(s) — круг радиуса E, с вершиной s в центре. Для каждого соседа t вершины s в графе G' обозначим R_E(t) область, содержащую множество всех окрытых отрезков от t до каждой точки из C_E(s).

Возьмем E равным минимуму из всех расстояний от вершины s до инцидентных ей вершин и до отрезков, проходящих мимо нее .

Fary5.png

Тогда получим, что все соседи t вершины s находятся снаружи C_E(s) и только ребра G', пересекающие R_E(t), являются инцидентными s.

Fary4.png

Проведем линию L через вершину s так, чтобы вершина p лежла с одной ее стороны, а q — с другой (иначе L наложится на ребра sp & sq. ), и L никакое из ребер {sx_i : 1<i<k} и {sy_i : 1<i<l} не лежало на ней. Ребра 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 с другой стороны.

Fary6.png

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

Fary7.png

Получим, что vw лежит на L. Так как p и q лежат с разных сторон L, ребра, инцидентные v и w, не пересекаются. По выбору E, ребра, инцидентные v и w, не пересекают и другие ребра G. Таким образом желаемая укладка графа G достигнута. Теперь мы можем удалить триангуляцию графа, оставив в графе лишь исходные (уже прямые) ребра. }}