Внешнепланарный граф - Outerplanar graph - Wikipedia

Максимальный внешнепланарный граф и его 3-раскраска.

В полный график K₄ - это наименьший плоский граф, не являющийся внешнепланарным.

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

Внешнепланарные графы можно охарактеризовать (аналогично Теорема Вагнера для плоских графов) двумя запрещенные несовершеннолетние K₄ и K_2,3, или их Граф инвариантов Колена де Вердьера У них есть гамильтоновы циклы тогда и только тогда, когда они двусвязны, и в этом случае внешняя грань образует единственный гамильтонов цикл. Каждый внешнепланарный граф 3-раскрашиваем и имеет вырождение и ширина дерева максимум 2.

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

История

Внешнепланарные графы впервые были изучены и названы Чартран и Харари (1967), в связи с проблемой определения планарности графов, сформированных с помощью идеальное соответствие для соединения двух копий базового графа (например, многие из обобщенные графы Петерсена формируются таким образом из двух копий одного график цикла ). Как они показали, когда базовый граф двусвязный, граф, построенный таким образом, является планарным тогда и только тогда, когда его базовый граф внешнепланарный и соответствие образует двугранный перестановка его внешнего цикла. Шартран и Харари также доказали аналог Теорема Куратовского для внешнепланарных графов, что граф является внешнепланарным тогда и только тогда, когда он не содержит подразделение одного из двух графиков K₄ или же K_2,3.

Определение и характеристики

Внешнепланарный граф - это неориентированный граф это может быть нарисованный в самолет без переходы таким образом, чтобы все вершины принадлежали неограниченной грани чертежа. То есть ни одна вершина не окружена ребрами полностью. Как вариант, график грамм внешнепланарен, если граф, сформированный из грамм добавлением новой вершины с ребрами, соединяющими ее со всеми остальными вершинами, является планарный граф.^[1]

А максимальный внешнепланарный граф является внешнепланарным графом, к которому не могут быть добавлены никакие дополнительные ребра при сохранении внешней планарности. Каждый максимальный внешнепланарный граф с п вершин ровно 2п - 3 ребра, и каждая ограниченная грань максимального внешнепланарного графа является треугольником.

Запрещенные графы

Внешнепланарные графы имеют характеристика запрещенного графа аналогично Теорема Куратовского и Теорема Вагнера для плоских графов: граф внешнепланарен тогда и только тогда, когда он не содержит подразделение из полный график K₄ или полный двудольный граф K_2,3.^[2] В качестве альтернативы граф является внешнепланарным тогда и только тогда, когда он не содержит K₄ или же K_2,3 как незначительный, граф, полученный из него удалением и сжатием ребер.^[3]

А граф без треугольников внешнепланарен тогда и только тогда, когда он не содержит подразделение K_2,3.^[4]

Инвариант Колена де Вердьера

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

Характеристики

Биконность и гамильтоничность

Внешнепланарный граф двусвязный тогда и только тогда, когда внешняя грань графа образует простой цикл без повторяющихся вершин. Внешнепланарный граф Гамильтониан тогда и только тогда, когда он двусвязен; в этом случае внешняя грань образует единственный гамильтонов цикл.^[5] В более общем плане размер самого длинного цикла во внешнепланарном графе равен количеству вершин в его наибольшем двусвязный компонент. По этой причине поиск гамильтоновых циклов и самых длинных циклов во внешнепланарных графах может быть решен в линейное время, в отличие от NP-полнота этих задач для произвольных графов.

Каждый максимальный внешнепланарный граф удовлетворяет более сильному условию, чем гамильтоничность: это узел панциклический, что означает, что для каждой вершины v и каждый k в диапазоне от трех до количества вершин в графе имеется длина -k цикл, содержащий v. Цикл такой длины можно найти, многократно удаляя треугольник, который соединен с остальной частью графа одним ребром, так что удаленная вершина не является v, пока внешняя грань оставшегося графа не станет длиной k.^[6]

