Теорема Фари о распрямлении графа: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
← Новая страница: «'''Теоре́ма Фа́ри''' — теорема теории графов.<ref>{{citation | last = Fáry | ...» |
мНет описания правки |
||
(не показано 35 промежуточных версий 24 участников) | |||
Строка 1: | Строка 1: | ||
{{Не путать|Теорема Фарри|теоремой Фарри|утверждением, относящимся к квантовой электродинамике}} |
|||
'''Теоре́ма Фа́ри''' — [[теорема]] [[теория графов|теории графов]].<ref>{{citation |
|||
'''Теорема Фа́ри''' — [[Теория графов|теоретико-графовое]] утверждение о возможности выпрямить рёбра любого [[планарный граф|планарного графа]]. Иными словами, разрешение рисовать рёбра не в виде отрезков, а в виде кривых, не расширяет класс планарных графов. |
|||
| last = Fáry | first = István | authorlink = István Fáry |
|||
| title = On straight-line representation of planar graphs |
|||
| journal = Acta Sci. Math. (Szeged) |
|||
| volume = 11 |
|||
| year = 1948 |
|||
| pages = 229–233 |
|||
| id = {{MathSciNet | id = 0026311}}}}</ref> |
|||
{{рамка}} |
|||
Любой [[планарный граф]] имеет плоское представление, в котором все ребра представлены в виде отрезков прямых. |
|||
Названа в честь венгерского математика [[Фари, Иштван|Иштвана Фа́ри]]{{sfn|Fáry|1948|с=229–233}}, хотя была доказана независимо Клаусом Вагнером в 1936{{sfn|Wagner|1936}} и Штайном в 1951{{sfn|Stein|1951}}. |
|||
{{/рамка}} |
|||
Таким образом, возможность рисовать ребра графов в виде кривых не дает возможности изобразить на плоскости большее множество графов. |
|||
Формулировка: любой [[Граф (математика)#Обобщение понятия графа|простой]] [[планарный граф]] имеет плоское представление, в котором все рёбра представлены в виде [[Отрезок|отрезков]] прямых. |
|||
== Ссылки == |
|||
<references/> |
|||
== Доказательство == |
|||
[[en:Fáry's theorem]] |
|||
[[Файл:Fary-induction.svg|thumb|right|Шаг индукции.]] |
|||
Один из путей доказательства теоремы Фари — применение [[Математическая индукция|математической индукции]]<ref>Приведённое доказательство можно найти в книге В. В. Прасолов. Элементы комбинаторной и дифференциальной топологии. М.: МЦНМО, 2004.<!-- Есть некоторая вероятность, что Чартранд и Лесняк {{harv|Chartrand, Lesniak, Zhang|2010|loc=259–260}} взяли доказательство с (английской версии) этой статьи, поскольку их публикация появилась позже появления статьи в WikipediA. --></ref>. Пусть <math>G</math> — простой [[планарный граф]] с <math>n</math> вершинами. Мы можем считать граф максимальным планарным, при необходимости можем добавить рёбра в исходный граф <math>G</math>. Все грани графа <math>G</math> в этом случае должны быть треугольниками, так как мы можем добавить ребро в любую грань с бо́льшим числом сторон, не нарушая планарности графа, что противоречит соглашению о максимальности графа. Выберем некоторые три вершины <math>a, b, c</math>, образующие треугольную грань графа <math>G</math>. Мы докажем по индукции по <math>n</math>, что существует комбинаторно изоморфное другое вложение с прямыми рёбрами графа <math>G</math>, в котором треугольник <math>abc</math> является внешней гранью вложения. (''Комбинаторная изоморфность'' означает, что вершины, рёбра и грани нового рисунка могут быть сделаны соответствующими элементам старого рисунка и при этом сохраняются все отношения инцидентности между рёбрами, вершинами и гранями, не только между вершинами и рёбрами.) База индукции тривиальна, когда <math>a, b, c</math> являются единственными вершинами в <math>G</math> (<math>n=3</math>). |
|||
По [[Планарный граф|формуле Эйлера]] для планарных графов граф <math>G</math> имеет <math>3n-6</math> рёбер. Эквивалентно, если определить ''дефицит'' вершины <math>v</math> в графе <math>G</math> как <math>6-\deg(v)</math>, сумма дефицитов равна {{math|12}}. Каждая вершина в графе <math>G</math> может иметь дефицит не выше трёх, так что имеется по меньшей мере четыре вершины с положительным дефицитом. В частности, мы можем выбрать вершину <math>v</math> с не более чем пятью соседями, которая отлична от <math>a, b |
|||
</math> и <math>c</math>. Пусть <math>G'</math> образуется путём удаления вершины <math>v</math> из графа <math>G</math> и триангуляции грани <math>f</math>, полученной после удаления вершины <math>v</math>. По индукции, граф <math>G'</math> имеет комбинаторно изоморфное вложение с прямолинейными рёбрами, в котором <math>abc</math> является внешней гранью. Поскольку полученное вложение <math>G</math> было комбинаторно изоморфно <math>G'</math>, удаление из него рёбер, которые были добавлены для получения графа <math>G'</math> оставляет грань <math>f</math>, которая теперь представляет собой многоугольник <math>P</math> с не более чем пятью сторонами. Для получения рисунка <math>G</math> с комбинаторно изоморфным вложением с прямыми рёбрами, вершина <math>v</math> должна быть добавлена в многоугольник и соединена отрезками с вершинами многоугольника. По [[Задача о картинной галерее# Теорема Шватала о картинной галерее|теореме о картинной галерее]] существует точка внутри <math>P</math>, куда можно поместить вершину <math>v</math>, так что рёбра, соединяющие вершину <math>v</math> с вершинами многоугольника <math>P</math>, не пересекут другие рёбра многоугольника, что завершает доказательство. |
|||
Шаг индукции доказательства проиллюстрирован справа. |
|||
== Связанные результаты == |
|||
Де Фрейсикс, Пах и Полак показали, как найти за линейное время рисунок с прямолинейными рёбрами на решётке с размерами, линейно зависящими от размера графа, давая [[универсальное множество точек]] с квадратичными размерами. Похожий метод использовал Шнайдер для доказательства улучшенных границ и [[Теорема Шнайдера|характеристики планарности]], где он основывался на частичном порядке инцидентности. Его работа делает упор на существование определённого разбиения рёбер максимального планарного графа на три дерева, которые известны как [[Древесность графа#Древесность как мера плотности|лес Шнайдера]]. |
|||
[[Вложение Татта|Теорема Татта «о резиновой укладке»]] утверждает, что любой трёхсвязный планарный граф можно нарисовать на плоскости без пересечений так, что его рёбра являются отрезками прямых и внешняя грань является выпуклым многоугольником{{sfn|Tutte|1963|с=743–767}}. Название отражает факт, что такое вложение может быть найдено как точка равновесия системы [[Пружина|пружин]], представляющих рёбра графа. |
|||
[[Теорема Штайница]] утверждает, что любой 3-связный планарный граф может быть представлен как рёбра выпуклого многогранника в трёхмерном пространстве. Вложение с прямыми рёбрами графа <math>G</math> может быть получено как проекция такого многогранника на плоскость. |
|||
[[Теорема об упаковке кругов]] утверждает, что любой планарный граф может быть представлен как [[граф пересечений]] набора непересекающихся окружностей на плоскости. Если разместить каждую вершину графа в центре соответствующей окружности, получим представление графа с прямолинейными рёбрами. |
|||
{{unsolved|математики|Существует ли для любого планарного графа представление с прямыми рёбрами, в котором длины всех рёбер являются целыми числами?}} |
|||
{{не переведено 5|Харборт, Хайко|Хайуо Харборт||Heiko Harborth}} поднял вопрос, существует ли для любого планарного графа представление с прямыми рёбрами, в котором все длины рёбер являются целыми числами<ref>{{harvnb|Harborth, Kemnitz, Moller, Sussenbach|1987}}; {{harvnb|Kemnitz, Harborth|2001}}; {{harvnb|Mohar, Thomassen|2001}}.</ref>. Верна ли [[гипотеза Харборта]], остаётся открытым вопросом ({{As of|2014|lc=on}}). Однако известно, что вложение с целочисленными прямыми рёбрами существует для [[Кубический граф|кубических графов]]{{sfn|Geelen, Guo, McKinnon|2008}}. |
|||
Сакс{{sfn|Sachs|1983}} поднял вопрос, имеет ли любой граф с [[Незацепленное вложение графа|незацепленным вложением]] в трёхмерном [[Евклидово пространство|евклидовом пространстве]] незацепленное вложение, в котором все рёбра представлены отрезками по аналогии с теоремой Фари для двухмерных вложений. |
|||
== См. также == |
|||
* [[Минимизация изломов]] |
|||
== Примечания == |
|||
{{примечания|2}} |
|||
== Литература == |
|||
* {{статья |
|||
|ref=Fáry |
|||
|автор=István Fáry |
|||
|заглавие=On straight-line representation of planar graphs |
|||
|издание=Acta Sci. Math. (Szeged) |
|||
|том=11 |
|||
|год=1948 |
|||
|страницы=229–233 |
|||
|id={{MathSciNet|id=0026311}} |
|||
}} |
|||
* {{книга |
|||
|заглавие=Graphs & Digraphs |
|||
|автор=Gary Chartrand, Linda Lesniak, Ping Zhang |
|||
|ref=Chartrand, Lesniak, Zhang |
|||
|издание=5th |
|||
|издательство=CRC Press |
|||
|год=2010 |
|||
|isbn=9781439826270 |
|||
|страницы=259–260 |
|||
|ссылка=https://books.google.com/books?id=K6-FvXRlKsQC&pg=PA259 |
|||
}} |
|||
* {{книга |
|||
|автор=Hubert de Fraysseix, János Pach, Richard Pollack |
|||
|ref=de Fraysseix, Pach, Pollack |
|||
|часть=Small sets supporting Fary embeddings of planar graphs |
|||
|заглавие=Twentieth Annual ACM Symposium on Theory of Computing |
|||
|ссылка=https://archive.org/details/proceedingsoftwe0000acms_z7q8 |
|||
|год=1988 |
|||
|страницы=[https://archive.org/details/proceedingsoftwe0000acms_z7q8/page/426 426]–433 |
|||
|doi=10.1145/62212.62254 |
|||
|isbn=0-89791-264-0 |
|||
}} |
|||
* {{статья |
|||
|автор=Hubert de Fraysseix, János Pach, Richard Pollack |
|||
|ref=de Fraysseix, Pach, Pollack |
|||
|заглавие=How to draw a planar graph on a grid |
|||
|ссылка=https://archive.org/details/sim_combinatorica_1990_10_1/page/41 |
|||
|издание=Combinatorica |
|||
|год=1990 |
|||
|том=10 |
|||
|страницы=41–51 |
|||
|mr=1075065 |
|||
|doi=10.1007/BF02122694 |
|||
}} |
|||
* {{статья |
|||
|автор=Jim Geelen, Anjie Guo, David McKinnon |
|||
|ref=Geelen, Guo, McKinnon |
|||
|doi=10.1002/jgt.20304 |
|||
|выпуск=3 |
|||
|издание=J. Graph Theory |
|||
|страницы=270–274 |
|||
|заглавие=Straight line embeddings of cubic planar graphs with integer edge lengths |
|||
|ссылка=http://www.math.uwaterloo.ca/~dmckinnon/Papers/Planar.pdf |
|||
|том=58 |
|||
|год=2008 |
|||
}} |
|||
* {{статья |
|||
|автор=Harborth H., Kemnitz A., Moller M., Sussenbach A. |
|||
|ref=Harborth, Kemnitz, Moller, Sussenbach |
|||
|издание=Elem. Math. |
|||
|страницы=118–122 |
|||
|заглавие=Ganzzahlige planare Darstellungen der platonischen Korper |
|||
|том=42 |
|||
|год=1987 |
|||
}} |
|||
* {{статья |
|||
|ref=Kemnitz, Harborth |
|||
|автор=Kemnitz A., Harborth H. |
|||
|doi=10.1016/S0012-365X(00)00442-8 |
|||
|издание=Discrete Math. |
|||
|страницы=191–195 |
|||
|заглавие=Plane integral drawings of planar graphs |
|||
|том=236 |
|||
|год=2001 |
|||
}} |
|||
* {{книга |
|||
|автор=Bojan Mohar, Carsten Thomassen |
|||
|ref=Mohar, Thomassen |
|||
|год=2001 |
|||
|заглавие=Graphs on Surfaces |
|||
|издательство=Johns Hopkins University Press |
|||
|страницы=roblem 2.8.15 |
|||
|isbn=0-8018-6689-8 |
|||
}} |
|||
* {{книга |
|||
|ref=Sachs |
|||
|автор=Horst Sachs |
|||
|doi=10.1007/BFb0071633 |
|||
|editor1-last=Horowiecki|editor1-first=M. |
|||
|editor2-last=Kennedy|editor2-first=J. W. |
|||
|editor3-last=Sysło|editor3-first=M. M. |
|||
|страницы=230–241 |
|||
|издательство=Springer-Verlag |
|||
|series=Lecture Notes in Mathematics |
|||
|заглавие=Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981 |
|||
|том=1018 |
|||
|год=1983 |
|||
|chapter=On a spatial analogue of Kuratowski's theorem on planar graphs — An open problem |
|||
|isbn=978-3-540-12687-4 |
|||
}} |
|||
* {{статья |
|||
|ref=Schnyder |
|||
|автор=Walter Schnyder |
|||
|chapter=Embedding planar graphs on the grid |
|||
|ссылка=http://portal.acm.org/citation.cfm?id=320176.320191 |
|||
|заглавие=Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA) |
|||
|год=1990 |
|||
|страницы=138–148 |
|||
}} |
|||
* {{статья |
|||
|автор=Stein S. K. |
|||
|ref=Stein |
|||
|заглавие=Convex maps |
|||
|издание=[[Proceedings of the American Mathematical Society]] |
|||
|том=2 |
|||
|год=1951 |
|||
|страницы=464–466 |
|||
|mr=0041425 |
|||
|doi=10.2307/2031777 |
|||
|выпуск=3 |
|||
|jstor=2031777 |
|||
}} |
|||
* {{статья |
|||
|ref=Tutte |
|||
|автор=[[Татт, Уильям Томас|Tutte W. T.]] |
|||
|заглавие=How to draw a graph |
|||
|издание=Proceedings of the London Mathematical Society |
|||
|том=13 |
|||
|год=1963 |
|||
|страницы=743–767 |
|||
|mr=0158387 |
|||
|doi=10.1112/plms/s3-13.1.743 |
|||
}} |
|||
* {{статья |
|||
|ref=Wagner |
|||
|автор=Klaus Wagner |
|||
|заглавие=Bemerkungen zum Vierfarbenproblem |
|||
|издание=Jahresbericht der Deutschen Mathematiker-Vereinigung |
|||
|том=46 |
|||
|год=1936 |
|||
|страницы=26–32 |
|||
|ссылка=http://www.digizeitschriften.de/index.php?id=resolveppn&PPN=GDZPPN002131633}}. |
|||
[[Категория:Планарные графы]] |
|||
[[Категория:Теоремы теории графов]] |
|||
{{rq|checktranslate|style}} |
Текущая версия от 13:40, 16 октября 2023
Теорема Фа́ри — теоретико-графовое утверждение о возможности выпрямить рёбра любого планарного графа. Иными словами, разрешение рисовать рёбра не в виде отрезков, а в виде кривых, не расширяет класс планарных графов.
Названа в честь венгерского математика Иштвана Фа́ри[1], хотя была доказана независимо Клаусом Вагнером в 1936[2] и Штайном в 1951[3].
Формулировка: любой простой планарный граф имеет плоское представление, в котором все рёбра представлены в виде отрезков прямых.
Доказательство
[править | править код]Один из путей доказательства теоремы Фари — применение математической индукции[4]. Пусть — простой планарный граф с вершинами. Мы можем считать граф максимальным планарным, при необходимости можем добавить рёбра в исходный граф . Все грани графа в этом случае должны быть треугольниками, так как мы можем добавить ребро в любую грань с бо́льшим числом сторон, не нарушая планарности графа, что противоречит соглашению о максимальности графа. Выберем некоторые три вершины , образующие треугольную грань графа . Мы докажем по индукции по , что существует комбинаторно изоморфное другое вложение с прямыми рёбрами графа , в котором треугольник является внешней гранью вложения. (Комбинаторная изоморфность означает, что вершины, рёбра и грани нового рисунка могут быть сделаны соответствующими элементам старого рисунка и при этом сохраняются все отношения инцидентности между рёбрами, вершинами и гранями, не только между вершинами и рёбрами.) База индукции тривиальна, когда являются единственными вершинами в ().
По формуле Эйлера для планарных графов граф имеет рёбер. Эквивалентно, если определить дефицит вершины в графе как , сумма дефицитов равна 12. Каждая вершина в графе может иметь дефицит не выше трёх, так что имеется по меньшей мере четыре вершины с положительным дефицитом. В частности, мы можем выбрать вершину с не более чем пятью соседями, которая отлична от и . Пусть образуется путём удаления вершины из графа и триангуляции грани , полученной после удаления вершины . По индукции, граф имеет комбинаторно изоморфное вложение с прямолинейными рёбрами, в котором является внешней гранью. Поскольку полученное вложение было комбинаторно изоморфно , удаление из него рёбер, которые были добавлены для получения графа оставляет грань , которая теперь представляет собой многоугольник с не более чем пятью сторонами. Для получения рисунка с комбинаторно изоморфным вложением с прямыми рёбрами, вершина должна быть добавлена в многоугольник и соединена отрезками с вершинами многоугольника. По теореме о картинной галерее существует точка внутри , куда можно поместить вершину , так что рёбра, соединяющие вершину с вершинами многоугольника , не пересекут другие рёбра многоугольника, что завершает доказательство.
Шаг индукции доказательства проиллюстрирован справа.
Связанные результаты
[править | править код]Де Фрейсикс, Пах и Полак показали, как найти за линейное время рисунок с прямолинейными рёбрами на решётке с размерами, линейно зависящими от размера графа, давая универсальное множество точек с квадратичными размерами. Похожий метод использовал Шнайдер для доказательства улучшенных границ и характеристики планарности, где он основывался на частичном порядке инцидентности. Его работа делает упор на существование определённого разбиения рёбер максимального планарного графа на три дерева, которые известны как лес Шнайдера.
Теорема Татта «о резиновой укладке» утверждает, что любой трёхсвязный планарный граф можно нарисовать на плоскости без пересечений так, что его рёбра являются отрезками прямых и внешняя грань является выпуклым многоугольником[5]. Название отражает факт, что такое вложение может быть найдено как точка равновесия системы пружин, представляющих рёбра графа.
Теорема Штайница утверждает, что любой 3-связный планарный граф может быть представлен как рёбра выпуклого многогранника в трёхмерном пространстве. Вложение с прямыми рёбрами графа может быть получено как проекция такого многогранника на плоскость.
Теорема об упаковке кругов утверждает, что любой планарный граф может быть представлен как граф пересечений набора непересекающихся окружностей на плоскости. Если разместить каждую вершину графа в центре соответствующей окружности, получим представление графа с прямолинейными рёбрами.
Хайуо Харборт[англ.] поднял вопрос, существует ли для любого планарного графа представление с прямыми рёбрами, в котором все длины рёбер являются целыми числами[6]. Верна ли гипотеза Харборта, остаётся открытым вопросом (на 2014 год). Однако известно, что вложение с целочисленными прямыми рёбрами существует для кубических графов[7].
Сакс[8] поднял вопрос, имеет ли любой граф с незацепленным вложением в трёхмерном евклидовом пространстве незацепленное вложение, в котором все рёбра представлены отрезками по аналогии с теоремой Фари для двухмерных вложений.
См. также
[править | править код]Примечания
[править | править код]- ↑ Fáry, 1948, с. 229–233.
- ↑ Wagner, 1936.
- ↑ Stein, 1951.
- ↑ Приведённое доказательство можно найти в книге В. В. Прасолов. Элементы комбинаторной и дифференциальной топологии. М.: МЦНМО, 2004.
- ↑ Tutte, 1963, с. 743–767.
- ↑ Harborth, Kemnitz, Moller, Sussenbach, 1987; Kemnitz, Harborth, 2001; Mohar, Thomassen, 2001.
- ↑ Geelen, Guo, McKinnon, 2008.
- ↑ Sachs, 1983.
Литература
[править | править код]- István Fáry. On straight-line representation of planar graphs // Acta Sci. Math. (Szeged). — 1948. — Т. 11. — С. 229–233.
- Gary Chartrand, Linda Lesniak, Ping Zhang. Graphs & Digraphs. — 5th. — CRC Press, 2010. — С. 259–260. — ISBN 9781439826270.
- Hubert de Fraysseix, János Pach, Richard Pollack. Small sets supporting Fary embeddings of planar graphs // Twentieth Annual ACM Symposium on Theory of Computing. — 1988. — С. 426–433. — ISBN 0-89791-264-0. — doi:10.1145/62212.62254.
- Hubert de Fraysseix, János Pach, Richard Pollack. How to draw a planar graph on a grid // Combinatorica. — 1990. — Т. 10. — С. 41–51. — doi:10.1007/BF02122694.
- Jim Geelen, Anjie Guo, David McKinnon. Straight line embeddings of cubic planar graphs with integer edge lengths // J. Graph Theory. — 2008. — Т. 58, вып. 3. — С. 270–274. — doi:10.1002/jgt.20304.
- Harborth H., Kemnitz A., Moller M., Sussenbach A. Ganzzahlige planare Darstellungen der platonischen Korper // Elem. Math.. — 1987. — Т. 42. — С. 118–122.
- Kemnitz A., Harborth H. Plane integral drawings of planar graphs // Discrete Math.. — 2001. — Т. 236. — С. 191–195. — doi:10.1016/S0012-365X(00)00442-8.
- Bojan Mohar, Carsten Thomassen. Graphs on Surfaces. — Johns Hopkins University Press, 2001. — С. roblem 2.8.15. — ISBN 0-8018-6689-8.
- Horst Sachs. Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981. — Springer-Verlag, 1983. — Т. 1018. — С. 230–241. — ISBN 978-3-540-12687-4. — doi:10.1007/BFb0071633.
- Walter Schnyder. Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA). — 1990. — С. 138–148.
- Stein S. K. Convex maps // Proceedings of the American Mathematical Society. — 1951. — Т. 2, вып. 3. — С. 464–466. — doi:10.2307/2031777. — .
- Tutte W. T. How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13. — С. 743–767. — doi:10.1112/plms/s3-13.1.743.
- Klaus Wagner. Bemerkungen zum Vierfarbenproblem // Jahresbericht der Deutschen Mathematiker-Vereinigung. — 1936. — Т. 46. — С. 26–32..
Для улучшения этой статьи желательно:
|