Вікіпедія

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

граф, що допускає планарну діаграму, в якій усі вершини належать зовнішній грані
(Перенаправлено з Зовнішньопланарний граф)

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

Максимальний зовніпланарний граф і його 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. ↑ Chartrand, Harary, (1967); Sysło, (1979); Brandstädt, Le, Spinrad, (1999), Proposition 7.3.1, p. 117; Felsner, (2004).
  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. ↑ El-Gindy, (1985); Lin, Skiena, (1995); Brandstädt, Le, Spinrad, (1999), Theorem 4.10.3, p. 65.
  20. ↑ Wessel, Pöschel, 1985.
  21. ↑ Unger, 1988.

Література ред.

Посилання ред.

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