Число пересечения (теория графов) - Crossing number (graph theory)

Рисунок График Хивуда с тремя переходами. Это минимальное количество пересечений среди всех рисунков этого графика, поэтому граф имеет номер пересечения cr (грамм) = 3.

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

Изучение числа скрещиваний началось в Проблема кирпичного завода Турана, в котором Пал Туран попросил план завода, который минимизировал бы количество переходов между путями, соединяющими печи для обжига кирпича с площадками для хранения. Математически эту задачу можно формализовать как запрос числа пересечения полный двудольный граф,[2] Эта же проблема возникла независимо в социология примерно в то же время, в связи со строительством социограммы.[3] Предполагаемая формула Турана для числа пересечений полных двудольных графов остается недоказанной, как и аналогичная формула для полные графики.

В пересечение числового неравенства утверждает, что для графиков, где число е ребер значительно больше, чем количество п вершин, число пересечений как минимум пропорционально е3/п2. Он имеет приложения в СБИС дизайн и геометрия падения.

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

Определения

Для определения номера перекрестка рисунок неориентированный граф представляет собой отображение вершин графа в непересекающиеся точки на плоскости и ребер графа в кривые, соединяющие их два конца. Никакая вершина не должна отображаться на ребро, которое не является конечной точкой, и всякий раз, когда два ребра имеют пересекающиеся кривые (кроме как в общей конечной точке), их пересечения должны образовывать конечный набор правильных пересечений, где две кривые поперечный. Пересечение считается отдельно для каждой из этих точек пересечения, для каждой пары пересекающихся ребер. Таким образом, количество пересечений на графике является минимальным для всех таких чертежей количества пересечений на чертеже.[5]

Некоторые авторы добавляют дополнительные ограничения к определению чертежа, например, что каждая пара ребер имеет не более одной точки пересечения (общая конечная точка или пересечение). Для числа пересечений, как определено выше, эти ограничения не имеют значения, потому что чертеж с минимальным пересечением не может иметь ребер с несколькими точками пересечения. Если два ребра с общей конечной точкой пересекаются, чертеж можно изменить локально в точке пересечения, оставив остальную часть чертежа без изменений, чтобы создать другой рисунок с одним пересечением меньше. Точно так же, если два ребра пересекаются два или более раз, рисунок можно изменить локально в двух точках пересечения, чтобы создать другой рисунок с двумя меньшими пересечениями. Однако эти ограничения актуальны для вариантов определения числа пересечений, которые, например, учитывают только количество пар пересекающихся ребер, а не количество пересечений.[5]

Особые случаи

По состоянию на апрель 2015 года числа пересечений известны для очень небольшого числа семейств графов. В частности, за исключением нескольких начальных случаев, число пересечений полных графов, двудольных полных графов и произведений циклов остается неизвестным, хотя был достигнут некоторый прогресс в отношении нижних оценок.[6]

Полные двудольные графы

Оптимальный рисунок K4,7 показывает, что проблема кирпичного завода Турана с 4 хранилищами (желтые точки) и 7 печами (синие точки) требует 18 переходов (красные точки)
Основная статья: Проблема кирпичного завода Турана

В течение Вторая Мировая Война, Венгерский математик Пал Туран был вынужден работать на кирпичном заводе, перевозя вагоны кирпичей из печей на склады. На фабрике были пути от каждой печи до каждого места хранения, и вагоны было труднее толкать в точках пересечения путей, откуда Туран был направлен на то, чтобы задать задачу своей кирпичной фабрике: как могут печи, места хранения и пути быть устроены так, чтобы минимизировать общее количество переходов? Математически печи и хранилища можно формализовать как вершины полный двудольный граф, с дорожками в качестве его краев. План завода можно представить в виде чертежа этого графика, поэтому возникает проблема: каково минимально возможное количество пересечений на чертеже полный двудольный граф ?[7]

Казимеж Заранкевич попытался решить проблему кирпичного завода Турана;[8] его доказательство содержало ошибку, но он установил действительное верхняя граница из

для числа пересечения полного двудольного графа Kм, н. Предполагается, что эта оценка является оптимальным числом пересечений для всех полных двудольных графов.[9]

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

Проблема определения числа пересечений полный график был впервые поставлен Энтони Хилл, и появился в печати в 1960 году.[10] Хилл и его сотрудник Джон Эрнест было два художники-конструкторы увлекается математикой. Они не только сформулировали эту проблему, но и создали гипотетическую формулу для этого числа пересечений, которая Ричард К. Гай опубликовано в 1960 году.[10] А именно известно, что всегда существует рисунок с

переходы. Эта формула дает значения 1, 3, 9, 18, 36, 60, 100, 150 за п = 5, ..., 12; см. последовательность A000241 в Он-лайн энциклопедия целочисленных последовательностей Гипотеза состоит в том, что не может быть лучшего рисунка, поэтому эта формула дает оптимальное количество пересечений для полных графов. Независимая формулировка той же гипотезы была сделана Томас Л. Саати в 1964 г.[11]

Саати дополнительно подтвердил, что эта формула дает оптимальное количество переходов для п ≤ 10 и Пан и Рихтер показали, что он также оптимален для п = 11, 12.[12]

В Гипотеза Альбертсона, сформулированный Майклом О. Альбертсоном в 2007 году, утверждает, что среди всех графов с хроматическое число п, полный граф Kп имеет минимальное количество переходов. То есть, если предполагаемая формула для числа пересечений полного графа верна, то каждый п-хроматический граф имеет число пересечений как минимум равное той же формуле. Теперь известно, что гипотеза Альбертсона верна для п ≤ 16.[13]

Кубические графы

Наименьший кубические графы с номерами пересечения 1–8 и 11 известны (последовательность A110507 в OEIS ). Наименьший кубический граф с 1 пересечением - это полный двудольный граф K3,3, с 6 вершинами. Наименьший кубический граф с двумя пересечениями - это Граф Петерсена, с 10 вершинами. Наименьший кубический граф с 3 пересечениями - это График Хивуда, с 14 вершинами. Наименьший кубический граф с 4 пересечениями - это Граф Мебиуса-Кантора, с 16 вершинами. Наименьший кубический граф с 5 пересечениями - это График Паппа, с 18 вершинами. Наименьший кубический граф с 6 пересечениями - это График дезарга, с 20 вершинами. Ни один из четырех кубических графов с 7 пересечениями и 22 вершинами хорошо известен.[14] Наименьшие кубические графы с 8 пересечениями включают Науру график и График Макги или (3,7) -клетка, с 24 вершинами.[15] Наименьшие кубические графы с 11 пересечениями включают Граф Кокстера с 28 вершинами.[16]

В 2009 году Пегг и Эксу предположили, что наименьший кубический граф с номером пересечения 13 является График Тутте – Кокстера а наименьший кубический граф с номером пересечения 170 - это Тутте 12 клеток.[15][17]

Сложность и приближение

В общем, определить число пересечений графа сложно; Гарей и Джонсон показал в 1983 году, что это NP-жесткий проблема.[18] На самом деле проблема остается NP-сложной даже при ограничении кубические графы[19] и почти планарным графам (графам, которые становятся планарными после удаления единственного ребра).[20] Тесно связанная проблема - определение числа прямолинейных пересечений - это полный для экзистенциальная теория реальности.[21]

С положительной стороны, существуют эффективные алгоритмы определения того, меньше ли число пересечений фиксированной константы. k. Другими словами, проблема в том, управляемый с фиксированными параметрами.[22][23] Остается трудным для больших k, такие как k = |V|/2. Также есть эффективные аппроксимационные алгоритмы для приближения cr (грамм) на графах ограниченной степени.[24] На практике эвристический используются такие алгоритмы, как простой алгоритм, который начинается без ребер и непрерывно добавляет каждое новое ребро таким образом, чтобы получить как можно меньше дополнительных пересечений. Эти алгоритмы используются для вычисления числа прямолинейных пересечений. распределенных вычислений проект.[25]

