Теорема Фариса - Fárys theorem

Для использования в других целях см. Теорема Фэри-Милнора.

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

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

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

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

К Формула Эйлера для плоских графов, грамм имеет 3п − 6 края; эквивалентно, если определить недостаток вершины v в грамм быть 6 − град (v), сумма недостатков составляет 12. С грамм имеет не менее четырех вершин и все грани грамм являются треугольниками, то каждая вершина в грамм имеет степень не ниже трех. Следовательно, каждая вершина в грамм имеет дефект не более трех, поэтому имеется не менее четырех вершин с положительным дефектом. В частности, мы можем выбрать вершину v не более чем с пятью соседями, отличными от а, б и c. Позволять ГРАММ' быть сформированным путем удаления v из грамм и ретриангулируя лицо ж сформированный путем удаления v. По индукции ГРАММ' имеет комбинаторно изоморфное повторное вложение прямой, в которое abc это внешняя грань. Поскольку повторное встраивание ГРАММ' комбинаторно изоморфен ГРАММ', удалив из него края, которые были добавлены для создания ГРАММ' оставляет лицо ж, который теперь представляет собой многоугольник п максимум с пяти сторон. Чтобы завершить рисунок к прямому комбинаторно изоморфному повторному вложению грамм, v должны быть помещены в многоугольник и соединены прямыми линиями с вершинами многоугольника. Посредством Теорема о художественной галерее, существует точка внутри п на котором v можно разместить так, чтобы края от v в вершины п не пересекайте никакие другие ребра, завершая доказательство.

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

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

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

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

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

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

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Есть ли у каждого плоского графа прямолинейное представление, в котором все длины ребер являются целыми числами?
(больше нерешенных задач по математике)

Хайко Харборт поднял вопрос, имеет ли каждый планарный граф прямолинейное представление, в котором все длины ребер являются целыми числами.[2] Правда о Гипотеза Харборта остается неизвестным по состоянию на 2014 г.. Однако известно, что вложения прямых целочисленных расстояний существуют для кубические графы.[3]

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

Смотрите также

Примечания

  1. ^ Следующее доказательство можно найти в Чартран, Гэри; Лесняк, Линда; Чжан, Пин (2010), Графы и диграфы (5-е изд.), CRC Press, стр. 259–260, ISBN  9781439826270.
  2. ^ Harborth et al. (1987); Кемниц и Харборт (2001); Мохар и Томассен (2001); Мохар (2003).
  3. ^ Гилен, Го и Маккиннон (2008).

Рекомендации