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

Определение

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

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

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

Классы графов с ограниченным числом очередей

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

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

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

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

Связанные инварианты

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

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

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

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

Вычислительная сложность

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

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

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

Приложение в визуализации графов

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

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

Примечания

Литература

Ссылки

• , The Open Problems Project
• , Problems presented in Summer 2009, Research Experiences for Graduate Students, Douglas B. West