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

10.04.2021

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

Определение

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

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

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

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

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

Число очередей бинарных графов де Брёйна равно 2. Число очередей графа d-мерного гиперкуба не превосходит d − 1 . Число очередей полных графов Kn и полных двудольных графов Ka,b известно точно — оно равно ⌊ n / 2 ⌋ {displaystyle lfloor n/2 floor } и min { ⌈ a / 2 ⌉ , ⌈ b / 2 ⌉ } {displaystyle min{lceil a/2 ceil ,lceil b/2 ceil }} соответственно.

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

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

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

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

Ω ( d n n 1 / d ) . {displaystyle Omega left({frac {sqrt {dn}}{n^{1/d}}} ight).}

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

Генли и Хит задали вопрос, ограничено ли число очередей графа функцией от его древесной ширины, и цитировали неопубликованную диссертацию С. В. Пеммараджу в качестве свидетельства отрицательного ответа — планарные 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 logO(1) n).



Имя:*
E-Mail:
Комментарий: