Зовніпланарний граф

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Максимальний зовніпланарний граф і його 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. Архівовано з джерела 20 січня 2022. Процитовано 25 листопада 2020..
  • 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. Архівовано з джерела 23 липня 2012. Процитовано 25 листопада 2020..
  • 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=39083865