Планарный граф является внешнепланарным тогда и только тогда, когда каждый из его двусвязных компонентов является внешнепланарным.^[4]

Окраска

Все внешнепланарные графы без петель могут быть цветной использование всего трех цветов;^[7] этот факт занимает видное место в упрощенном доказательстве Хватала Теорема о художественной галерее к Фиск (1978). 3-раскраску можно найти в линейное время по жадная окраска алгоритм, удаляющий любую вершину степень не более двух, рекурсивно окрашивает оставшийся граф, а затем добавляет обратно удаленную вершину цветом, отличным от цветов двух ее соседей.

В соответствии с Теорема Визинга, то хроматический индекс любого графа (минимальное количество цветов, необходимых для окраски его ребер, чтобы никакие два соседних ребра не имели одинаковый цвет) либо максимальное степень любой вершины графа или одна плюс максимальная степень. Однако в связном внешнепланарном графе хроматический индекс равен максимальной степени, за исключением тех случаев, когда граф образует цикл нечетной длины.^[8] Раскраска ребер с оптимальным количеством цветов может быть найдена за линейное время на основе обход в ширину слабого дуального дерева.^[7]

Другие свойства

Внешнепланарные графы имеют вырождение не более двух: каждый подграф внешнепланарного графа содержит вершину со степенью не более двух.^[9]

Внешнепланарные графы имеют ширина дерева не более двух, что означает, что многие задачи оптимизации графа НП-полный для произвольных графов может быть решена в полиномиальное время к динамическое программирование когда вход внешнепланарный. В более общем смысле, k-непланарные графы имеют ширину дерева O (k).^[10]

Каждый внешнепланарный граф можно представить в виде граф пересечений прямоугольников, выровненных по осям на плоскости, поэтому внешнепланарные графы имеют коробочка максимум два.^[11]

Связанные семейства графов

А кактус граф. Кактусы образуют подкласс внешнепланарных графов.

Каждый внешнепланарный граф является планарный граф.Каждый внешнепланарный граф также является подграфом последовательно-параллельный граф.^[12] Однако не все плоские последовательно-параллельные графы внешнепланарны. В полный двудольный граф K_2,3 плоский и последовательно-параллельный, но не внешнепланарный. С другой стороны, полный график K₄ плоский, но не последовательно-параллельный или внешнепланарный. Каждый лес и каждый кактус граф внешнепланарные.^[13]

В слабый плоский дуальный граф вложенного внешнепланарного графа (граф, имеющий вершину для каждой ограниченной грани вложения и ребро для каждой пары смежных ограниченных граней) является лесом, а слабый плоский двойственный элемент График Халина внешнепланарный граф. Планарный граф является внешнепланарным тогда и только тогда, когда его слабый двойник является лесом, и он является халиновым тогда и только тогда, когда его слабый двойник двусвязен и внешнепланарен.^[14]

Есть понятие степени внешнепланарности. 1-внешнепланарное вложение графа аналогично внешнепланарному вложению. За k > 1 плоское вложение называется k-апланарный если удаление вершин на внешней грани приводит к (k - 1) -внешнеплоскостное вложение. График k-outerplanar, если он имеет k-аплоскостное вложение.^[15]

An внешний 1-планарный граф, аналогично 1-планарные графы может быть нарисован в диске с вершинами на границе диска и с не более чем одним пересечением на каждом ребре.

Каждый максимальный внешнепланарный граф является хордовый граф. Каждый максимальный внешнепланарный граф является график видимости из простой многоугольник.^[16] Максимальные внешнепланарные графы также образуются как графики триангуляции многоугольников. Они примеры 2-деревья, из последовательно-параллельные графы, и из хордовые графы.

Каждый внешнепланарный граф является круговой график, то граф пересечений набора хорд круга.^[17]

Примечания

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

внешняя ссылка

• Внешнепланарные графы на Информационная система по классам графов и их включениям
• Вайсштейн, Эрик В. «Внешний график». MathWorld.