Номер очереди - Queue number

А граф де Брейна. С указанным порядком вершин разделение ребер на два подмножества, проходящих по левой и правой сторонам чертежа, представляет собой схему с двумя очередями этого графа.

В математике номер очереди из график это инвариант графа определяется аналогично номер стека (толщина книги) с использованием первым пришел-первым вышел (очередь) заказов вместо последний пришел - первый ушел (стековые) заказы.

Определение

Схема очереди данного графа определяется общий заказ из вершины графа вместе с разбиением края в ряд «очередей». Набор ребер в каждой очереди необходим, чтобы избежать должным образом вложенных ребер: если ab и CD два ребра в одной очереди, то не должно быть а < c < d < б в порядке вершин. Номер очереди qn (грамм) графа грамм - минимальное количество очередей в схеме очередей.^[1]

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

Макеты очередей были определены Хит и Розенберг (1992), по аналогии с предыдущей работой над книжные вложения графов, которые можно определить таким же образом, используя стеки вместо очередей. Как они заметили, эти макеты также связаны с более ранней работой по сортировке перестановки используя системы параллельных очередей, и может быть мотивировано приложениями в СБИС дизайн и управление коммуникациями для распределенные алгоритмы.^[1]

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

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

Двоичный графы де Брейна иметь очередь номер 2.^[7] В d-размерный граф гиперкуба имеет номер очереди не более ${ displaystyle d- lfloor log _ {2} d rfloor}$ .^[8] Номера очередей полные графики K_п и полные двудольные графы K_а,б точно известны: они ${ Displaystyle lfloor п / 2 rfloor}$ и ${ Displaystyle мин { lceil а / 2 rceil, lceil b / 2 rceil }}$ соответственно.^[9]

Каждый граф с 1 очередью является планарный граф, с «арочным выровненным» планарным вложением, в котором вершины размещаются на параллельных линиях (уровнях), и каждое ребро либо соединяет вершины на двух последовательных уровнях, либо образует арку, которая соединяет две вершины на одном уровне, обходя все предыдущие уровни. И наоборот, каждый арочный выровненный планарный граф имеет схему с одной очередью.^[10] В 1992 г. Хит, Лейтон и Розенберг (1992) предположил, что каждый планарный граф имеет ограниченное количество очереди. Эта гипотеза была положительно решена в 2019 г. Дуймович и др. (2019) который показал, что планарные графы и, в более общем смысле, каждый собственный минно-замкнутый класс графов имеет ограниченное число очереди.

Используя вариант номера очереди, называемый сильным номером очереди, номер очереди граф продукта может быть ограничена функцией номеров очередей и строгих номеров очередей факторов в продукте.^[11]

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

Графики с малым номером очереди разреженные графики: Графы с одной очередью п вершины имеют не более 2п - 3 ребра,^[12] и более общие графики с номером очередиq иметь самое большее 2qn − q(2q + 1) края.^[13] Это означает, что эти графы также имеют небольшие хроматическое число: в частности, графы с 1 очередью можно раскрашивать в 3 цвета, а графы с номером очереди q может понадобиться как минимум 2q + 1 и не более 4q цвета.^[13] С другой стороны, оценка количества ребер подразумевает гораздо более слабую оценку количества очереди: графы с п вершины и м ребра имеют номер очереди не более О(√м).^[14] Эта граница близка к точной, поскольку для случайных d-регулярных графов номер очереди, с большой вероятностью,

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

^[15]

Нерешенная проблема в математике:

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

(больше нерешенных задач по математике)

Графики с номером очереди 1 имеют толщину книги не более 2.^[16]Для любого фиксированного порядка вершин произведение толщины книги и номеров очередей для этого порядка не меньше, чем ширина разреза графика делится на его максимальную степень.^[16]Толщина книги может быть намного больше номера очереди: троичная Графы Хэмминга имеют логарифмический номер очереди, но полиномиально большую толщину книги.^[16] Остается неизвестным, может ли толщина книги быть ограничена какой-либо функцией номера очереди. Хит, Лейтон и Розенберг (1992) высказали предположение, что номер очереди является не более чем линейной функцией толщины книги, но функциональные границы в этом направлении также неизвестны. Известно, что если все двудольные графы с 3-страничными вложениями книг имеют ограниченное количество очереди, тогда все графы с ограниченной толщиной книги имеют ограниченное количество очереди.^[17]

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

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

это НП-полный чтобы определить номер очереди данного графа или даже проверить, равно ли это число единице.^[19]

Однако, если порядок вершин макета очереди задается как часть ввода, то оптимальное количество очередей для макета равно максимальному количеству ребер в макете. k-радуга, набор k ребра, каждые два из которых образуют вложенную пару. Разделение ребер на очереди можно выполнить, назначив ребро е это внешний край я-радуга (и радуги не больше) к я-я очередь. Есть возможность построить оптимальную планировку в срок О(м журнал журнал п), куда п обозначает количество вершин входного графа, а м обозначает количество ребер.^[20]

Графики ограниченного номера очереди также имеют ограниченное расширение, что означает, что их мелкие несовершеннолетние находятся разреженные графики с отношением ребер к вершинам (или эквивалентно вырождение или же родословие ), которая ограничена функцией номера очереди и глубины минора. Как следствие, несколько алгоритмических проблем, включая изоморфизм подграфов для графов шаблонов ограниченного размера имеют линейное время алгоритмы для этих графов.^[21] В целом, из-за их ограниченного расширения можно проверить, есть ли какое-либо предложение в логика первого порядка графиков действительна для данного графа с ограниченным номером очереди за линейное время.^[22]

