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

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

Не следует путать с теоремой Фарри — утверждением, относящимся к квантовой электродинамике.

Названа в честь венгерского математика Иштвана Фа́ри[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-связный планарный граф может быть представлен как рёбра выпуклого многогранника в трёхмерном пространстве. Вложение с прямыми рёбрами графа может быть получено как проекция такого многогранника на плоскость.

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

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

Хайуо Харборт поднял вопрос, существует ли для любого планарного графа представление с прямыми рёбрами, в котором все длины рёбер являются целыми числами[6]. Верна ли гипотеза Харборта, остаётся открытым вопросом (на 2014 год). Однако известно, что вложение с целочисленными прямыми рёбрами существует для кубических графов[7].

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

См. также

Примечания
  1. Fáry, 1948, с. 229–233.
  2. Wagner, 1936.
  3. Stein, 1951.
  4. Приведённое доказательство можно найти в книге В. В. Прасолов. Элементы комбинаторной и дифференциальной топологии. М.: МЦНМО, 2004.
  5. Tutte, 1963, с. 743–767.
  6. Harborth, Kemnitz, Moller, Sussenbach, 1987; Kemnitz, Harborth, 2001; Mohar, Thomassen, 2001.
  7. Geelen, Guo, McKinnon, 2008.
  8. Sachs, 1983.

Литература
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.