Неравенство числа пересечений

Основная статья: Пересечение числового неравенства

Для неориентированного простой график грамм с п вершины и е края такие, что е > 7п номер перехода всегда не менее

Эта связь между ребрами, вершинами и числом пересечений была независимо обнаружена Аджтай, Chvátal, Новорожденный и Семереди,[26] и по Leighton.[27] Он известен как пересечение числового неравенства или перекрестная лемма.

Постоянная 29 является наиболее известным на сегодняшний день и принадлежит Акерману.[28] Постоянная 7 может быть понижен до 4, но за счет замены 29 с худшей константой 64.[26][27]

Мотивация Лейтон к изучению чисел скрещивания заключалась в том, что СБИС дизайн в теоретической информатике.[27] Позже Секели также понял, что это неравенство дает очень простые доказательства некоторых важных теорем из геометрия падения, такие как Теорема Бека и Теорема Семереди-Троттера,[29] и Тамал Дей использовал его, чтобы доказать верхние оценки на геометрический k-наборы.[30]

Вариации

Если требуется рисовать ребра как отрезки прямых, а не как произвольные кривые, то для некоторых графов требуется больше пересечений. В номер прямолинейного перехода определяется как минимальное количество пересечений чертежа этого типа. Оно всегда не меньше числа пересечений, а для некоторых графиков больше. Числа прямолинейных пересечений для K5 через K12 находятся 1, 3, 9, 19, 36, 62, 102, 153, (A014540 ) и значениями до K27 известны, с K28 требуя либо 7233, либо 7234 пересечений. Дальнейшие значения собираются проектом «Число прямолинейных пересечений».[25]

График имеет местный номер перехода k если его можно нарисовать не более чем k пересечений на ребро, но не меньше. Графы, которые можно нарисовать не более k переходы на ребро также называют k-плоскостной.[31]

Другие варианты номера пересечения включают номер попарного пересечения (минимальное количество пар ребер, которые пересекаются на любом чертеже) и нечетный номер пересечения (количество пар ребер, пересекающихся нечетное количество раз на любом чертеже). Нечетное число пересечений не более чем равно количеству попарных пересечений, которое не более чем равно количеству пересечений. Однако по Теорема Ханани – Тутте, когда одно из этих чисел равно нулю, все они равны.[5] Шефер (2014, 2018 ) рассматривает множество таких вариантов.[32][33]

Смотрите также

