Теорема Фари о распрямлении графа: различия между версиями

[отпатрулированная версия]

Содержимое удалено Содержимое добавлено

Линейный

Текущая версия от 13:40, 16 октября 2023

Теорема Фа́ри — теоретико-графовое утверждение о возможности выпрямить рёбра любого планарного графа. Иными словами, разрешение рисовать рёбра не в виде отрезков, а в виде кривых, не расширяет класс планарных графов.

Названа в честь венгерского математика Иштвана Фа́ри^[1], хотя была доказана независимо Клаусом Вагнером в 1936^[2] и Штайном в 1951^[3].

Формулировка: любой простой планарный граф имеет плоское представление, в котором все рёбра представлены в виде отрезков прямых.

Доказательство

Один из путей доказательства теоремы Фари — применение математической индукции^[4]. Пусть $G$ — простой планарный граф с $n$ вершинами. Мы можем считать граф максимальным планарным, при необходимости можем добавить рёбра в исходный граф $G$ . Все грани графа $G$ в этом случае должны быть треугольниками, так как мы можем добавить ребро в любую грань с бо́льшим числом сторон, не нарушая планарности графа, что противоречит соглашению о максимальности графа. Выберем некоторые три вершины $a,b,c$ , образующие треугольную грань графа $G$ . Мы докажем по индукции по $n$ , что существует комбинаторно изоморфное другое вложение с прямыми рёбрами графа $G$ , в котором треугольник $abc$ является внешней гранью вложения. (Комбинаторная изоморфность означает, что вершины, рёбра и грани нового рисунка могут быть сделаны соответствующими элементам старого рисунка и при этом сохраняются все отношения инцидентности между рёбрами, вершинами и гранями, не только между вершинами и рёбрами.) База индукции тривиальна, когда $a,b,c$ являются единственными вершинами в $G$ ( $n=3$ ).

По формуле Эйлера для планарных графов граф $G$ имеет $3n-6$ рёбер. Эквивалентно, если определить дефицит вершины $v$ в графе $G$ как $6-\deg(v)$ , сумма дефицитов равна 12. Каждая вершина в графе $G$ может иметь дефицит не выше трёх, так что имеется по меньшей мере четыре вершины с положительным дефицитом. В частности, мы можем выбрать вершину $v$ с не более чем пятью соседями, которая отлична от $a,b$ и $c$ . Пусть $G'$ образуется путём удаления вершины $v$ из графа $G$ и триангуляции грани $f$ , полученной после удаления вершины $v$ . По индукции, граф $G'$ имеет комбинаторно изоморфное вложение с прямолинейными рёбрами, в котором $abc$ является внешней гранью. Поскольку полученное вложение $G$ было комбинаторно изоморфно $G'$ , удаление из него рёбер, которые были добавлены для получения графа $G'$ оставляет грань $f$ , которая теперь представляет собой многоугольник $P$ с не более чем пятью сторонами. Для получения рисунка $G$ с комбинаторно изоморфным вложением с прямыми рёбрами, вершина $v$ должна быть добавлена в многоугольник и соединена отрезками с вершинами многоугольника. По теореме о картинной галерее существует точка внутри $P$ , куда можно поместить вершину $v$ , так что рёбра, соединяющие вершину $v$ с вершинами многоугольника $P$ , не пересекут другие рёбра многоугольника, что завершает доказательство.

Шаг индукции доказательства проиллюстрирован справа.

Связанные результаты

Де Фрейсикс, Пах и Полак показали, как найти за линейное время рисунок с прямолинейными рёбрами на решётке с размерами, линейно зависящими от размера графа, давая универсальное множество точек с квадратичными размерами. Похожий метод использовал Шнайдер для доказательства улучшенных границ и характеристики планарности, где он основывался на частичном порядке инцидентности. Его работа делает упор на существование определённого разбиения рёбер максимального планарного графа на три дерева, которые известны как лес Шнайдера.

Теорема Татта «о резиновой укладке» утверждает, что любой трёхсвязный планарный граф можно нарисовать на плоскости без пересечений так, что его рёбра являются отрезками прямых и внешняя грань является выпуклым многоугольником^[5]. Название отражает факт, что такое вложение может быть найдено как точка равновесия системы пружин, представляющих рёбра графа.

Теорема Штайница утверждает, что любой 3-связный планарный граф может быть представлен как рёбра выпуклого многогранника в трёхмерном пространстве. Вложение с прямыми рёбрами графа $G$ может быть получено как проекция такого многогранника на плоскость.

