Число черг графа

Граф де Брейна. Для наведеного впорядкування розподіл ребер на дві множини, що йдуть ліворуч і праворуч від вершин, є схемою 2 черг цього графа.

Число черг графа — це інваріант графа, визначений аналогічно стековому числу (товщині книги) і використовує впорядкування FIFO (перший увійшов, перший вийшов, черга) замість упорядкування LIFO (останнім увійшов, першим вийшов, стек).

Визначення

Подання заданого графа як черг (макет черг) визначається повним упорядкуванням вершин графа разом із розкладанням ребер графа на кілька «черг». Потрібно, щоби множини ребер кожної з черг не мали вкладеності за порядком вершин у тому сенсі, що якщо $ab$ і $cd$ — два ребра в одній черзі, то не повинно бути $a<c<d<b$. Число черг $qn(G)$ графа $G$ — це найменше число черг подання графа у вигляді чергШаблон:Sfn.

Використовуючи макет черг графа, можна перебрати ребра окремої черги, застосовуючи стандартну структуру черг шляхом перебору вершин у заданому порядку і коли досягаємо вершини, вибираємо всі ребра, для яких вершина є другою вершиною дуги і заносимо в чергу дуги, для яких вершина є першою. Умова відсутності вкладеності забезпечує, що з досягненням вершини все ребра, що мають цю вершину як кінцеву, перебувають у черзі і готові до вибирання. Розклад графа на черги з описаними властивостями можна вважати альтернативним визначеннямШаблон:Sfn. Інше еквівалентне визначення макета черг використовує поняття вкладення заданого графа в циліндр із вершинами, розташованими на прямій, що лежить на поверхні циліндра, а кожне ребро огинає циліндр. Ребра, включені в одну чергу, не повинні перетинатися, але перетини ребер різних черг дозволеноШаблон:Sfn.

Макет черг увели Гіт і РозенбергШаблон:Sfn за аналогією з попередньою роботою про книжкові вкладення графів, які визначаються в той самий спосіб з використанням стеків замість черг. Як вони зазначили, ці макети також пов'язані з ранніми роботами про сортування перестановок із використанням паралельних черг і до створення пов'язане з розробкою інтегральних схем та управлінням зв'язками в Шаблон:Не перекладеноШаблон:Sfn.

Класи графів з обмеженою кількістю черг

Будь-яке дерево має число черг, що дорівнює 1 з упорядкуванням вершин, заданим пошуком у ширинуШаблон:Sfn. У псевдолісів і решіток число черг також дорівнює 1Шаблон:Sfn. Число черг зовніпланарних графів не перевищує 2. Сонячний 3-граф (трикутник, кожне ребро якого замінено трикутником) є прикладом зовніпланарного графа, число черг якого дорівнює 2Шаблон:SfnШаблон:Sfn. Число черг паралельно-послідовного графа не перевищує 3Шаблон:Sfn.

Число черг двійкових графів де Брейна дорівнює 2Шаблон:Sfn. Число черг графа $d$-вимірного гіперкуба не перевищує $d-1$. Число черг повних графів $K_n$ і повних двочасткових графів $K_{a,b}$ відоме точно — воно одно $\lfloor n/2\rfloor$ і $\min \{\lceil a/2\rceil ,\lceil b/2\rceil \}$ відповідноШаблон:Sfn. Шаблон:Нерозв'язано Будь-який граф з однією чергою є планарним графом з «дуговим рівневим» планарним вкладенням, у якому вершини розташовуються на паралельних прямих (рівнях), а кожне ребро або з'єднує вершини двох сусідніх рівнів, або утворює дугу, що з'єднує дві вершини на тому самому рівні. І тому, будь-який дуговий рівневий планарний граф має макет з однією чергоюШаблон:Sfn. Гіт, Лейтон і РозенбергШаблон:Sfn припустили, що будь-який планарний граф має обмежену кількість черг, але підтвердження цього припущення поки що немає. Якщо число черг планарних графів обмежене, то це виконується і для 1-планарних графів і, більш того, для $k$-планарних графівШаблон:Sfn. Найсильніша межа, відома для числа черг планарних графів, не є сталою, вона дорівнює $O(\log n)$ Полілогарифмічні межі числа черг відомі для графів з обмеженим родом та загальніших графів із мінорно замкнутих сімействШаблон:Sfn.

Якщо використати варіант числа черг, званий «сильним числом черг», число черг добутку графів можна обмежити функцією від числа черг та сильного числа черг множників добуткуШаблон:Sfn.

Пов'язані інваріанти

Графи з малим числом черг є розрідженими — графи з $n$ вершинами, що мають одну чергу, мають не більше $2n-3$ реберШаблон:Sfn, а більш загального виду графи з числом черг $q$ мають не більше $2qn-q(2q+1)$ реберШаблон:Sfn. Звідси випливає, що ці графи мають мале хроматичне число. Зокрема графи з однією чергою мають розфарбування в 3 кольори, а графи з числом черг $q$ можуть вимагати не менше $2q+1$ і не більше $4q$ кольорівШаблон:Sfn. І навпаки, межа числа ребер тягне за собою нижчу межу числа черг графа — число черг графів з $n$ вершинами і $m$ ребрами не перевищує $O(\sqrt{m})$. Межа близька до строгої, оскільки для випадкових $d$-регулярних графів число черг із високою ймовірністю дорівнюєШаблон:SfnШаблон:Sfn