Рекомендации

  1. ^ Покупка, Елена С .; Коэн, Роберт Ф .; Джеймс, Мюррей I. (1995). «Проверка эстетики рисования графиков». В Бранденбурге, Франц-Иосиф (ред.). Graph Drawing, Symposium on Graph Drawing, GD '95, Пассау, Германия, 20-22 сентября 1995 г., Труды. Конспект лекций по информатике. 1027. Springer. С. 435–446. Дои:10.1007 / BFb0021827..
  2. ^ Туран, П. (1977). «Приветственная записка». Журнал теории графов. 1: 7–9. Дои:10.1002 / jgt.3190010105.CS1 maint: ref = harv (ссылка на сайт)
  3. ^ Бронфенбреннер, Ури (1944). «Графическое представление социометрических данных». Социометрия. 7 (3): 283–289. JSTOR  2785096. Расположение предметов на диаграмме, хотя отчасти случайное, определяется в основном методом проб и ошибок с целью минимизировать количество пересекающихся линий.
  4. ^ Шайнерман, Эдвард Р.; Уилф, Герберт С. (1994). «Число прямолинейного пересечения полного графа и« четырехточечная проблема »Сильвестра геометрической вероятности». Американский математический ежемесячный журнал. 101 (10): 939–943. Дои:10.2307/2975158. JSTOR  2975158.CS1 maint: ref = harv (ссылка на сайт)
  5. ^ а б c Пах, Дж.; Тот, Г. (1998). «И вообще, какой это номер перехода?». Материалы 39-го ежегодного симпозиума по основам информатики (FOCS 1998). С. 617–626. Дои:10.1109 / SFCS.1998.743512..
  6. ^ de Klerk, E .; Maharry, J .; Пасечник, Д. В .; Рихтер, В .; Салазар, Г. (2006). "Улучшены оценки числа пересечений Kм, н и Kп". Журнал SIAM по дискретной математике. 20 (1): 189–202. arXiv:математика / 0404142. Дои:10.1137 / S0895480104442741.CS1 maint: ref = harv (ссылка на сайт)
  7. ^ Пах, Янош; Шарир, Миха (2009). «5.1 Переезды - проблема кирпичного завода». Комбинаторная геометрия и ее алгоритмические приложения: лекции по Алкале. Математические обзоры и монографии. 152. Американское математическое общество. С. 126–127.
  8. ^ Заранкевич, К. (1954). «К проблеме П. Турана о графах». Fundamenta Mathematicae. 41: 137–145.CS1 maint: ref = harv (ссылка на сайт)
  9. ^ Гай, Ричард К. (1969). «Упадок и падение теоремы Заранкевича». Методы доказательства в теории графов (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968). Academic Press, Нью-Йорк. С. 63–69. Г-Н  0253931..
  10. ^ а б Гай, Р. К. (1960). «Комбинаторная задача». Набла (Бюллетень Малайского математического общества). 7: 68–72.CS1 maint: ref = harv (ссылка на сайт)
  11. ^ Саати, Т. (1964). «Минимальное количество пересечений в полных графах». Труды Национальной академии наук Соединенных Штатов Америки. 52: 688–690. Bibcode:1964ПНАС ... 52..688С. Дои:10.1073 / pnas.52.3.688. ЧВК  300329. PMID  16591215.CS1 maint: ref = harv (ссылка на сайт)
  12. ^ Пан, Шэнцзюнь; Рихтер, Р. Брюс (2007). "Число пересечений K11 является 100". Журнал теории графов. 56 (2): 128–134. Дои:10.1002 / jgt.20249. Г-Н  2350621..
  13. ^ Барат, Янош; Тот, Геза (2009). «К гипотезе Альбертсона». arXiv:0909.0413 [math.CO ].CS1 maint: ref = harv (ссылка на сайт)
  14. ^ Вайсштейн, Эрик В. «Число пересечения графика». MathWorld.
  15. ^ а б Пегг, Э. Т.; Эксу, Г. (2009). «Графики пересекающихся чисел». Математика журнал. 11. Дои:10.3888 / tmj.11.2-2.CS1 maint: ref = harv (ссылка на сайт)
  16. ^ Хэйторп, Майкл; Ньюкомб, Алекс (2018), Кубических графов на 26 вершинах с пересечением 11 не существует, arXiv:1804.10336
  17. ^ Эксу, Дж. «Прямолинейные рисунки знаменитых графов».
  18. ^ Гарей, М.; Джонсон, Д.С. (1983). «Переходной номер NP-полный». Журнал SIAM по алгебраическим и дискретным методам. 4 (3): 312–316. Дои:10.1137/0604033. Г-Н  0711340.CS1 maint: ref = harv (ссылка на сайт)
  19. ^ Глинены, П. (2006). «Число пересечений для кубических графов сложно». Журнал комбинаторной теории. Серия Б. 96 (4): 455–471. Дои:10.1016 / j.jctb.2005.09.009. Г-Н  2232384.CS1 maint: ref = harv (ссылка на сайт)
  20. ^ Кабельо С. и Мохар Б. (2013). «Добавление одного края к планарным графам затрудняет число пересечений и 1-плоскостность». SIAM Журнал по вычислениям. 42 (5): 1803–1829. arXiv:1203.5944. Дои:10.1137/120872310.CS1 maint: ref = harv (ссылка на сайт)
  21. ^ Шефер, Маркус (2010). Сложность некоторых геометрических и топологических задач (PDF). Графический рисунок, 17-й Международный симпозиум, GS 2009, Чикаго, Иллинойс, США, сентябрь 2009 г., Исправленные статьи. Конспект лекций по информатике. 5849. Springer-Verlag. С. 334–344. Дои:10.1007/978-3-642-11805-0_32. ISBN  978-3-642-11804-3.CS1 maint: ref = harv (ссылка на сайт).
  22. ^ Гроэ, М. (2005). «Вычисление числа пересечений за квадратичное время». Журнал компьютерных и системных наук. 68 (2): 285–302. arXiv:cs / 0009010. Дои:10.1016 / j.jcss.2003.07.008. Г-Н  2059096.CS1 maint: ref = harv (ссылка на сайт)
  23. ^ Каварабаяси, Кен-ичи; Рид, Брюс (2007). Вычисление числа пересечений за линейное время. Материалы 29-го ежегодного симпозиума ACM по теории вычислений. С. 382–390. Дои:10.1145/1250790.1250848. ISBN  978-1-59593-631-8.CS1 maint: ref = harv (ссылка на сайт)
  24. ^ Даже, Гай; Гуха, Судипто; Шибер, Барух (2003). «Улучшенная аппроксимация пересечений в графических чертежах и областях макета СБИС». SIAM Журнал по вычислениям. 32 (1): 231–252. Дои:10.1137 / S0097539700373520.CS1 maint: ref = harv (ссылка на сайт)
  25. ^ а б Освин Айхольцер. «Проект прямолинейных переходных номеров». Архивировано из оригинал на 30.12.2012., иНомер прямолинейного перехода об Институте программных технологий при Технологическом университете Граца (2009 г.).
  26. ^ а б Айтай, М.; Хватал, В.; Новорожденный, М .; Семереди, Э. (1982). Подграфы без пересечений. Теория и практика комбинаторики. Математические исследования Северной Голландии. 60. С. 9–12. Г-Н  0806962.
  27. ^ а б c Лейтон, Т. (1983). Проблемы сложности в СБИС. Основы вычислительной серии. Кембридж, Массачусетс: MIT Press.
  28. ^ Акерман, Эяль (2013). «О топологических графах с не более чем четырьмя пересечениями на ребро» (PDF). Архивировано из оригинал (PDF) на 2014-07-14.
  29. ^ Секели, Л. А. (1997). «Пересечения чисел и трудные задачи Эрдеша в дискретной геометрии». Комбинаторика, теория вероятностей и вычисления. 6 (3): 353–358. Дои:10.1017 / S0963548397002976. Г-Н  1464571.CS1 maint: ref = harv (ссылка на сайт)
  30. ^ Дей, Т.К. (1998). "Улучшены границы для плоских k-наборы и связанные с ними проблемы ». Дискретная и вычислительная геометрия. 19 (3): 373–382. Дои:10.1007 / PL00009354. Г-Н  1608878.CS1 maint: ref = harv (ссылка на сайт)
  31. ^ Рингель, Герхард (1965). "Ein Sechsfarbenproblem auf der Kugel". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (на немецком). 29: 107–117. Дои:10.1007 / BF02996313. Г-Н  0187232.
  32. ^ Шефер, Маркус (2014). «Число пересечений графа и его варианты: обзор». Электронный журнал комбинаторики. DS21.CS1 maint: ref = harv (ссылка на сайт)
  33. ^ Шефер, Маркус (2018). Числа пересечения графов. CRC Press.