Применение в графическом чертеже

Хотя макеты очередей не обязательно обеспечивают хорошее двухмерное графические рисунки, они были использованы для рисования трехмерных графиков. В частности, класс графа Икс имеет ограниченный номер очереди тогда и только тогда, когда для каждого п-вершинный граф грамм в Икс, можно разместить вершины грамм в трехмерной сетке размеров О(п) × О(1) × О(1) так, чтобы никакие два края (когда они нарисованы прямо) не пересекались.^[23] Так, например, графы де Брейна, графы с ограниченной древесной шириной, планарные графы и собственные семейства минорно-замкнутых графов имеют трехмерные вложения линейного объема.^[24] ^[25] ^[26].

Примечания

^ ^а ^б ^c Хит и Розенберг (1992).
^ Auer et al. (2011).
^ Хит и Розенберг (1992), Предложение 4.1.
^ Хит и Розенберг (1992), Предложения 4.2 и 4.3.
^ Хит, Лейтон и Розенберг (1992); Ренгараджан и Вени Мадхаван (1995).
^ Ренгараджан и Вени Мадхаван (1995).
^ Хит и Розенберг (1992), Предложение 4.6.
^ Грегор, Шкрековски и Вукашинович (2012)
^ Хит и Розенберг (1992), Предложения 4.7 и 4.8.
^ Хит и Розенберг (1992), Теорема 3.2.
^ Дерево (2005).
^ Хит и Розенберг (1992), Теорема 3.6
^ ^а ^б Дуймович и Вуд (2004).
^ Хит, Лейтон и Розенберг (1992). Алгоритм с полиномиальным временем для поиска макета с таким количеством очередей определяется выражением Шахрохи и Ши (2000). Дуймович и Вуд (2004) улучшил постоянный множитель в этой связи до е√м, куда е это основа натуральный логарифм.
^ Хит, Лейтон и Розенберг (1992); Дерево (2008).
^ ^а ^б ^c Хит, Лейтон и Розенберг (1992).
^ Дуймович и Вуд (2005).
^ Дуймович и Вуд (2003); Дуймович, Morin & Wood (2005). Видеть Дерево (2002) для более слабого предварительного результата, ограничивая номер очереди ширина пути или сочетанием ширины дерева и градуса.
^ Хит и Розенберг (1992), Следствие 3.9.
^ Хит и Розенберг (1992), Теорема 2.3.
^ Нешетржил, Оссона де Мендес и Вуд (2012); Нешетржил и Оссона де Мендес (2012) С. 321–327.
^ Нешетржил и Оссона де Мендес (2012), Теорема 18.2, с. 401.
^ Дерево (2002); Дуймович, Пор и Вуд (2004); Дуймович, Morin & Wood (2005). Видеть Ди Джакомо и Мейер (2004) для более жестких границ размеров сетки для графов с малым числом очередей.
^ Дуймович и Вуд (2003)
^ Дуймович, Morin & Wood (2005)
^ Дуймович и др. (2019)

внешняя ссылка

Макеты стека и очереди, Проблемы, представленные летом 2009 г., Исследования для аспирантов, Дуглас Б. Вест

[hr92-1] а ^б ^c Хит и Розенберг (1992).

[2] Auer et al. (2011).

[3] Хит и Розенберг (1992), Предложение 4.1.

[4] Хит и Розенберг (1992), Предложения 4.2 и 4.3.

[5] Хит, Лейтон и Розенберг (1992); Ренгараджан и Вени Мадхаван (1995).

[6] Ренгараджан и Вени Мадхаван (1995).

[7] Хит и Розенберг (1992), Предложение 4.6.

[8] Грегор, Шкрековски и Вукашинович (2012)

[9] Хит и Розенберг (1992), Предложения 4.7 и 4.8.

[10] Хит и Розенберг (1992), Теорема 3.2.

[11] Дерево (2005).

[12] Хит и Розенберг (1992), Теорема 3.6

[dw04-13] а ^б Дуймович и Вуд (2004).

[14] Хит, Лейтон и Розенберг (1992). Алгоритм с полиномиальным временем для поиска макета с таким количеством очередей определяется выражением Шахрохи и Ши (2000). Дуймович и Вуд (2004) улучшил постоянный множитель в этой связи до е√м, куда е это основа натуральный логарифм.

[15] Хит, Лейтон и Розенберг (1992); Дерево (2008).

[hlr92-16] а ^б ^c Хит, Лейтон и Розенберг (1992).

[dw05-17] Дуймович и Вуд (2005).

[18] Дуймович и Вуд (2003); Дуймович, Morin & Wood (2005). Видеть Дерево (2002) для более слабого предварительного результата, ограничивая номер очереди ширина пути или сочетанием ширины дерева и градуса.

[19] Хит и Розенберг (1992), Следствие 3.9.

[20] Хит и Розенберг (1992), Теорема 2.3.

[21] Нешетржил, Оссона де Мендес и Вуд (2012); Нешетржил и Оссона де Мендес (2012) С. 321–327.

[22] Нешетржил и Оссона де Мендес (2012), Теорема 18.2, с. 401.

[23] Дерево (2002); Дуймович, Пор и Вуд (2004); Дуймович, Morin & Wood (2005). Видеть Ди Джакомо и Мейер (2004) для более жестких границ размеров сетки для графов с малым числом очередей.

[24] Дуймович и Вуд (2003)

[25] Дуймович, Morin & Wood (2005)

[26] Дуймович и др. (2019)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]