Википедия

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

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

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

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

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

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

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

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

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

Число очередей бинарных графов де Брёйна равно 2[7]. Число очередей графа d-мерного гиперкуба не превосходит d − 1 [8]. Число очередей полных графов Kn и полных двудольных графов Ka,b известно точно — оно равно   и   соответственно[9].

Нерешённые проблемы математики: Имеет ли все планарные графы ограниченное число очередей?

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

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

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

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

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

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

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

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

Определение числа очередей графа является NP-полной задачей. NP-полной задачей является даже проверка, что число очередей равно единице[21].

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

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

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

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

Логарифмические или полилогарифмические границы числа очередей преобразуются при подобных вложениях в трёхмерные решётки в почти линейные объёмы, решётка в одном направлении будет иметь линейный размер, а в двух других — полилогарифмический. Планарные графы, графы с ограниченным родом и графы с ограниченной локальной древесной шириной имеют вложения объёма O(n log n) [12], в то время как графы замкнутых по минорам семейств имеют объём O(n logO(1) n)[13].

Примечания править

  1. ↑ 1 2 3 4 Heath, Rosenberg, 1992.
  2. ↑ Auer, Bachmaier, Brandenburg, Brunner, 2011.
  3. ↑ Heath, Rosenberg, 1992, с. Proposition 4.1.
  4. ↑ Heath, Rosenberg, 1992, с. Propositions 4.2, 4.3.
  5. ↑ 1 2 3 4 5 6 7 Heath, Leighton, Rosenberg, 1992.
  6. ↑ 1 2 Rengarajan, Veni Madhavan, 1995.
  7. ↑ Heath, Rosenberg, 1992, с. Proposition 4.6.
  8. ↑ Heath, Rosenberg, 1992, Proposition 4.10; Hasunuma, Hirota, 2007; Pai, Chang, Wang, 2008; Gregor, Škrekovski, Vukašinović, 2011.
  9. ↑ Heath, Rosenberg, 1992, с. Propositions 4.7, 4.8.
  10. ↑ Heath, Rosenberg, 1992, с. Theorem 3.2.
  11. ↑ 1 2 Dujmović, Wood, 2005.
  12. ↑ 1 2 Дуймович (Dujmović 2015), улучшение более ранней границы Ди Батисты, Фрати и Паха (Di Battista, Frati, Pach 2013).
  13. ↑ 1 2 Dujmović, Morin, Wood, 2013.
  14. ↑ Wood, 2005.
  15. ↑ Heath, Rosenberg, 1992, с. Theorem 3.6.
  16. ↑ 1 2 Dujmović, Wood, 2004.
  17. ↑ Heath, Leighton, Rosenberg, 1992. Алгоритм полиномиального времени для поиска макета с близким этому числом очередей дали Шароки и Ши (Shahrokhi, Shi 2000). Дуймович и Вуд (Dujmović, Wood 2004) улучшил константу в этой границе до e√m, где e — основание натурального логарифма.
  18. ↑ Wood, 2008.
  19. ↑ Ganley, Heath, 2001.
  20. ↑ Dujmović, Wood, 2003; Dujmović, Morin, Wood, 2005. См. статью Вуда (Wood 2002) о более слабом предварительном результате, ограничивающем число очередей путевой шириной или комбинацией древесной ширины и степени графа.
  21. ↑ Heath, Rosenberg, 1992, с. Corollary 3.9.
  22. ↑ Heath, Rosenberg, 1992, с. Theorem 2.3.
  23. ↑ Nešetřil, Ossona de Mendez, Wood, 2012.
  24. ↑ Nešetřil, Ossona de Mendez, 2012, с. 321–327.
  25. ↑ Nešetřil, Ossona de Mendez, 2012, с. 401, Theorem 18.2.
  26. ↑ Wood, 2002; Dujmović, Pór, Wood, 2004; Dujmović, Morin, Wood, 2005. См. Di Giacomo, Meijer, 2004 for tighter bounds on the grid dimensions for graphs of small queue number.
  27. ↑ Dujmović, Wood, 2003.
  28. ↑ Dujmović, Morin, Wood, 2005.