$\mathrm{\Omega }\left(\frac{\sqrt{dn}}{n^{1/d}}\right).$

Шаблон:Нерозв'язано Графи з однією чергою мають книжкову товщину, що не перевищує двохШаблон:Sfn. Для будь-якого фіксованого порядку вершин, добуток книжкової товщини та числа черг не менший від ширини перерізу графа, поділеного на максимальний степінь вершинШаблон:Sfn. Книжкова товщина може бути значно більшою за кількість черг — трійкові графи Геммінга мають логарифмічне число черг, але поліноміальну книжкову товщинуШаблон:Sfn. Залишається невідомим, чи обмежена книжкова товщина будь-якою функцією від кількості черг. Гіт, Лейтон і РозенбергШаблон:Sfn висловили припущення, що число черг не більше ніж лінійно залежить від книжкової товщини, але жодних досягнень у цьому напрямі немає. Відомо, що якщо всі двочасткові графи з 3-сторінковими книжковими вкладеннями мають обмежене число черг, то всі графи з обмеженою книжковою товщиною мають обмежене число чергШаблон:Sfn.

Генлі і ГітШаблон:Sfn поставили питання, чи обмежене число черг графа функцією від його деревної ширини, і цитували неопубліковану дисертацію С. В. Пеммараджу як свідчення заперечної відповіді — планарні 3-дерева, що з'являються в цьому контексті, мають необмежене число черг. Проте число черг, як було показано, обмежене (двічі експоненційною) функцією від деревної ширини.

Обчислювальна складність

Визначення числа черг графа є NP-повною задачею. NP-повною задачею є навіть перевірка, що число черг дорівнює одиниціШаблон:Sfn.

Однак, якщо порядок вершин попередньо задано, то оптимальне число черг дорівнює найбільшому числу ребер у $k$-веселці, множині з $k$ ребер, у кожній парі яких одне ребро вкладене в інше (в описаному вище сенсі). Поділ ребер на черги можна здійснити, включивши ребро $e$, яке є зовнішнім ребром $i$-веселки (але не більшої веселки) в $i$-ту чергу. Оптимальний макет можна побудувати за час $O(m\log \log n)$, де $n$ — число вершин графа, а $m$ — число реберШаблон:Sfn.

Графи з обмеженим числом черг мають також обмежене розширення, що означає, що їх неглибокі мінори є розрідженими графами з відношенням ребер до вершин (або, еквівалентно, виродженістю або деревністю), обмеженим функцією від числа черг і глибини мінора. Як наслідок, деякі алгоритмічні задачі, включно із задачею ізоморфізму графів для графів обмеженого розміру, мають алгоритми лінійного часу виконання для таких графівШаблон:SfnШаблон:Sfn. Загальніше, з огляду на обмежене розширення можна перевірити за лінійний час, чи є істинним твердження логіки першого порядку для графа з обмеженим числом чергШаблон:Sfn.

Застосування у візуалізації графів

Хоча макети черг не обов'язково дають хороші двовимірні візуалізації, їх використовують для тривимірного подання графів. Зокрема, граф $G$ має обмежене число черг тоді й лише тоді, коли його вершини можна розташувати на тривимірній решітці розміром $O(n)\times O(1)\times O(1)$ так, що жодні два ребра не перетинаються. Наприклад, графи де Брейна та графи з обмеженою деревною шириною мають тривимірне вкладення лінійного об'ємуШаблон:SfnШаблон:Sfn.

Логарифмічні або полілогарифмічні межі числа черг перетворюються при подібних вкладеннях у тривимірні решітки в майже лінійні об'єми, решітка в одному напрямку матиме лінійний розмір, а в двох інших — полілогарифмічний. Планарні графи, графи з обмеженим родом і графи з обмеженою локальною деревною шириною мають вкладення об'єму $O(n\log n)$, тоді як графи замкнутих за мінорами сімейств мають об'єм $O(n{\log }^{O(1)}n)$Шаблон:Sfn.

Література

• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття.
• Шаблон:Стаття.
• Шаблон:Книга.
• Шаблон:Стаття.
• Шаблон:Книга.
• Шаблон:Стаття.
• Шаблон:Стаття.
• Шаблон:Стаття.
• Шаблон:Стаття.
• Шаблон:Стаття.
• Шаблон:Стаття.
• Шаблон:Стаття.
• Шаблон:Книга.
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга.
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття.
• Шаблон:СтаттяШаблон:Недоступне посилання.

Посилання

• Problem 52: Queue-Number of Planar Graphs, The Open Problems Project
• Stack and Queue Layouts — проблеми, представлені влітку 2009, Research Experiences for Graduate Students, Douglas B. West