Внешнепланарный граф

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

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

Внешнепланарные графы можно охарактеризовать (аналогично теореме Вагнера для планарных графов) двумя запрещёнными минорами K4и K2,3, или их инвариантами Колен де Вердьера. Эти графы имеют гамильтоновы циклы тогда и только тогда, когда они двусвязны, и в этом случае внешняя грань образует единственный гамильтонов цикл. Любой внешнепланарный граф раскрашиваем в 3 цвета и имеет вырождение[en] и древесную ширину не больше 2.

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

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

Внешнепланарные графы впервые изучали и назвали Шартран и Харари[1] при рассмотрении задачи определения планарности графов, образованных при помощи совершенных паросочетаний, связывающих две копии базового графа (например, многие из обобщённых графов Петерсена образованы этим способом из двух копий графа-цикла). Как они показали, если базовый граф двусвязен, граф, полученный из него описанным способом, планарен тогда и только тогда, когда базовый граф внешнепланарен и паросочетание образует диэдральные перестановки внешнего цикла.

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

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

Максимальный внешнепланарный граф — это внешнепланарный граф, к которому нельзя добавить какое-либо ребро, не нарушив свойство внешнепланарности. Любой максимальный внешнепланарный граф с n вершинами имеет в точности 2n − 3 рёбер и любая ограниченная грань максимального внешнепланарного графа является треугольником.

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

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

Граф без треугольников внешнепланарен тогда и только тогда, когда он не содержит подразделений K2,3[5].

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

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

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

Двусвязность и гамильтоновость[править | править код]

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

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

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

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

Все внешнепланарные графы без петель могут быть раскрашены всего тремя цветами[7]. Этот факт проявляется заметно в упрощенном доказательстве теоремы о картинной галерее[en] Хватала[en] Фиском[8]. Раскраска тремя цветами может быть найдена за линейное время алгоритмом жадной раскраски, который удаляет любую вершину со степенью, не превосходящей двух и раскрашивает оставшийся граф рекурсивно, а затем возвращает каждую из удалённых вершин с цветом, отличным от цветов двух её соседей.

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

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

Внешнепланарные графы имеют вырождение[en], не превосходящее 2 — любой подграф внешнепланарного графа содержит вершину со степенью, не превосходящей 2[10].

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

Любой внешнепланарный граф можно представить в виде графа пересечений прямоугольников с параллельными осям сторонами, так что внешнепланарные графы имеют интервальную размерность[12][13] максимум два[14][15].

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

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

Любой внешнепланарный граф является планарным. Любой внешнепланарный граф является подграфом параллельно-последовательного графа[16]. Однако не все параллельно-последовательные графы внешнепланарны. Полный двудольный граф K2,3 является планарным и параллельно-последовательным, но не внешнепланарным. С другой стороны, полный граф K4 планарен, но ни параллельно-последователен, ни внешнепланарен. Любой лес и любой кактус внешнепланарны[17].

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

Существует понятие степени внешнепланарности. 1-внешнепланарное вложение графа — это то же самое, что внешнепланарное вложение. Для k > 1 говорят, что планарное вложение является k-внешнепланарным, если удаление вершины из внешней грани приводит к (k − 1)-внешнепланарному вложению. Граф является k-внешнепланарным тогда и только тогда, когда он имеет k-внешнепланарное вложение[19][5].

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

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

Примечания[править | править код]

  1. 1 2 Chartrand, Harary, 1967.
  2. Felsner, 2004.
  3. Chartrand, Harary (1967); Sysło (1979); Brandstädt, Le, Spinrad (1999), Proposition 7.3.1, p. 117; Felsner (2004).
  4. Diestel, 2000.
  5. 1 2 3 4 Sysło, 1979.
  6. Li, Corneil, Mendelsohn, 2000, с. Proposition 2.5.
  7. 1 2 Proskurowski, Sysło, 1986.
  8. Fisk, 1978.
  9. Fiorini, 1975.
  10. Lick, White, 1970.
  11. Baker, 1994.
  12. Определение интервальной размерности графа можно найти в книге Робертса. Английское название термина — boxicity.
  13. Робертс, 1986, с. 129.
  14. Scheinerman, 1984.
  15. Brandstädt, Le, Spinrad, 1999, с. 54.
  16. Brandstädt, Le, Spinrad, 1999, с. 174.
  17. Brandstädt, Le, Spinrad, 1999, с. 169.
  18. Sysło, Proskurowski, 1983.
  19. Kane, Basu, 1976.
  20. El-Gindy (1985); Lin, Skiena (1995); Brandstädt, Le, Spinrad (1999), Theorem 4.10.3, p. 65.
  21. Wessel, Pöschel, 1985.
  22. Unger, 1988.

Литература[править | править код]

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