Теорема об упаковке кругов утверждает, что любой планарный граф может быть представлен как граф пересечений набора непересекающихся окружностей на плоскости. Если разместить каждую вершину графа в центре соответствующей окружности, получим представление графа с прямолинейными рёбрами.

Нерешённые проблемы математики: Существует ли для любого планарного графа представление с прямыми рёбрами, в котором длины всех рёбер являются целыми числами?

Хайуо Харборт^[англ.] поднял вопрос, существует ли для любого планарного графа представление с прямыми рёбрами, в котором все длины рёбер являются целыми числами^[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. — JSTOR 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..

[_5903d09ed06983e4-1] Fáry, 1948, с. 229–233.

[_a716ab292ce25d06-2] Wagner, 1936.

[_25539388e57b6676-3] Stein, 1951.

[4] Приведённое доказательство можно найти в книге В. В. Прасолов. Элементы комбинаторной и дифференциальной топологии. М.: МЦНМО, 2004.

[_a406cfc05ea2265b-5] Tutte, 1963, с. 743–767.

[6] Harborth, Kemnitz, Moller, Sussenbach, 1987; Kemnitz, Harborth, 2001; Mohar, Thomassen, 2001.

[_1ac030e9c0e1c01f-7] Geelen, Guo, McKinnon, 2008.

[_e368a915599d2f3e-8] Sachs, 1983.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Строка 1: / Строка 1: @@
+{{Не путать|Теорема Фарри|теоремой Фарри|утверждением, относящимся к квантовой электродинамике}}
-'''Теорема Фа́ри''' — это [[теорема]] [[теория графов|теории графов]], названная в честь венгерского математика {{не переведено|есть=:en:István Fáry|нужно=Иштвана Фа́ри}}{{sfn|Fáry|1948|с=229–233}}.
+'''Теорема Фа́ри''' — [[Теория графов|теоретико-графовое]] утверждение о возможности выпрямить рёбра любого [[планарный граф|планарного графа]]. Иными словами, разрешение рисовать рёбра не в виде отрезков, а в виде кривых, не расширяет класс планарных графов.
-{{рамка}}
-Любой [[Граф (математика)#Обобщение понятия графа|простой]] [[планарный граф]] имеет плоское представление, в котором все ребра представлены в виде [[Отрезок|отрезков]] прямых.
+Названа в честь венгерского математика [[Фари, Иштван|Иштвана Фа́ри]]{{sfn|Fáry|1948|с=229–233}}, хотя была доказана независимо Клаусом Вагнером в 1936{{sfn|Wagner|1936}} и Штайном в 1951{{sfn|Stein|1951}}.
-{{конец рамки}}
-То есть разрешение рисовать рёбра не в виде отрезков, а в виде кривых линий, не расширяет класс графов. Теорема носит имя Фа́ри, хотя была доказана независимо Клаусом Вагнером в 1936{{sfn|Wagner|1936}} и Штайном в 1951{{sfn|Stein|1951}}.
+Формулировка: любой [[Граф (математика)#Обобщение понятия графа|простой]] [[планарный граф]] имеет плоское представление, в котором все рёбра представлены в виде [[Отрезок|отрезков]] прямых.
 == Доказательство ==
-[[Файл:Fary-induction.svg|thumb|right|Шаг индукции доказательства теоремы Фари.]]
+[[Файл:Fary-induction.svg|thumb|right|Шаг индукции.]]
-Один из путей доказательства теоремы Фари — применение [[Математическая индукция|математической индукции]]<ref>Приведённое доказательство можно найти в книге Чартранда, Лесняк и Чжана «Графы и диграфы» {{harv|Chartrand, Lesniak, Zhang|2010|loc=259–260}}<!-- Есть некоторая вероятность, что Чартранд и Лесняк взяли доказательство с (английской версии) этой статьи, поскольку их публикация появилась позже появления статьи в WikipediA. --></ref>. Пусть {{mvar|G}} — простой [[планарный граф]] с {{mvar|n}} вершинами. Мы можем считать граф максимальным планарным, при необходимости можем добавить рёбра в исходный граф {{mvar|G}}. Все грани графа {{mvar|G}} в этом случае должны быть треугольниками, так как мы можем добавить ребро в любую грань с бо́льшим числом сторон, не нарушая планарности графа, что противоречит соглашению о максимальности графа. Выберем некоторые три вершины {{math|''a'', ''b'', ''c''}}, образующие треугольную грань графа {{mvar|G}}. Мы докажем по индукции по {{mvar|n}}, что существует комбинаторно изоморфное другое вложение с прямыми рёбрами графа {{mvar|G}}, в котором треугольник {{math|''abc''}} является внешней гранью вложения.  (''Комбинаторная изоморфность'' означает, что вершины, рёбра и грани нового рисунка могут быть сделаны соответствующими элементам старого рисунка и при этом сохраняются все отношения инцидентности между рёбрами, вершинами и гранями, не только между вершинами и рёбрами.) База индукции тривиальна, когда {{mvar|a}}, {{mvar|b}} и {{mvar|c}} являются единственными вершинами в {{mvar|G}} ({{math|1=''n''=3}}).
+Один из путей доказательства теоремы Фари — применение [[Математическая индукция|математической индукции]]<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>).
-По [[Планарный граф|формуле Эйлера]] для планарных графов граф {{mvar|G}} имеет {{math|3''n'' &minus; 6}} рёбер. Эквивалентно, если определить ''дефицит'' вершины {{mvar|v}} в графе {{mvar|G}} как {{math|6 &minus; [[Степень вершины (теория графов)|deg]](''v'')}}, сумма дефицитов равна {{math|12}}. Каждая вершина в графе {{mvar|G}} может иметь дефицит не выше трёх, так что имеется по меньшей мере четыре вершины с положительным дефицитом. В частности, мы можем выбрать вершину {{mvar|v}} с не более чем пятью соседями, которая отлична от {{mvar|a}}, {{mvar|b}} и {{mvar|c}}. Пусть {{math|''G'''}} образуется путём удаления вершины {{mvar|v}} из графа {{mvar|G}} и триангуляции грани {{mvar|f}}, полученной после удаления вершины {{mvar|v}}.  По индукции, граф {{mvar|G'}} имеет комбинаторно изоморфное вложение с прямолинейными рёбрами, в котором {{mvar|abc}} является внешней гранью. Поскольку полученное вложение {{mvar|G}} было комбинаторно изоморфно {{mvar|G'}}, удаление из него рёбер, которые были добавлены для получения графа {{mvar|G'}} оставляет грань {{mvar|f}}, которая теперь представляет собой многоугольник{{mvar|P}} с не более чем пятью сторонами.  Для получения рисунка {{mvar|G}} с комбинаторно изоморфным вложением с прямыми рёбрами, вершина {{mvar|v}} должна быть добавлена в многоугольник и соединена отрезками с вершинами многоугольника. По [[Задача о картинной галерее# Теорема Шватала о картинной галерее|теореме о картинной галерее]] существует точка внутри {{mvar|P}}, куда можно поместить вершину {{mvar|v}}, так что рёбра, соединяющие вершину {{mvar|v}} с вершинами многоугольника {{mvar|P}}, не пересекут другие рёбра многоугольника, что завершает доказательство.
+По [[Планарный граф|формуле Эйлера]] для планарных графов граф <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>, не пересекут другие рёбра многоугольника, что завершает доказательство.
 Шаг индукции доказательства проиллюстрирован справа.
-{{clear|right}}
 == Связанные результаты ==
 Де Фрейсикс, Пах и Полак показали, как найти за линейное время рисунок с прямолинейными рёбрами на решётке с размерами, линейно зависящими от размера графа, давая [[универсальное множество точек]] с квадратичными размерами. Похожий метод использовал Шнайдер для доказательства улучшенных границ и [[Теорема Шнайдера|характеристики планарности]], где он основывался на частичном порядке инцидентности. Его работа делает упор на существование определённого разбиения рёбер максимального планарного графа на три дерева, которые известны как [[Древесность графа#Древесность как мера плотности|лес Шнайдера]].
@@ Строка 21: / Строка 21: @@
 [[Теорема Штайница]] утверждает, что любой 3-связный планарный граф может быть представлен как рёбра выпуклого многогранника в трёхмерном пространстве. Вложение с прямыми рёбрами графа <math>G</math> может быть получено как проекция такого многогранника на плоскость.
-[[Теорема об упаковке кругов]] утверждает, что любой планарный грай может быть представлен как [[граф пересечений]] набора непересекающихся окружностей на плоскости. Если разместить каждую вершину графа в центре соответствующей окружности, получим представление графа с прямолинейными рёбрами.
+[[Теорема об упаковке кругов]] утверждает, что любой планарный граф может быть представлен как [[граф пересечений]] набора непересекающихся окружностей на плоскости. Если разместить каждую вершину графа в центре соответствующей окружности, получим представление графа с прямолинейными рёбрами.
 {{unsolved|математики|Существует ли для любого планарного графа представление с прямыми рёбрами, в котором длины всех рёбер являются целыми числами?}}
-{{не переведено 5|Харборт, Хайко|Хайуо Харборт||Heiko Harborth}} поднял вопрос, существует ли для любого планарного графа представление с прямыми рёбрами, в котором все длины рёбер являются целыми числами<ref>{{harvnb|Harborth, Kemnitz, Moller, Sussenbach|1987}}; {{harvnb|Kemnitz, Harborth|2001}}; {{harvnb|Mohar, Thomassen|2001}}.</ref>. Верна ли {{не переведено 5|гипотеза Харборта|||Harborth's conjecture}}, остаётся открытым вопросом ({{As of|2014|lc=on}}). Однако известно, что вложение с целочисленными прямыми рёбрами существует для [[Кубический граф|кубических графов]]{{sfn|Geelen, Guo, McKinnon|2008}}.
+{{не переведено 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}}
-==Литература==
+== Литература ==
-{{refbegin|colwidth=30em}}
-*{{статья
+* {{статья
 |ref=Fáry
 |автор=István Fáry
@@ Строка 45: / Строка 45: @@
 |id={{MathSciNet|id=0026311}}
 }}
-*{{книга
+* {{книга
 |заглавие=Graphs & Digraphs
 |автор=Gary Chartrand, Linda Lesniak, Ping Zhang
@@ Строка 56: / Строка 56: @@
 |ссылка=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
-|страницы=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
@@ Строка 77: / Строка 79: @@
 |doi=10.1007/BF02122694
 }}
-*{{статья
+* {{статья
 |автор=Jim Geelen, Anjie Guo, David McKinnon
 |ref=Geelen, Guo, McKinnon
@@ Строка 89: / Строка 91: @@
 |год=2008
 }}
-*{{статья
+* {{статья
 |автор=Harborth H., Kemnitz A., Moller M., Sussenbach A.
 |ref=Harborth, Kemnitz, Moller, Sussenbach
@@ Строка 98: / Строка 100: @@
 |год=1987
 }}
-*{{статья
+* {{статья
 |ref=Kemnitz, Harborth
 |автор=Kemnitz A., Harborth H.
@@ Строка 108: / Строка 110: @@
 |год=2001
 }}
-*{{книга
+* {{книга
 |автор=Bojan Mohar, Carsten Thomassen
 |ref=Mohar, Thomassen
@@ Строка 117: / Строка 119: @@
 |isbn=0-8018-6689-8
 }}
-*{{книга
+* {{книга
 |ref=Sachs
 |автор=Horst Sachs
@@ Строка 133: / Строка 135: @@
 |isbn=978-3-540-12687-4
 }}
-*{{статья
+* {{статья
 |ref=Schnyder
 |автор=Walter Schnyder
@@ Строка 142: / Строка 144: @@
 |страницы=138–148
 }}
-*{{статья
+* {{статья
 |автор=Stein S. K.
 |ref=Stein
@@ Строка 155: / Строка 157: @@
 |jstor=2031777
 }}
-*{{статья
+* {{статья
 |ref=Tutte
-|автор=[[Тат, Уильям Томас|Tutte W. T.]]
+|автор=[[Татт, Уильям Томас|Tutte W. T.]]
 |заглавие=How to draw a graph
 |издание=Proceedings of the London Mathematical Society
@@ Строка 166: / Строка 168: @@
 |doi=10.1112/plms/s3-13.1.743
 }}
-*{{статья
+* {{статья
 |ref=Wagner
 |автор=Klaus Wagner
@@ Строка 175: / Строка 177: @@
 |страницы=26–32
 |ссылка=http://www.digizeitschriften.de/index.php?id=resolveppn&PPN=GDZPPN002131633}}.
-{{refend}}
 [[Категория:Планарные графы]]
 [[Категория:Теоремы теории графов]]
-{{rq|checktranslate|style|grammar}}
+{{rq|checktranslate|style}}

Теорема Фари о распрямлении графа: различия между версиями

Текущая версия от 13:40, 16 октября 2023

Содержание

Доказательство

Связанные результаты

См. также

Примечания

Литература

Навигация

Теорема Фари о распрямлении графа: различия между версиями

Текущая версия от 13:40, 16 октября 2023

Доказательство

Связанные результаты

См. также

Примечания

Литература

Навигация

Поиск