Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Максимальный внешнепланарный граф и его 3-раскраска.
Полный граф K 4 является наименьшим плоский граф , который не внешнепланарным.

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

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

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

История [ править ]

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

Определение и характеристики [ править ]

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

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

Запрещенные графики [ править ]

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

Граф без треугольников является внешнепланарным тогда и только тогда , когда она не содержит разбиение К 2,3 . [4]

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

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

Свойства [ править ]

Биконность и гамильтоничность [ править ]

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

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

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

Раскраска [ править ]

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

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

Другие свойства [ править ]

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

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

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

Связанные семейства графиков [ править ]

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

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

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

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

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

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

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

Заметки [ править ]

  1. ^ Felsner (2004) .
  2. ^ Чартран и Харари (1967) ; Сысло (1979) ; Brandstädt, Le & Spinrad (1999) , предложение 7.3.1, стр. 117; Фельснер (2004) .
  3. ^ Дистель (2000) .
  4. ^ а б Сысло (1979) .
  5. ^ Чартран и Харари (1967) ; Сысло (1979) .
  6. ^ Ли, Корнейл и Мендельсон (2000) , предложение 2.5.
  7. ^ a b Проскуровский и Сисло (1986) .
  8. ^ Fiorini (1975) .
  9. Перейти ↑ Lick & White (1970) .
  10. ^ Бейкер (1994) .
  11. ^ Шайнерман (1984) ; Brandstädt, Le & Spinrad (1999) , стр. 54.
  12. ^ Brandstädt, Le & Spinrad (1999) , стр. 174.
  13. ^ Brandstädt, Le & Spinrad (1999) , стр. 169.
  14. ^ Sysło & Proskurowski (1983) .
  15. ^ Кейн и Басу (1976) ; Сысло (1979) .
  16. ^ El-Gindy (1985) ; Лин и Скиена (1995) ; Brandstädt, Le & Spinrad (1999) , теорема 4.10.3, с. 65.
  17. ^ Wessel & Pöschel (1985) ; Унгер (1988) .

Ссылки [ править ]

  • Бейкер, Brenda S. (1994), "Приближенные алгоритмы для NP-полных задач на плоских графах", Журнал ACM , 41 (1): 153-180, DOI : 10,1145 / 174644,174650.
  • Боза, Луис; Fedriani, Eugenio M .; Нуньес, Хуан (2004), "Проблема внешних вложений в псевдоповерхности", Ars Combinatoria , 71 : 79–91.
  • Боза, Луис; Fedriani, Eugenio M .; Нуньес, Хуан (2004), "Наборы препятствий для графов внешней поверхности банана", Ars Combinatoria , 73 : 65–77.
  • Боза, Луис; Fedriani, Eugenio M .; Нуньес, Хуан (2006), "Бесчисленные графы со всеми своими вершинами в одном лице", Acta Mathematica Hungarica , 112 (4): 307-313, DOI : 10.1007 / s10474-006-0082-0.
  • Боза, Луис; Fedriani, Eugenio M .; Нуньес, Хуан (2010), "Outer-вложимость в некоторых pseudosurfaces , вытекающих из трех сфер", Дискретная математика , 310 : 3359-3367, DOI : 10.1016 / j.disc.2010.07.027.
  • Брандштадт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, Общество промышленной и прикладной математики , ISBN 0-89871-432-X.
  • Чартран, Гэри ; Харари, Франк (1967), «Планарные графы перестановок» , Анналы института Анри Пуанкаре B , 3 (4): 433–438, MR  0227041.
  • Дистель, Рейнхард (2000), Теория графов , Тексты для выпускников по математике , 173 , Springer-Verlag, p. 107, ISBN 0-387-98976-5.
  • Эль-Гинди, Х. (1985), Иерархическая декомпозиция многоугольников с приложениями , доктор философии. кандидатская диссертация, Университет Макгилла. Цитируется Brandstädt, Le & Spinrad (1999) .
  • Фельснер, Стефан (2004), Геометрические графы и устройства: некоторые главы комбинационной геометрии , Vieweg + Teubner Verlag, стр. 6, ISBN 978-3-528-06972-8.
  • Фиорини, Стэнли (1975), «О хроматическом индексе внешнепланарных графов», Журнал комбинаторной теории , серия B, 18 (1): 35–38, DOI : 10.1016 / 0095-8956 (75) 90060-X.
  • Фиск, Стив (1978), «Краткое доказательство теоремы о сторожем Хватала», Журнал комбинаторной теории , серия B, 24 : 374, DOI : 10.1016 / 0095-8956 (78) 90059-X.
  • Fleischner, Herbert J .; Геллер, Д.П .; Харари, Франк (1974), «Внешнепланарные графы и слабые двойники», Журнал Индийского математического общества , 38 : 215–219, MR  0389672.
  • Kane, Vinay G .; Басу, Санат К. (1976), «О глубине плоского графа», Дискретная математика , 14 (1): 63–67, DOI : 10.1016 / 0012-365X (76) 90006-6.
  • Ли, Мин-Чу; Корнейл, Дерек Г .; Мендельсон, Эрик (2000), "Pancyclicity и NP-полнота в плоских графах", Дискретная прикладная математика , 98 (3): 219-225, DOI : 10.1016 / S0166-218X (99) 00163-8.
  • Лик, Дон Р .; Белый, Артур Т. (1970), " К -degenerate графов" , Canadian Journal математики , 22 : 1082-1096, DOI : 10,4153 / CJM-1970-125-1.
  • Линь, Яу-Линг; Skiena, Стивен С. (1995), "Сложность аспекты видимости графов", Международный журнал вычислительной геометрии и приложений , 5 (3): 289-312, DOI : 10,1142 / S0218195995000179.
  • Проскуровский, Анджей; Sysło, Маца М. (1986), «Эффективный вершинный и ребро окраски Внешнепланарных графов», SIAM журнал по алгебраическому и методам дискретных , 7 : 131-136, DOI : 10,1137 / 0607016.
  • Шайнерман, Э. Р. (1984), Классы пересечений и множественные параметры пересечений графа , доктор философии. диссертация, Принстонский университет. Цитируется Brandstädt, Le & Spinrad (1999) .
  • Сысло, Мацей М. (1979), "Характеризация внешнепланарных графов", Дискретная математика , 26 (1): 47–53, DOI : 10.1016 / 0012-365X (79) 90060-8.
  • Sysło, Maciej M .; Проскуровский, Анджей (1983), «О графах Халина», Теория графов: Труды конференции, состоявшейся в Лагове, Польша, 10–13 февраля 1981 г. , Конспект лекций по математике , 1018 , Springer-Verlag, стр. 248–256, DOI : 10.1007 / BFb0071635.
  • Унгер, Вальтер (1988), "О k- раскраске круговых графов", Proc. 5-й симпозиум по теоретическим аспектам информатики (STACS '88) , конспект лекций по информатике , 294 , Springer-Verlag, стр. 61–72, doi : 10.1007 / BFb0035832.
  • Wessel, W .; Pöschel, R. (1985), "О круговых графах", в Sachs, Horst (ed.), Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory, проведенной в Eyba, 1-5 октября 1984 г. , Teubner-Texte zur Mathematik, 73 , BG Teubner, стр. 207–210. Цитируется Унгером (1988) .

Внешние ссылки [ править ]

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