Теорема Фари о распрямлении графа

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

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

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

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

Шаг индукции.

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

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

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

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

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

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

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

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

Шаблон:Unsolved Шаблон:Не переведено 5 поднял вопрос, существует ли для любого планарного графа представление с прямыми рёбрами, в котором все длины рёбер являются целыми числами. Верна ли гипотеза Харборта, остаётся открытым вопросом (Шаблон:As of). Однако известно, что вложение с целочисленными прямыми рёбрами существует для кубических графовШаблон:Sfn.

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

См. также

• Минимизация изломов

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья.