Зовніпланарний граф: відмінності між версіями

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Наступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
Створено шляхом перекладу сторінки «Внешнепланарный граф»
(Немає відмінностей)

Версія за 13:19, 25 листопада 2020

Найбільший зовніпланарний граф і його 3-розмальовка.
Повний граф K4 є найменшим планарним графом, який не є зовніпланарним.

В теорії графів зовніпланарний граф - це граф, що допускає планарну діаграму, в якій усі вершини належать зовнішній межі.

Зовніпланарні графи можна схарактеризувати (аналогічно теоремі Вагнера для планарних графів) двома забороненими мінорами K4 і K2,3, або їх інваріантами Колен де Вердьєра. Ці графи мають гамільтонові цикли тоді й лише тоді, коли вони двозв'язні, і в цьому випадку зовнішня грань утворює єдиний гамільтонів цикл. Будь-який Зовніпланарний граф можна розфарбувати в 3 кольори і він має виродження● і деревну ширину не більше 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]. Цей факт проявляється помітно у спрощеному доведенні теореми про картинну галерею● Хватала● Фіском[8]. Розмальовку трьома кольорами можна знайти за лінійний час алгоритмом жадібного розмальовування, який видаляє будь-яку вершину зі степенем, що не перевищує двох, і розфарбовує решту графа рекурсивно, а потім повертає кожну з видалених вершин з кольором, відмінним від кольорів двох її сусідів.

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

Інші властивості

Зовніпланарні графи мають виродження●, яке не перевершує 2 — будь-який підграф зовніпланарного графа містить вершину зі степенем, що не перевершує 2[10].

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

Будь-який зовніпланарний граф можна подати у вигляді графа перетинів прямокутників із паралельними осям сторонами, так що зовніпланарні графи мають інтервальну розмірність[12][13] максимум два[14][15].

Пов'язані родини графів

Кактус. Кактуси утворюють підклас зовніпланарних графів.

Будь-який зовніпланарний граф є планарним. Будь-який зовніпланарний граф є підграфом паралельно-послідовного графа[16]. Однак не всі паралельно-послідовні графи зовніпланарні. Повний дводольний граф K2,3 є планарним і паралельно-послідовним, але не зовніпланарним. З іншого боку, повний граф K4 планарний, але ні паралельно-послідовний, ні зовніпланарний. Будь-який ліс і будь-який кактус зовніпланарні.

Слабко двоїстий планарний граф вкладеного зовніпланарного графа (граф, що має на вершині для кожної обмеженої грані вкладення і по ребру для суміжних обмежених граней) є лісом, а слабко двоїстий планарний граф графа Халіна є зовніпланарним графом. Планарний граф є зовніпланарним тоді й лише тоді, коли його слабко двоїстий граф є лісом, і граф є графом Халіна тоді й лише тоді, коли його слабко двоїстий граф є двозв'язним і зовніпланарним[17].

Існує поняття ступеня зовніпланарності. 1-зовніпланарне вкладення графа - це те ж саме, що зовніпланарне вкладення. Для k > 1 кажуть, що планарне вкладення є k-зовніпланарним, якщо видалення вершини з зовнішньої грані призводить до (k − 1)-зовніпланарного вкладення. Граф є k-зовніпланарним тоді й лише тоді, коли він має k-зовніпланарне вкладення[18][5].

Будь-який максимальний зовніпланарний граф є хордальним графом. Будь-який максимальний зовніпланарний граф є графом видимості простого багатокутника[19]. Максимальні зовніпланарні графи утворюються як графи тріангуляції багатокутників. Вони є також прикладами 2-дерев, паралельно-послідовних графів і хордальних графів.

Будь-який зовніпланарний граф є коловим графом, графом перетинів множини хорд кола[20][21].

Примітки

  1. ↑ а б Chartrand, Harary, 1967.
  2. ↑ Felsner, 2004.
  3. ↑ Помилка скрипту: Функції «harvard_core» не існує.; Помилка скрипту: Функції «harvard_core» не існує.; Помилка скрипту: Функції «harvard_core» не існує., Proposition 7.3.1, p. 117; Помилка скрипту: Функції «harvard_core» не існує..
  4. ↑ Diestel, 2000.
  5. ↑ а б в г Sysło, 1979.
  6. ↑ Li, Corneil, Mendelsohn, 2000, с. Proposition 2.5.
  7. ↑ а б 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. ↑ Sysło, Proskurowski, 1983.
  18. ↑ Kane, Basu, 1976.
  19. ↑ Помилка скрипту: Функції «harvard_core» не існує.; Помилка скрипту: Функції «harvard_core» не існує.; Помилка скрипту: Функції «harvard_core» не існує., Theorem 4.10.3, p. 65.
  20. ↑ Wessel, Pöschel, 1985.
  21. ↑ Unger, 1988.

