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

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

Представление графа в виде очередей (макет очередей) для заданного графа определяется полным упорядочением вершин графа вместе с разложением рёбер графа на несколько «очередей». Требуется, чтобы множество рёбер каждой очереди не имели вложенности по порядку вершин в том смысле, что если ab и cd являются двумя рёбрами в одной очереди, то не должно быть a < c < d < b. Число очередей qn(G) графа G — это минимальное число очередей представления графа в виде очередей^[1].

Используя макет очередей графа, можно перебрать рёбра отдельной очереди, используя стандартную структуру очередей путём перебора вершин в заданном порядке и, когда достигаем вершины, выбираем все рёбра, для которых вершина является второй вершиной дуги и заносим в очередь дуги, для которых вершина является первой. Условие отсутствие вложенности обеспечивает, что при достижении вершины все рёбра, имеющие эту вершину в качестве конечной, находятся в очереди и готовы к выборке. Разложение графа на очереди с описанными свойствами можно считать альтернативным определением^[1]. Другое эквивалентное определение макета очередей использует понятие вложения заданного графа в цилиндр с вершинами, расположенными на прямой, находящейся на поверхности цилиндра, а каждое ребро огибает цилиндр. Рёбра, включённые в одну очередь, не должны пересекаться, но пересечения рёбер различных очередей разрешены^[2].

Макет очередей был определён Хитом и Розенбергом^[1] по аналогии с предыдущей работой о книжных вложениях графах, которые определяются тем же способом с использованием стэков вместо очередей. Как они отметили, эти макеты также связаны с более ранними работами о сортировке перестановок с использованием параллельных очередей. Макет очередей был мотивирован требованиям разработки интегральных схем и управления связей в распределённых алгоритмах^{[англ.][1]}.

Любое дерево имеет число очередей, равное 1 с упорядочением вершин, заданным поиском в ширину^[3]. У псевдолесов и решёток число очередей также равно 1^[4]. Число очередей внешнепланарных графов не превосходит 2. Солнечный 3-граф (треугольник, каждое ребро которого заменено треугольником) является примером внешнепланарного графа, число очередей которого равно в точности 2^[5][6]. Число очередей параллельно-последовательного графа не превосходит 3^[6].

Число очередей бинарных графов де Брёйна равно 2^[7]. Число очередей графа d-мерного гиперкуба не превосходит d − 1 ^[8]. Число очередей полных графов K_n и полных двудольных графов K_a,b известно точно — оно равно ${\displaystyle \lfloor n/2\rfloor }$ и ${\displaystyle \min\{\lceil a/2\rceil ,\lceil b/2\rceil \}}$ соответственно^[9].

Нерешённые проблемы математики: Имеет ли все планарные графы ограниченное число очередей?

Любой граф с одной очередью является планарным графом с «дуговым уровневым» планарным вложением, в котором вершины располагаются на параллельных прямых (уровнях), а каждое ребро либо соединяет вершины двух соседних уровней, либо образует дугу, соединяющую две вершины на том же самом уровне. И обратно, любой дуговой уровневый планарный граф имеет макет с одной очередью^[10]. Хит, Лейтон и Розенберг^[5] высказали предположение, что любой планарный граф имеет ограниченное число очередей, но подтверждения этому высказыванию пока нет. Если число очередей планарных графов ограничено, то же самое верно и для 1-планарных графов и, более того, для k-планарных графов^[11]. Наиболее сильная граница, известная для числа очередей планарных графов, не является константой, она равна O(log n) ^[12] Полилогарифмические границы числа очередей известны для графов с ограниченным родом и более общими графами из минорно замкнутых семейств^[13].

Если использовать вариант числа очередей, называемый «сильным числом очередей», число очередей произведения графов можно ограничить функцией от числа очередей и строгого числа очередей множителей произведения^[14].