Литература править

  • Christopher Auer, Christian Bachmaier, Franz Josef Brandenburg, Wolfgang Brunner, Andreas Gleißner. Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers. — Heidelberg: Springer, 2011. — Т. 6502. — С. 68–79. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-18469-7_7.
  • Giuseppe Di Battista, Fabrizio Frati, János Pach. On the queue number of planar graphs // SIAM Journal on Computing. — 2013. — Т. 42, вып. 6. — С. 2243–2285. — doi:10.1137/130908051.
  • Emilio Di Giacomo, Henk Meijer. Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003 Revised Papers. — Berlin: Springer, 2004. — Т. 2912. — С. 214–225. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-24595-7_20.
  • Vida Dujmović. Graph layouts via layered separators // Journal of Combinatorial Theory. — 2015. — Т. 110. — С. 79–89. — doi:10.1016/j.jctb.2014.07.005. — arXiv:1302.0304..
  • Vida Dujmović, Pat Morin, David R. Wood. Layout of graphs with bounded tree-width // SIAM Journal on Computing. — 2005. — Т. 34, вып. 3. — С. 553–579. — doi:10.1137/S0097539702416141. — arXiv:cs/0406024..
  • Vida Dujmović, Pat Morin, David R. Wood. Proceedings of the 54th IEEE Symposium on Foundations of Computer Science (FOCS ’13). — 2013. — С. 280–289. — doi:10.1109/FOCS.2013.38..
  • Vida Dujmović, Attila Pór, David R. Wood. Track layouts of graphs // Discrete Mathematics & Theoretical Computer Science. — 2004. — Т. 6, вып. 2. — С. 497–521..
  • Vida Dujmović, David R. Wood. Graph-theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers. — Berlin: Springer, 2003. — Т. 2880. — С. 205–217. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-39890-5_18..
  • Vida Dujmović, David R. Wood. On linear layouts of graphs // Discrete Mathematics & Theoretical Computer Science. — 2004. — Т. 6, вып. 2. — С. 339–357..
  • Vida Dujmović, David R. Wood. Stacks, queues and tracks: layouts of graph subdivisions // Discrete Mathematics & Theoretical Computer Science. — 2005. — Т. 7, вып. 1. — С. 155–201..
  • Joseph L. Ganley, Lenwood S. Heath. The pagenumber of k-trees is O(k) // Discrete Applied Mathematics. — 2001. — Т. 109, вып. 3. — С. 215–221. — doi:10.1016/S0166-218X(00)00178-5..
  • Petr Gregor, Riste Škrekovski, Vida Vukašinović. On the queue-number of the hypercube // Electronic Notes in Discrete Mathematics. — 2011. — Т. 38. — С. 413–418. — doi:10.1016/j.endm.2011.09.067..
  • Toru Hasunuma, Misa Hirota. An improved upper bound on the queuenumber of the hypercube // Information Processing Letters. — 2007. — Т. 104, вып. 2. — С. 41–44. — doi:10.1016/j.ipl.2007.05.006..
  • Lenwood S. Heath, Frank Thomson Leighton, Arnold L. Rosenberg. Comparing queues and stacks as mechanisms[sic] for laying out graphs // SIAM Journal on Discrete Mathematics. — 1992. — Т. 5, вып. 3. — С. 398–412. — doi:10.1137/0405031..
  • Lenwood S. Heath, Arnold L. Rosenberg. Laying out graphs using queues // SIAM Journal on Computing. — 1992. — Т. 21, вып. 5. — С. 927–958. — doi:10.1137/0221055..
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7. — doi:10.1007/978-3-642-27875-4..
  • Jaroslav Nešetřil, Patrice Ossona de Mendez, David R. Wood. Characterisations and examples of graph classes with bounded expansion // European Journal of Combinatorics. — 2012. — Т. 33, вып. 3. — С. 350–373. — doi:10.1016/j.ejc.2011.09.008. — arXiv:0902.3265.
  • Kung-Jui Pai, Jou-Ming Chang, Yue-Li Wang. A note on “An improved upper bound on the queuenumber of the hypercube” // Information Processing Letters. — 2008. — Т. 108, вып. 3. — С. 107–109. — doi:10.1016/j.ipl.2008.04.019.
  • S. Rengarajan, C. E. Veni Madhavan. Computing and Combinatorics: First Annual International Conference, COCOON '95 Xi'an, China, August 24–26, 1995, Proceedings. — Berlin: Springer, 1995. — Т. 959. — С. 203–212. — (Lecture Notes in Computer Science). — doi:10.1007/BFb0030834..
  • Farhad Shahrokhi, Weiping Shi. On crossing sets, disjoint sets, and pagenumber // Journal of Algorithms. — 2000. — Т. 34, вып. 1. — С. 40–53. — doi:10.1006/jagm.1999.1049.
  • David R. Wood. FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, 22nd Conference Kanpur, India, December 12–14, 2002, Proceedings. — Berlin: Springer, 2002. — Т. 2556. — С. 348–359. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-36206-1_31.
  • David R. Wood. Queue layouts of graph products and powers // Discrete Mathematics & Theoretical Computer Science. — 2005. — Т. 7, вып. 1. — С. 255–268..
  • David R. Wood. Bounded-degree graphs have arbitrarily large queue-number // Discrete Mathematics & Theoretical Computer Science. — 2008. — Т. 10, вып. 1. — С. 27–34. — arXiv:math/0601293. (недоступная ссылка).

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

Источник — https://ru.wikipedia.org/w/index.php?title=Число_очередей_графа&oldid=112207884