Книжкове вкладення в теорії графів — узагальнення планарного вкладення графа до вкладення в книжку — набір напівплощин, які мають межею одну й ту саму пряму. Зазвичай потрібно, щоб вершини графа лежали на цій межі, а ребра мають міститися всередині однієї сторінки. Книжкова товщина (або кількість сторінок) графа — найменша кількість напівплощин серед усіх книжкових вкладень графа. Книжкове вкладення використовують для деяких інших інваріантів графа, серед яких ширина сторінки та книжкове число схрещень.
Будь-який граф з вершинами має книжкову товщину не більше . Ця межа близька до повних графів. Однак поділ кожного ребра може зменшти книжкову товщину до величини, пропорційної кореню квадратному з . Графи з книжковою товщиною один є зовніпланарними графами, а графи з книжковою товщиною не більше двох є підгамільтоновими, які завжди планарні. Будь-який планарний граф має книжкову товщину, що не перевищує чотирьох. Всі мінорно замкнуті сімейства графів, і, зокрема, графи з обмеженою деревною шириною або обмеженим родом, також мають обмежену книжкову товщину. Визначення точної книжкової товщини заданого графа є NP-складною задачею, незалежно від того, чи відомий порядок вершин на корінці.
Одним із початкових приводів вивчення книжкового вкладення було його застосування в розробці НВІС, де вершини книжкового вкладення представляють компоненти, а ребра — з'єднання між ними.. При візуалізації графів за допомогою книжкового вкладення можна побудувати два стандартні стилі подання графів: дугові діаграми та колові розташування ,. Різні початкові та кінцеві точки руху пішоходів і машин, що регульованого світлофором, можна математично змоделювати як вершини графа, а ребра будуть представляти пари початок-кінець, книжкове ж вкладення цього графа можна використати для розробки режиму роботи світлофора, щоб забезпечити регулювання руху з найменшим числом станів світлофора. У задачах біоінформатики, що працюють зі структурами РНК, односторінкове книжкове вкладення представляє класичну форму , а двосторінкове вкладення представляє псевдовузли. Книжкове вкладення використовують також у загальній алгебрі та теорії вузлів.
Відкритими проблемами, що стосуються книжкового вкладення, є
Чи обмежена книжкова товщина довільного графа функцією його підрозбиттів? Чи достатньо знати порядок вершин на корінці, щоб перевірити, чи граф має тристорінкове вкладення?. Чи існує планарний граф, книжкова товщина якого дорівнює чотирьом? Скільки перетинів на корінці необхідно для тристорінкового топологічного вкладення (у цьому випадку ребра можуть переходити зі сторінки на сторінку через корінець) довільного графа?
Історія Назву «книга» ввели Персінгер і Атнеосен (C. A. Persinger, Gail Atneosen) у 1960-ті роки.. Атнеосен вже використовував вкладення графів у книги, але формально концепцію книжкового вкладення сформулювали Кайнен та Оллман (C. Kainen, L. Taylor Ollman) на початку 1970-х і додали деякі обмеження на спосіб вкладення — в їхньому формулюванні вершини графа мають лежати на корінці книги, кожне ребро має лежати на одній сторінці (не перетинати корінець) і будь-які два ребра перетинаються тільки в спільних кінцевих вершинах...
Важливими віхами в подальшому розвитку книжкового вкладення є доведення Міхаліса Яннакакіса наприкінці 1980-х, що книжкова товщина планарних графів не перевищує чотирьох, і відкриття наприкінці 1990-х тісного зв'язку між книжковим вкладенням та біоінформатикою.
Визначення Книга є частковим випадком топологічного простору (називана також віялом півплощин).. Він складається з однієї прямої ℓ, званої корінцемВ оригіналі — spine або back книги, разом з набором з однієї або більше півплощин, званих сторінками або аркушами книги. Кожна півплощина повинна мати межею ту саму пряму ℓ. Книги зі скінченним числом () сторінок можна вкласти в тривимірний простір, наприклад, за допомогою вибору як прямої ℓ осі прямокутної системи координат, а як -ту сторінку (з ) можна взяти множину точок , таких що найкоротший відрізок, що з'єднує з віссю утворює з площиною кут .
Візуалізація книги скінченного графа у книгу — це малюнок графа у , такий що будь-яка вершина графа малюється на корінці , а будь-яке ребро малюється як крива, що лежить усередині однієї сторінки . -сторінкове книжкове число перетинів графа — це найменше число перетинів у малюнку на -сторінковій книзі.
Книжкове вкладення графа у — це вкладення графа у простір . Тобто це малюнок графа в , при якому ребра не перетинаються. Будь-який скінченний граф має книжкове вкладення в книгу з достатнім числом сторінок. Наприклад, завжди є можливість вкласти кожне ребро на свою сторінку. Товщина книги, число сторінок, або стекове число графа — це найменша кількість сторінок, потрібна для книжкового вкладення графа . Інший параметр, який вимірює якість книжкового вкладення, крім кількості сторінок, — це ширина сторінки — найбільше число ребер всередині окремої сторінки, які перетинає промінь, перпендикулярний до корінця. Еквівалентно (для книжкових вкладень, у яких кожне ребро намальоване як монотонна крива), це найбільший розмір підмножини ребер, таких що інтервали, визначені на корінці кінцевими точками ребер, всі перетинаються...
Істотно для цих визначень, що ребра можуть лежати лише на одній сторінці. Як зазначив Амеозен, якщо ребра можуть переходити зі сторінки на сторінку (через корінець), то будь-який граф можна вкласти в тристорінкову книгу. Однак для тристорінкового топологічного книжкового вкладення, в якому перетин корінця дозволено, залишається цікавою задача визначення найменшої кількості перетинів корінця, що дозволяє вкласти граф у книгу..
Конкретні графи Як показано на першому малюнку, книжкова товщина повного графа дорівнює трьом. Оскільки він не планарний, його книжкова товщина більше двох, але існує книжкове вкладення з трьома сторінками. Книжкова товщина будь-якого повного графа з вершинами дорівнює рівно . Цей результат дає верхню межу найбільшої книжкової товщини будь-яких графів вершинами. Двосторінкова кількість перетинів повного графа дорівнює
що відповідає недоведеній гіпотезі . Тобто, якщо гіпотеза Гілла істинна, то малюнком цього графа, що мінімізує число перетинів, є двосторінковий малюнок.
Товщина книги повного двочасткового графа майже дорівнює — для кожної вершини меншої частки можна розташувати ребра, інцидентні цим вершинам, на власній сторінці. Ця межа не завжди строга. Наприклад, має товщину книги три, а не чотири. Однак, коли дві сторони графа дуже розбалансовані, , товщина книги дорівнює рівно .Більше результатів щодо книжкової товщини повних двочасткових графів див. . Товщина книг двійкових графів де Брейна, графів тасованого обміну, і (коли ці графи досить великі, щоб не бути планарними) дорівнює рівно трьом Див. також ..
Властивості
Поведінка під час підрозбиттів
Розбиття кожного ребра графа на двореберні шляхи додаванням нових вершин для кожного ребра може іноді збільшити книжкову товщину (наприклад, алмаз має книжкову товщину один, але його підрозбиття має книжкову товщину два). Однак таке підрозбиття може істотно зменшити книжкову товщину графа після розбиття. Наприклад, книжкова товщина повного графа пропорційна числу його вершин, але розбиття кожного ребра на два дає підрозбиття зі значно меншою книжковою товщиною, лише . Попри існування прикладів, подібних до наведеного вище, Бланкеншип і Опоровські висловили гіпотезу, що книжкова товщина підрозбиттів не може бути істотно меншою, ніж у початкового графа. Зокрема, вони припустили, що існує певна функція , що для будь-якого графа і графа , отриманого заміною кожного ребра шляхом із двох ребер, якщо книжкова товщина графа дорівнює , то книжкова товщина графа не перевищує . До 2013 року гіпотеза Бланкеншипа — Опоровські залишалася недоведеною.
Планарність та зовнішня планарність
Книжкова товщина даного графа не перевищує 1 тоді й лише тоді, коли зовніпланарний. Зовніпланарний граф — це граф, що має планарне вкладення, в якому всі вершини належать до зовнішньої грані вкладення. Для таких графів розташування вершин уздовж корінця в тому ж порядку, в якому вони з'являються на зовнішній грані (за повторної появи вершини на зовнішній грані береться лише одна копія вершини) дає односторінкове вкладення графа. І навпаки, односторінкове книжкове вкладення є автоматично зовніпланарним — якщо граф вкладено в одну сторінку, приєднання другої півплощини дає повну площину, а зовнішня грань міститиме всю додану півплощину, при цьому всі вершини лежатимуть на цій зовнішній грані.
Будь-яке книжкове вкладення з двома сторінками є окремим випадком планарного вкладення, оскільки об'єднання двох сторінок є простором, топологічно еквівалентним площині. Таким чином, будь-який граф із книжковою товщиною два автоматично є планарним. Точніше, книжкова товщина графа не більше двох тоді й лише тоді, коли є підграфом планарного графа, який має гамільтонів цикл. Якщо дано граф із книжковим вкладенням у дві сторінки, граф можна розширити до планарного гамільтонового графа, додавши (на будь-якій сторінці) ребера між будь-якими двома послідовними вершинами вздовж корінця, якщо вони ще не з'єднані ребром, а також між першою та останньою вершиною корінця. Граф Голднера — Харарі є прикладом планарного графа, який має книжкову товщину два — це максимальний планарний граф, отже, неможливо додати жодного ребра, зберігаючи планарність, і граф не має гамільтонового циклу. Зважаючи на вимогу наявності гамільтонових циклів, графи, що дозволяють двосторінкове вкладення, відомі як підгамільтонові графи.
Всі планарні графи з найбільшим степенем, що не перевищує чотирьох, мають товщину книжкового вкладення, що не перевищує двох. Планарні 3-дерева мають найбільшу товщину книги, рівну трьом. Усі планарні графи мають книжкову товщину, що не перевищує чотирьох. Як стверджував Міхаліс Яннакакіс 1986 року, існують планарні графи з товщиною книжкового вкладення, точно рівною чотирьом, проте детальне доведення цього твердження, анонсоване в статті, так і не було опубліковане. Тому Дуймович позначив задачу визначення найбільшої товщини книжкового вкладення планарних графів як нерозв'язану.
Зв'язок із іншими інваріантами графів Книжкова товщина пов'язана з товщиною графа, числом планарних графів, необхідних для покриття ребер заданого графа. Граф має товщину θ, якщо його можна вкласти в площину, і при цьому ребра можна розфарбувати в θ кольорів так, що ребра одного кольору не перетинаються. Аналогічно граф має книжкову товщину θ, якщо його можна намалювати в півплощині з вершинами на межі півплощини та розфарбувати ребра в θ кольорів без перетинів ребер одного кольору. За такого формулювання ребра одного кольору відповідають сторінкам книжкового вкладення. Однак товщина графа і книжкова товщина можуть істотно відрізнятися — існують підрозділи повних графів, що мають необмежену книжкову товщину, попри те, що товщина графа дорівнює двом.
Графи з деревною шириною мають книжкову товщину, яка не перевищує . і ця межа досягається для . Графи з ребрами мають книжкову товщину , а графи з родом — книжкову товщину .. Загальніше, будь-яке мінорно-замкнуте сімейство графів має обмежену книжкову товщину. Як процитовано в Нешетрі..
Будь-який стягувальний мінор графа обмеженої книжкової товщини є розрідженим графом, у якого відношення числа ребер до числа вершин обмежене сталою, яка залежить лише від глибини мінору та книжкової товщини. Тобто, в термінології Нешетрила, графи з обмеженою книжковою товщиною мають обмежений зріст. Однак навіть графи з обмеженим степенем графа (істотно сильніша вимога обмеження зросту) можуть мати необмежену книжкову товщину..
Оскільки графи з книжковою товщиною два є планарними графами, вони задовольняють теоремі про планарне розбиття — вони мають сепаратори, підмножини вершин, видалення яких ділить граф на частини з максимум вершинами в кожній частині, тільки з вершинами в сепараторі, де — кількість вершин графа. Однак існують графи з книжковою товщиною три, що не мають сепараторів сублінійного розміру, покращення ранішого результату ;