Номер очереди

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

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

Определение

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

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

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

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

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

Двоичные графы де Брёйна имеют очередь номер 2. ^[8] Граф d -мерного гиперкуба имеет номер очереди не более $d-\lfloor \log _{2}d\rfloor$ . ^[9] Номера очередей полных графов K _n и полных двудольных графов K _{a , b} известны точно: они равны $\lfloor n/2\rfloor$ и $\min\{\lceil a/2\rceil ,\lceil b/2\rceil \}$ соответственно. ^[10]

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

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

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

Графы с малым числом очередей являются разреженными графами : графы с 1 очередью и $n$ вершинами имеют не более $2 n - 3$ ребер, ^[13] и, в более общем смысле, графы с номером очереди $q$ имеют не более $2 qn - q (2 q + 1)$ ребер. ^[14] Это означает, что эти графы также имеют небольшое хроматическое число : в частности, графы с 1 очередью раскрашиваются в 3 цвета, а графам с номером очереди $q$ может потребоваться как минимум $2 q + 1$ и не более $4 q$ цветов. ^[14] С другой стороны, ограничение на количество ребер подразумевает гораздо более слабое ограничение на количество очередей: графы с $n$ вершинами и $m$ ребрами имеют не более ⁠ числа очередей. $O({\sqrt {m}})$ ⁠ . ^[15] Эта оценка близка к точной, поскольку для случайных $d$ -регулярных графов номер очереди с высокой вероятностью равен

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

^[16]

Нерешенная задача по математике :

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

(еще нерешенные задачи по математике)

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

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

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

NP -полно определить номер очереди данного графа или даже проверить, равно ли это число 1. ^[21]

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

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

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

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

Примечания

^ Jump up to: ^а ^б ^с Хит и Розенберг (1992) .
^ Ауэр и др. (2011) .
^ Хит и Розенберг (1992) , Предложение 4.1.
^ Хит и Розенберг (1992) , предложения 4.2 и 4.3.
^ Хит, Лейтон и Розенберг (1992) ; Ренгараджан и Вени Мадхаван (1995) .
^ Ренгараджан и Вени Мадхаван (1995) .
^ Алам и др. (2020) .
^ Хит и Розенберг (1992) , Предложение 4.6.
^ Грегор, Шкрековски и Вукашинович (2012)
^ Хит и Розенберг (1992) , предложения 4.7 и 4.8.
^ Хит и Розенберг (1992) , Теорема 3.2.
^ Вуд (2005) .
^ Хит и Розенберг (1992) , Теорема 3.6.
^ Jump up to: ^а ^б Дуймович и Вуд (2004) .
^ Хит, Лейтон и Розенберг (1992) . Алгоритм с полиномиальным временем для поиска макета с таким количеством очередей предложен Шахрохи и Ши (2000) . Дуймович и Вуд (2004) улучшили постоянный коэффициент в этой связи до ⁠ $e{\sqrt {m}}$ ⁠ , где $e$ — основание натурального логарифма .
^ Хит, Лейтон и Розенберг (1992) ; Вуд (2008) .
^ Jump up to: ^а ^б Дуймович и др. (2022)
^ Jump up to: ^а ^б Хит, Лейтон и Розенберг (1992) .
^ Дуймович и Вуд (2005) .
^ Дуймович и Вуд (2003) ; Дуймович, Морен и Вуд (2005) . См. Wood (2002) для более слабого предварительного результата, ограничивающего номер очереди шириной пути или комбинацией ширины дерева и степени.
^ Хит и Розенберг (1992) , Следствие 3.9.
^ Хит и Розенберг (1992) , Теорема 2.3.
^ Он не пощадил, Оссона де Мендес и Вуд (2012) ; Нешетрил и Оссона де Мендес (2012) , стр. 321–327.
^ Нешетрил и Оссона де Мендес (2012) , Теорема 18.2, стр. 401.
^ Вуд (2002) ; Дуймович, Пор и Вуд (2004) ; Дуймович, Морен и Вуд (2005) . См. Di Giacomo & Meijer (2004) для более точных ограничений размеров сетки для графов с небольшим количеством очередей.
^ Дуймович и Вуд (2003)
^ Дуймович, Морен и Вуд (2005)
^ Дуймович и др. (2020)

Ссылки

