Теорема Фари

Чтобы узнать о других значениях, см. теорему Фари–Милнора .

В математической области графов теории теорема Фари утверждает, что любой плоский простой граф можно нарисовать без пересечений, так что его ребра представляют собой отрезки прямых линий . То есть возможность рисовать ребра графа в виде кривых, а не в виде отрезков прямых линий не позволяет рисовать более широкий класс графов. Теорема названа в честь Иштвана Фари , хотя она была независимо доказана Клаусом Вагнером ( 1936 ), Фари ( 1948 ) и Шерманом К. Штайном ( 1951 ).

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

Шаг индукции для доказательства теоремы Фари.

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

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

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

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

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

Пружинная теорема Тутте утверждает, что каждый 3-связный плоский граф можно нарисовать на плоскости без пересечений так, чтобы его ребра были отрезками прямых, а внешняя грань представляла собой выпуклый многоугольник (Tutte 1963). Оно названо так потому, что такое вложение можно найти как положение равновесия системы пружин, представляющих ребра графа.

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

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

Нерешенная задача по математике :

Имеет ли каждый планарный граф представление прямой линии, в котором длины всех ребер являются целыми числами?

(еще нерешенные задачи по математике)

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

Сакс (1983) поднял вопрос о том, имеет ли каждый граф с бесзвенным вложением в трехмерном евклидовом пространстве бесзвенное вложение, в котором все ребра представлены отрезками прямых, аналогично теореме Фари для двумерных вложений.

См. также

• Минимизация изгиба

Ссылки

• Фари, Иштван (1948), «О прямолинейном представлении плоских графов», Acta Sci. Математика. (Сегед) , 11 : 229–233, MR   0026311 .
• де Фрессе, Юбер; Пах, Янош ; Поллак, Ричард (1988), «Малые наборы, поддерживающие вложения Фэри плоских графов» , Двадцатый ежегодный симпозиум ACM по теории вычислений , стр. 426–433, doi : 10.1145/62212.62254 , ISBN  0-89791-264-0 , S2CID   15230919 .
• де Фрессе, Юбер; Пах, Янош ; Поллак, Ричард (1990), «Как нарисовать плоский граф на сетке», Combinatorica , 10 : 41–51, doi : 10.1007/BF02122694 , MR   1075065 , S2CID   6861762 .
• Гилен, Джим ; Го, Энджи; Маккиннон, Дэвид (2008), «Вложения прямых кубических плоских графов с целыми длинами ребер» (PDF) , Journal of Graph Theory , 58 (3): 270–274, doi : 10.1002/jgt.20304 .
• Харборт, Хейко; Кемниц, Арнфрид; Мёллер, Мейнхард; Зюссенбах, Андреас (1987), «Целочисленные плоские представления платоновых тел» , Elements of Mathematics , 42 (5): 118–122, MR   0905393 .
• Кемниц, А.; Харборт, Х. (2001), «Плоские интегральные рисунки плоских графов», Discrete Mathematics , 236 (1–3): 191–195, doi : 10.1016/S0012-365X(00)00442-8 .
• Мохар, Боян (2003), Задачи из книги «Графы на поверхностях» .
• Мохар, Боян ; Томассен, Карстен (2001), Графики на поверхностях , Издательство Университета Джонса Хопкинса, стр. Проблема 2.8.15, ISBN  0-8018-6689-8 .
• Сакс, Хорст (1983), «О пространственном аналоге теоремы Куратовского о плоских графах - открытая проблема», в Горовецкий, М.; Кеннеди, JW; Сысло М.М. (ред.), Теория графов: материалы конференции, состоявшейся в Лагуве, Польша, 10–13 февраля 1981 г. , Конспекты лекций по математике, том. 1018, Springer-Verlag, стр. 230–241, doi : 10.1007/BFb0071633 , ISBN.  978-3-540-12687-4 .
• Шнайдер, Уолтер (1990), «Вложение плоских графов в сетку» , Proc. 1-й симпозиум ACM/SIAM по дискретным алгоритмам (SODA) , стр. 138–148, ISBN  9780898712513 .
• Штейн, С.К. (1951), «Выпуклые карты», Труды Американского математического общества , 2 (3): 464–466, doi : 10.2307/2031777 , JSTOR   2031777 , MR   0041425 .
• Тутте, WT (1963), «Как нарисовать график», Труды Лондонского математического общества , 13 : 743–767, doi : 10.1112/plms/s3-13.1.743 , MR   0158387 .
• Вагнер, Клаус (1936), «Замечания о проблеме четырех цветов» , Годовой отчет Ассоциации немецких математиков , 46 : 26–32 .