Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Де Брейна график . При показанном порядке вершин разделение ребер на два подмножества, проходящих по левой и правой сторонам чертежа, представляет собой схему с двумя очередями этого графа.

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

Определение [ править ]

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

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

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

Классы графов с ограниченным номером очереди [ править ]

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

Binary графов де Брейна имеют очереди номер 2. [7] d - мерный гиперкуб граф имеет очереди число максимум . [8] Номера очередей полных графов K n и полных двудольных графов K a , b точно известны: они равны и соответственно. [9]

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

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

Связанные инварианты [ править ]

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

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

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

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

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

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

Вычислительная сложность [ править ]

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

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

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

Приложение в графическом изображении [ править ]

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

Заметки [ править ]

  1. ^ a b 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. ^ Грегор, Škrekovski & Vukašinović (2012)
  9. ^ Хит и Розенберг (1992) , предложения 4.7 и 4.8.
  10. ^ Хит и Розенберг (1992) , теорема 3.2.
  11. ^ Вуд (2005) .
  12. ^ Хит и Розенберг (1992) , теорема 3.6
  13. ^ а б Дуймович и Вуд (2004) .
  14. ^ Хит, Лейтон и Розенберг (1992) . Алгоритм с полиномиальным временем для поиска макета с таким количеством очередей представлен Shahrokhi & Shi (2000) . Dujmović & Wood (2004) улучшили постоянный множитель в этой оценке до e √ m , где e - основание натурального логарифма .
  15. ^ Хит, Лейтон и Розенберг (1992) ; Дерево (2008) .
  16. ^ а б Дуймович и др. (2020)
  17. ^ a b Хит, Лейтон и Розенберг (1992) .
  18. ^ Дуймович и Вуд (2005) .
  19. ^ Дуймович и Вуд (2003) ; Дуймович, Morin & Wood (2005) . См. Wood (2002) для более слабого предварительного результата, ограничивающего номер очереди шириной пути или комбинацией ширины дерева и степени.
  20. ^ Хит и Розенберг (1992) , следствие 3.9.
  21. ^ Хит и Розенберг (1992) , теорема 2.3.
  22. ^ Нешетржил, Оссона де Мендес и Вуд (2012) ; Нешетржил и Оссона де Мендес (2012) , стр. 321–327.
  23. ^ Nešetřil & Ossona де Мендес (2012) , теорема 18.2, стр. 401.
  24. ^ Вуд (2002) ; Дуймович, Пор и Вуд (2004) ; Дуймович, Morin & Wood (2005) . См. Di Giacomo & Meijer (2004), где приведены более жесткие границы размеров сетки для графов с малым числом очередей.
  25. ^ Дуймович и Вуд (2003)
  26. ^ Дуймович, Морин & Wood (2005)
  27. ^ Дуймович и др. (2019)