Література

  • Ф.С.Робертс. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. — Москва : «Наука», 1986. — С. 129. — (Теория и методы системного анализа)
  • Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs // Journal of the ACM. — 1994. — Т. 41, вип. 1 (15 травня). — С. 153–180. — DOI:10.1145/174644.174650..
  • Luis Boza, Eugenio M. Fedriani, Juan Núñez. The problem of outer embeddings in pseudosurfaces // Ars Combinatoria[en]. — 2004. — Т. 71 (15 травня). — С. 79–91..
  • Luis Boza, Eugenio M. Fedriani, Juan Núñez. Obstruction sets for outer-bananas-surface graphs // Ars Combinatoria[en]. — 2004. — Т. 73 (15 травня). — С. 65–77..
  • Luis Boza, Eugenio M. Fedriani, Juan Núñez. Uncountable graphs with all their vertices in one face // Acta Mathematica Hungarica. — 2006. — Т. 112 (4) (15 травня). — С. 307–313. — DOI:10.1007/s10474-006-0082-0..
  • Luis Boza, Eugenio M. Fedriani, Juan Núñez. Outer-embeddability in certain pseudosurfaces arising from three spheres // Discrete Mathematics. — 2010. — Т. 310 (15 травня). — С. 3359–3367. — DOI:10.1016/j.disc.2010.07.027..
  • Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — Society for Industrial and Applied Mathematics, 1999. — (SIAM Monographs on Discrete Mathematics and Applications) — ISBN 0-89871-432-X..
  • Gary Chartrand, Frank Harary. Planar permutation graphs // Annales de l'Institut Henri Poincaré B. — 1967. — Т. 3, вип. 4 (15 травня). — С. 433–438..
  • Reinhard Diestel. Graph Theory. — Springer-Verlag, 2000. — Т. 173. — С. 107. — (Graduate Texts in Mathematics) — ISBN 0-387-98976-5..
  • H. El-Gindy. Hierarchical decomposition of polygons with applications. — McGill University, 1985. — (Ph.D. thesis). Как процитировано у Брандштедта, ли и Спинрада (Помилка скрипту: Функції «harvard_core» не існує.).
  • Stefan Felsner. Geometric graphs and arrangements: some chapters from combinational geometry. — Vieweg+Teubner Verlag, 2004. — С. 6. — ISBN 978-3-528-06972-8..
  • Stanley Fiorini. On the chromatic index of outerplanar graphs // Journal of Combinatorial Theory. — 1975. — Т. 18, вип. 1 (15 травня). — С. 35–38. — (Series B). — DOI:10.1016/0095-8956(75)90060-X..
  • Steve Fisk. A short proof of Chvátal's watchman theorem // Journal of Combinatorial Theory. — 1978. — Т. 24 (15 травня). — С. 374. — (Series B). — DOI:10.1016/0095-8956(78)90059-X..
  • Herbert J. Fleischner, D. P. Geller, Frank Harary. Outerplanar graphs and weak duals // Journal of the Indian Mathematical Society. — 1974. — Т. 38 (15 травня). — С. 215–219..
  • Vinay G. Kane, Sanat K. Basu. On the depth of a planar graph // Discrete Mathematics. — 1976. — Т. 14, вип. 1 (15 травня). — С. 63–67. — DOI:10.1016/0012-365X(76)90006-6..
  • Ming-Chu Li, Derek G. Corneil, Eric Mendelsohn. Pancyclicity and NP-completeness in planar graphs // Discrete Applied Mathematics. — 2000. — Т. 98, вип. 3 (15 травня). — С. 219–225. — DOI:10.1016/S0166-218X(99)00163-8..
  • Don R. Lick, Arthur T. White. k-degenerate graphs // Canadian Journal of Mathematics. — 1970. — Т. 22 (15 травня). — С. 1082–1096. — DOI:10.4153/CJM-1970-125-1..
  • Yaw-Ling Lin, Steven S. Skiena. Complexity aspects of visibility graphs // International Journal of Computational Geometry and Applications. — 1995. — Т. 5, вип. 3 (15 травня). — С. 289–312. — DOI:10.1142/S0218195995000179..
  • Andrzej Proskurowski, Maciej M. Sysło. Efficient vertex-and edge-coloring of outerplanar graphs // SIAM Journal on Algebraic and Discrete Methods. — 1986. — Т. 7 (15 травня). — С. 131–136. — DOI:10.1137/0607016..
  • E. R. Scheinerman. Intersection Classes and Multiple Intersection Parameters of a Graph. — Princeton University, 1984. — (Ph.D. thesis). As cited by Помилка скрипту: Функції «harvard_core» не існує..
  • Maciej M. Sysło. Characterizations of outerplanar graphs // Discrete Mathematics. — 1979. — Т. 26, вип. 1 (15 травня). — С. 47–53. — DOI:10.1016/0012-365X(79)90060-8..
  • Maciej M. Sysło, Andrzej Proskurowski. Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981. — Springer-Verlag, 1983. — Т. 1018. — С. 248–256. — (Lecture Notes in Mathematics) — DOI:10.1007/BFb0071635..
  • Walter Unger. Proc. 5th Symposium on Theoretical Aspects of Computer Science (STACS '88). — Springer-Verlag, 1988. — Т. 294. — С. 61–72. — (Lecture Notes in Computer Science) — DOI:10.1007/BFb0035832..
  • W. Wessel, R. Pöschel. Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984 / Horst Sachs. — B.G. Teubner, 1985. — Т. 73. — С. 207–210. — (Teubner-Texte zur Mathematik). Как процитировал Унгер (Помилка скрипту: Функції «harvard_core» не існує.).

Посилання

Отримано з https://uk.wikipedia.org/w/index.php?title=Зовніпланарний_граф&oldid=30128740