Русская Википедия:Число очередей графа

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:DeBruijn-3-2.svg
Граф де Брёйна. Для приведённого упорядочения деление рёбер на два множества, идущих слева и справа от вершин, является схемой 2 очередей этого графа.

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

Определение

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

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

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

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

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

Число очередей бинарных графов де Брёйна равно 2Шаблон:Sfn. Число очередей графа d-мерного гиперкуба не превосходит Шаблон:Nowrap [1]. Число очередей полных графов Kn и полных двудольных графов Ka,b известно точно — оно равно <math>\lfloor n/2\rfloor</math> и <math>\min\{\lceil a/2\rceil,\lceil b/2\rceil\}</math> соответственноШаблон:Sfn.

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

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

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

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

<math>\Omega\left(\frac{\sqrt{dn}}{n^{1/d}}\right).</math>

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

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

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

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

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

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

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

Хотя макеты очередей не обязательно дают хорошие двумерные визуализации, они используются для трёхмерного представления графов. В частности, граф G имеет ограниченное число очередей тогда и только тогда, когда можно расположить вершины графа G на трёхмерной решётке размером Шаблон:Nowrap таким образом, что никакие два ребра не пересекаются[5] Например, графы де Брёйна и графы с ограниченной древесной шириной имеют трёхмерное вложение линейного объёмаШаблон:SfnШаблон:Sfn.

Логарифмические или полилогарифмические границы числа очередей преобразуются при подобных вложениях в трёхмерные решётки в почти линейные объёмы, решётка в одном направлении будет иметь линейный размер, а в двух других — полилогарифмический. Планарные графы, графы с ограниченным родом и графы с ограниченной локальной древесной шириной имеют вложения объёма Шаблон:Nowrap, в то время как графы замкнутых по минорам семейств имеют объём Шаблон:NowrapШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Harvnb, Proposition 4.10; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb.
  2. ↑ Дуймович Шаблон:Harv, улучшение более ранней границы Ди Батисты, Фрати и Паха Шаблон:Harv.
  3. ↑ Шаблон:Harvnb. Алгоритм полиномиального времени для поиска макета с близким этому числом очередей дали Шароки и Ши Шаблон:Harv. Дуймович и Вуд Шаблон:Harv улучшил константу в этой границе до e√m, где e — основание натурального логарифма.
  4. ↑ Шаблон:Harvnb; Шаблон:Harvnb. См. статью Вуда Шаблон:Harv о более слабом предварительном результате, ограничивающем число очередей путевой шириной или комбинацией древесной ширины и степени графа.
  5. ↑ Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb. См. Шаблон:Harvnb for tighter bounds on the grid dimensions for graphs of small queue number.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Число_очередей_графа&oldid=11339914