Ссылки [ править ]

  • Ауэр, Кристофер; Бахмайер, Кристиан; Бранденбург, Франц Иосиф; Бруннер, Вольфганг; Гляйсснер, Андреас (2011), «Плоские чертежи графов очередей и двухсторонних графиков», Рисование графиков : 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21–24 сентября 2010 г., Revised Selected Papers , Lecture Notes in Computer Science, 6502 , Гейдельберг:. Спрингер, С. 68-79, DOI : 10.1007 / 978-3-642-18469-7_7 , МР  2781254.
  • Бекос, Майкл А .; Ферстер, Генри; Гронеманн, Мартин; Мчедлидзе, Тамара; Монтеккиани, Фабрицио; Рафтопулу, Хризанти; Ueckerdt, Torsten (2018), «Плоские графы ограниченной степени имеют постоянный номер очереди», CoRR 1811.00816 , arXiv : 1811.00816 , Bibcode : 2018arXiv181100816B.
  • Ди Баттиста, Джузеппе; Фрати, Фабрицио; Pach, Янош (2013), "О числе очереди планарных графов" (PDF) , SIAM журнал по вычислениям , 42 (6): 2243-2285, DOI : 10,1137 / 130908051 , MR  3141759.
  • Ди Джакомо, Эмилио; Мейер, Хенк (2004), «Дорожные рисунки графов с постоянным номером очереди», Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, 21-24 сентября 2003 г. Пересмотренные статьи , Lecture Notes in Computer Science, 2912 , Berlin: . Спрингер, С. 214-225, DOI : 10.1007 / 978-3-540-24595-7_20 , МР  2177595.
  • Дуймович, Вида (2015), «Макеты графов с помощью слоистых разделителей», Журнал комбинаторной теории , серия B, 110 : 79–89, arXiv : 1302.0304 , doi : 10.1016 / j.jctb.2014.07.005 , MR  3279388.
  • Дуймович, Вида; Эпштейн, Дэвид ; Хикингботэм, Роберт; Morin, Pat ; Вуд, Дэвид (2020), Номер стека не ограничен номером очереди , arXiv : 2011.04195.
  • Дуймович, Вида; Йорет, Гвенэль; Мичек, Петр; Morin, Pat ; Ueckerdt, Torsten; Вуд, Дэвид Р. (2019), «Планарные графы имеют ограниченное число очереди», Proc. 60-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS 2019) , arXiv : 1904.04791
  • Дуймович, Вида; Morin, Pat ; Вуд, Дэвид Р. (2005), «Макет графов с ограниченной шириной дерева», SIAM Journal on Computing , 34 (3): 553–579, arXiv : cs / 0406024 , doi : 10.1137 / S0097539702416141 , MR  2137079.
  • Дуймович, Вида; Morin, Pat ; Вуд, Дэвид Р. (2013), «Слоистые разделители для макетов очередей, рисование трехмерных графиков и неповторяющаяся раскраска», Труды 54-го симпозиума IEEE по основам компьютерных наук (FOCS '13) , стр. 280–289, arXiv : 1306.1595 , DOI : 10,1109 / FOCS.2013.38.
  • Дуймович, Вида; Пор, Аттила; Вуд, Дэвид Р. (2004), «Схема расположения графиков» (PDF) , Дискретная математика и теоретическая информатика , 6 (2): 497–521, arXiv : cs / 0407033 , Bibcode : 2004cs ...... ..7033D , Руководство по эксплуатации  2180055.
  • Дуймович, Вида; Вуд, Дэвид Р. (2003), «Древовидные разбиения k -деревьев с приложениями в макете графов», Теоретико- графические концепции в компьютерных науках: 29-й международный семинар, WG 2003. Эльспит, Нидерланды, 19-21 июня 2003 г. . Пересмотренные документы , Lecture Notes в области компьютерных наук, 2880 , Берлин: Springer, С. 205-217,. DOI : 10.1007 / 978-3-540-39890-5_18 , MR  2080081.
  • Дуймович, Вида; Вуд, Дэвид Р. (2004), «О линейных схемах графиков» (PDF) , Дискретная математика и теоретическая информатика , 6 (2): 339–357, MR  2081479.
  • Дуймович, Вида; Вуд, Дэвид Р. (2005), «Стеки, очереди и дорожки: схемы подразделов графа» (PDF) , Дискретная математика и теоретическая информатика , 7 (1): 155–201, MR  2164064.
  • Ganley, Joseph L .; Хит, Lenwood С. (2001), "О PageNumber из к -деревьях есть О ( к )", Дискретный прикладной математики , 109 (3): 215-221, DOI : 10.1016 / S0166-218X (00) 00178-5 , MR  1818238.
  • Грегор, Петр; Шкрековски, Ристе; Вукашинович, Вида (2011), «О порядке очереди гиперкуба», Электронные заметки по дискретной математике , 38 : 413–418, doi : 10.1016 / j.endm.2011.09.067.
  • Грегор, Петр; Шкрековски, Ристе; Vukašinović, Вид (2012), "Очередь макеты гиперкуб", SIAM журнал по дискретной математике , 26 (1): 77-88, CiteSeerX  10.1.1.417.7129 , DOI : 10,1137 / 100813865.
  • Хасунума, Тору; Хирота, Миса (2007), "улучшенный верхняя граница на queuenumber гиперкуба", Information Processing Letters , 104 (2): 41-44, DOI : 10.1016 / j.ipl.2007.05.006 , MR  2343263.
  • Heath, Lenwood S .; Лейтон, Фрэнк Томсон ; Розенберг, Арнольд Л. (1992), "Сравнение очередей и стеков в качестве механизмов для прокладки графиков", SIAM журнал по дискретной математике , 5 (3): 398-412, DOI : 10,1137 / 0405031 , МР  1172748.
  • Heath, Lenwood S .; Розенберг, Арнольд Л. (1992), "Разметка графики с использованием очередей", SIAM журнал по вычислениям , 21 (5): 927-958, DOI : 10,1137 / 0221055 , МР  1181408.
  • Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), разреженность: графики, структуры и алгоритмы , алгоритмы и комбинаторика, 28 , Springer, DOI : 10.1007 / 978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR  2920058.
  • Нешетржил, Ярослав ; Оссона де Мендес, Патрис ; Вуд, Дэвид Р. (2012), «Характеристики и примеры классов графов с ограниченным расширением», Европейский журнал комбинаторики , 33 (3): 350–373, arXiv : 0902.3265 , doi : 10.1016 / j.ejc.2011.09.008 , Руководство по ремонту  2864421.
  • Пай, Кунг-Джуй; Чанг, Джоу-Мин; Ван, Юэ-Ли (2008), «Заметка о« улучшенной верхней границе числа очереди гиперкуба » », Письма об обработке информации , 108 (3): 107–109, DOI : 10.1016 / j.ipl.2008.04. 019 , Руководство MR  2452135.
  • Rengarajan, S .; Вени Мадхаван, CE (1995), "Стек и количество очередей 2-деревьев", Вычислительная техника и комбинаторика: первая ежегодная международная конференция, COCOON '95, Сиань, Китай, 24–26 августа 1995 г., Труды , Лекционные заметки на компьютере Наука, 959 , Берлин:. Springer, С. 203-212, DOI : 10.1007 / BFb0030834 , MR  1450116.
  • Шахрохи, Фархад; Ши, Вэйпин (2000), "О пересечении множеств, непересекающихся множеств, и PageNumber", журнал алгоритмов , 34 (1): 40-53, DOI : 10,1006 / jagm.1999.1049 , МР  1732197.
  • Вуд, Дэвид Р. (2002), «Макеты очередей, ширина дерева и рисование трехмерных графиков», FST TCS 2002: Основы программных технологий и теоретической информатики, 22-я конференция Канпур, Индия, 12–14 декабря 2002 г. , Труды , Лекции по информатике, 2556 , Берлин: Springer, С. 348-359,. DOI : 10.1007 / 3-540-36206-1_31 , MR  2046017.
  • Вуд, Дэвид Р. (2005), «Макеты очередей графов произведений и степеней» (PDF) , Дискретная математика и теоретическая информатика , 7 (1): 255–268, MR  2183176.
  • Вуд, Дэвид Р. (2008), «Графы с ограниченной степенью имеют произвольно большое количество очередей» , Дискретная математика и теоретическая информатика , 10 (1): 27–34, arXiv : math / 0601293 , Bibcode : 2006math ... ... 1293 Вт.

Внешние ссылки [ править ]

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