Графы с малым числом очередей являются разреженными — графы с n вершинами, имеющие одну очередь, имеют не более 2n − 3 рёбер^[15], а более общего вида графы с числом очередей q имеют не более 2qn − q(2q + 1) рёбер^[16]. Отсюда следует, что эти графы имеют малое хроматическое число. В частности графы с одной очередью имеют раскраску в 3 цвета, а графы с числом очередей q могут потребовать не менее 2q + 1 и не более 4q цветов^[16]. В обратную сторону, граница числа рёбер влечёт за собой более низкую границу числа очередей графа — число очередей графов с n вершинами и m рёбрами не превосходит O(√m) ^[17]. Граница близка к строгой, поскольку для случайных d-регулярных графов число очередей с высокой вероятностью равно^[5][18]

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

Нерешённые проблемы математики: Должен ли любой граф с ограниченным числом очередей иметь ограниченную книжную толщину и наоборот?

Графы с одной очередью имеют книжную толщину, не превышающую двух^[5]. Для любого фиксированного порядка вершин, произведение толщины книги и числа очередей для этого порядка вершин не менее ширины сечения графа, делённого на максимальную степень вершин^[5]. Толщина книги может быть много больше числа очередей — троичные графы Хэмминга имеют логарифмическое число очередей, но полиномиальную толщину книг^[5]. Остаётся неизвестным, ограничена ли книжная толщина какой-либо функцией от числа очередей. Хит, Лейтон и Розенберг^[5] высказали предположение, что число очередей не более чем линейно зависит от толщины книг, но никаких достижений в этом направлении нет. Известно, что если все двудольные графы с 3-страничными книжными вложениями имеют ограниченное число очередей, то все графы с ограниченной книжной толщиной имеют ограниченное число очередей^[11].

Генли и Хит^[19] задали вопрос, ограничено ли число очередей графа функцией от его древесной ширины, и цитировали неопубликованную диссертацию С. В. Пеммараджу в качестве свидетельства отрицательного ответа — планарные 3-деревья^[англ.], появляющиеся в этом контексте, имеют неограниченное число очередей. Однако число очередей, как было показано, ограничено (дважды экспоненциальной) функцией от древесной ширины^[20]

Определение числа очередей графа является NP-полной задачей. NP-полной задачей является даже проверка, что число очередей равно единице^[21].

Однако, если порядок вершин предварительно задан, то оптимальное число очередей равно максимальному числу рёбер в k-радуге, множестве из k рёбер, в каждой паре которых одно ребро вложено в другое (в описанном выше смысле). Разделение рёбер на очереди может быть осуществлено путём включения ребра e, являющегося внешним ребром i-радуги (но не большей радуги) в i-ю очередь. Можно построить оптимальный макет за время O(m log log n), где n означает число вершин графа, а m — число рёбер^[22].

Графы с ограниченным числом очередей имеют также ограниченное расширение, что означает, что их неглубокие миноры являются разреженными графами с отношением рёбер к вершинам (или, эквивалентно, вырожденностью или древесностью), ограниченным функцией от числа очередей и глубины минора. Как следствие, некоторые алгоритмические задачи, включая задачу изоморфизма графов для графов ограниченного размера, имеют алгоритмы линейного времени исполнения для таких графов^[23][24]. Более обще, ввиду ограниченного расширения можно проверить за линейное время, является ли верным утверждение логики первого порядка для графа с ограниченным числом очередей^[25].

Хотя макеты очередей не обязательно дают хорошие двумерные визуализации, они используются для трёхмерного представления графов. В частности, граф G имеет ограниченное число очередей тогда и только тогда, когда можно расположить вершины графа G на трёхмерной решётке размером O(n) × O(1) × O(1) таким образом, что никакие два ребра не пересекаются^[26] Например, графы де Брёйна и графы с ограниченной древесной шириной имеют трёхмерное вложение линейного объёма^[27][28].

Логарифмические или полилогарифмические границы числа очередей преобразуются при подобных вложениях в трёхмерные решётки в почти линейные объёмы, решётка в одном направлении будет иметь линейный размер, а в двух других — полилогарифмический. Планарные графы, графы с ограниченным родом и графы с ограниченной локальной древесной шириной имеют вложения объёма O(n log n) ^[12], в то время как графы замкнутых по минорам семейств имеют объём O(n log^O(1) n)^[13].

• Problem 52: Queue-Number of Planar Graphs, The Open Problems Project
• Stack and Queue Layouts, Problems presented in Summer 2009, Research Experiences for Graduate Students, Douglas B. West