Ауэр, Кристофер; Бахмайер, Кристиан; Бранденбург, Франц Иосиф; Бруннер, Вольфганг; Гляйснер, Андреас (2011), «Плоские чертежи графов очередей и деков», Рисование графиков: 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21–24 сентября 2010 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 6502, Гейдельберг: Springer, стр. 68–79, номер документа : 10.1007/978-3-642-18469-7_7 , ISBN. 978-3-642-18468-0 , МР 2781254 .
Алам, Джавахерул, Мэриленд; Бекос, Майкл А.; Гронеманн, Мартин; Кауфманн, Майкл; Пупырев, Сергей (2020), «Схемы очередей плоских 3-деревьев», Algorithmica , 9 (82): 2564–2585, arXiv : 1808.10841 , doi : 10.1007/s00453-020-00697-4 , S2CID 52143414 .
Бекос, Майкл А.; Гронеманн, Мартин; Рафтопулу, Хрисанти Н. (2021), «О количестве очередей планарных графов», Рисование графиков: 29-й Международный симпозиум, GD 2021, Тюбинген, Германия, 14–17 сентября 2021 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, Гейдельберг: Спрингер .
Ди Баттиста, Джузеппе; Фрати, Фабрицио; Пах, Янош (2013), «О количестве очередей плоских графов» (PDF) , SIAM Journal on Computing , 42 (6): 2243–2285, doi : 10.1137/130908051 , MR 3141759 .
Ди Джакомо, Эмилио; Мейер, Хенк (2004), «Отслеживайте рисунки графов с постоянным номером очереди», Рисование графиков: 11-й Международный симпозиум, GD 2003, Перуджа, Италия, 21–24 сентября 2003 г. Пересмотренные статьи , Конспекты лекций по информатике, том. 2912, Берлин: Springer, стр. 214–225, номер doi : 10.1007/978-3-540-24595-7_20 , ISBN. 978-3-540-20831-0 , МР 2177595 .
Дуймович, Вида (2015), «Схемы графов с помощью слоистых разделителей», Журнал комбинаторной теории , серия B, 110 : 79–89, arXiv : 1302.0304 , doi : 10.1016/j.jctb.2014.07.005 , MR 3279388 , S2CID 60 212 .
Дуймович, Вида ; Эппштейн, Дэвид ; Хикингботэм, Роберт; Морен, Пэт ; Вуд, Дэвид Р. (2022), «Номер стека не ограничен номером очереди», Combinatorica , 42 (2): 151–164, arXiv : 2011.04195 , doi : 10.1007/s00493-021-4585-7 , MR 4426297 , S2CID 226281691 .
Дуймович, Вида ; Джорет, Гвенэль; Мичек, Петр; Морен, Пэт ; Юкердт, Торстен; Вуд, Дэвид Р. (2020), «Плоские графы имеют ограниченный номер очереди», Журнал ACM , 67 (4): 1–38, arXiv : 1904.04791 , doi : 10.1145/3385731
Дуймович, Вида ; Морен, Пэт ; Вуд, Дэвид Р. (2005), «Макет графов с ограниченной шириной дерева», SIAM Journal on Computing , 34 (3): 553–579, arXiv : cs/0406024 , doi : 10.1137/S0097539702416141 , MR 2137079 , S2CID 3264071 .
Дуймович, Вида ; Морен, Пэт ; Вуд, Дэвид Р. (2013), «Слоистые разделители для макетов очередей, рисование трехмерных графиков и неповторяющаяся раскраска», Труды 54-го симпозиума IEEE по основам компьютерных наук (FOCS '13) , стр. 280–289, arXiv : 1306.1595 , doi : 10.1109/FOCS.2013.38 , S2CID 5613857 .
Дуймович, Вида ; Пор, Аттила; Вуд, Дэвид Р. (2004), «Схемы графиков» (PDF) , Дискретная математика и теоретическая информатика , 6 (2): 497–521, arXiv : cs/0407033 , Bibcode : 2004cs...... ..7033D , МР 2180055 .
Дуймович, Вида ; Вуд, Дэвид Р. (2003), «Разбиение k -деревьев с применением в виде графов», Теоретико-графовые концепции в информатике: 29-й международный семинар, WG 2003. Элспит, Нидерланды, 19-21 июня 2003 г. Пересмотренные статьи , Конспекты лекций по информатике, том. 2880, Берлин: Springer, стр. 205–217, CiteSeerX 10.1.1.130.1914 , doi : 10.1007/978-3-540-39890-5_18 , ISBN 978-3-540-20452-7 , МР 2080081 .
Дуймович, Вида ; Вуд, Дэвид Р. (2004), «О линейных компоновках графов» (PDF) , Дискретная математика и теоретическая информатика , 6 (2): 339–357, MR 2081479 .
Дуймович, Вида ; Вуд, Дэвид Р. (2005), «Стеки, очереди и дорожки: схемы подразделений графа» (PDF) , Дискретная математика и теоретическая информатика , 7 (1): 155–201, doi : 10.46298/dmtcs.346 , MR 2164064 .
Гэнли, Джозеф Л.; Хит, Ленвуд С. (2001), «Номер страницы k -деревьев равен O ( k )», Discrete Applied Mathematics , 109 (3): 215–221, doi : 10.1016/S0166-218X(00)00178-5 , МР 1818238 .
Грегор, Петр; Шкрековски, Ристе; Вукашинович, Вида (2011), «О номере очереди гиперкуба», Электронные заметки по дискретной математике , 38 : 413–418, doi : 10.1016/j.endm.2011.09.067 .
Грегор, Петр; Шкрековски, Ристе; Вукашинович, Вида (2012), «Схемы очередей гиперкубов», SIAM Journal on Discrete Mathematics , 26 (1): 77–88, CiteSeerX 10.1.1.417.7129 , doi : 10.1137/100813865 .
Хасунума, Тору; Хирота, Миса (2007), «Улучшенная верхняя граница номера очереди гиперкуба», Information Processing Letters , 104 (2): 41–44, doi : 10.1016/j.ipl.2007.05.006 , MR 2343263 .
Хит, Ленвуд С.; Лейтон, Фрэнк Томсон ; Розенберг, Арнольд Л. (1992), «Сравнение очередей и стеков как механизмов построения графов», SIAM Journal on Discrete Mathematics , 5 (3): 398–412, doi : 10.1137/0405031 , MR 1172748 .
Хит, Ленвуд С.; Розенберг, Арнольд Л. (1992), «Размещение графиков с использованием очередей», SIAM Journal on Computing , 21 (5): 927–958, doi : 10.1137/0221055 , MR 1181408 .
Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Спрингер, номер домена : 10.1007/978-3-642-27875-4 , ISBN. 978-3-642-27874-7 , МР 2920058 .
Нешетржил, Ярослав ; Оссона де Мендес, Патрис ; Вуд, Дэвид Р. (2012), «Характеристики и примеры классов графов с ограниченным расширением», Европейский журнал комбинаторики , 33 (3): 350–373, arXiv : 0902.3265 , doi : 10.1016/j.ejc.2011.09.008 , МР 2864421 , S2CID 2633083 .
Пай, Кунг-Джуи; Чанг, Джоу-Мин; Ван, Юэ-Ли (2008), «Заметка об «Улучшенной верхней границе номера очереди гиперкуба» », Information Processing Letters , 108 (3): 107–109, doi : 10.1016/j.ipl.2008.04. 019 , МР 2452135 .
Ренгараджан, С.; Вени Мадхаван, CE (1995), «Количество стека и очереди двумерных деревьев», Вычисления и комбинаторика: Первая ежегодная международная конференция, COCOON '95, Сиань, Китай, 24–26 августа 1995 г., Труды , Конспекты лекций по компьютеру Наука, том. 959, Берлин: Springer, стр. 203–212, doi : 10.1007/BFb0030834 , ISBN. 978-3-540-60216-3 , МР 1450116 .
Шахрохи, Фархад; Ши, Вейпин (2000), «О пересекающихся множествах, непересекающихся множествах и номере страницы», Journal of Algorithms , 34 (1): 40–53, doi : 10.1006/jagm.1999.1049 , MR 1732197 .
Вуд, Дэвид Р. (2002), «Схемы очередей, ширина дерева и рисование трехмерных графов», FST TCS 2002: Основы программных технологий и теоретической информатики, 22-я конференция Канпур, Индия, 12–14 декабря 2002 г. , Труды , Конспекты лекций по информатике, вып. 2556, Берлин: Springer, стр. 348–359, номер документа : 10.1007/3-540-36206-1_31 , ISBN. 978-3-540-00225-3 , МР 2046017 .
Вуд, Дэвид Р. (2005), «Схемы очередей произведений и степеней графа» (PDF) , Discrete Mathematics & Theoretical Computer Science , 7 (1): 255–268, doi : 10.46298/dmtcs.352 , MR 2183176 , S2CID 2361133 .
Вуд, Дэвид Р. (2008), «Графы ограниченной степени имеют сколь угодно большое число очередей» , Discrete Mathematics & Theoretical Computer Science , 10 (1): 27–34, arXiv : math/0601293 , Bibcode : 2006math... ...1293 Вт .

Внешние ссылки

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

[hr92-1] Jump up to: ^а ^б ^с Хит и Розенберг (1992) .

[2] Ауэр и др. (2011) .

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

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

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

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

[7] Алам и др. (2020) .

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

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

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

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

[12] Вуд (2005) .

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

[dw04-14] Jump up to: ^а ^б Дуймович и Вуд (2004) .

[15] Хит, Лейтон и Розенберг (1992) . Алгоритм с полиномиальным временем для поиска макета с таким количеством очередей предложен Шахрохи и Ши (2000) . Дуймович и Вуд (2004) улучшили постоянный коэффициент в этой связи до ⁠ $e{\sqrt {m}}$ ⁠ , где $e$ — основание натурального логарифма .

[16] Хит, Лейтон и Розенберг (1992) ; Вуд (2008) .

[dehmw20-17] Jump up to: ^а ^б Дуймович и др. (2022)

[hlr92-18] Jump up to: ^а ^б Хит, Лейтон и Розенберг (1992) .

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

[20] Дуймович и Вуд (2003) ; Дуймович, Морен и Вуд (2005) . См. Wood (2002) для более слабого предварительного результата, ограничивающего номер очереди шириной пути или комбинацией ширины дерева и степени.

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

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

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

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

[25] Вуд (2002) ; Дуймович, Пор и Вуд (2004) ; Дуймович, Морен и Вуд (2005) . См. Di Giacomo & Meijer (2004) для более точных ограничений размеров сетки для графов с небольшим количеством очередей.

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

[27] Дуймович, Морен и Вуд (2005)

[28] Дуймович и др. (2020)

[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]

[27]

[28]