Можно ли нарисовать полный двудольный граф с меньшим числом пересечений, чем число, указанное Заранкевичем?
В математике на графику рисунка , проблема кирпичного завода Турана запрашивает минимальное число пересечений в рисунке полного двудольного графа . Проблема названа в честь Пала Турана , который сформулировал ее, когда был вынужден работать на кирпичном заводе во время Второй мировой войны. [1]
Было высказано предположение, что метод рисования, найденный Казимежем Заранкевичем , дает правильный ответ для каждого полного двудольного графа, и утверждение, что это верно, стало известно как гипотеза числа скрещивания Заранкевича . Гипотеза остается открытой, решены лишь некоторые частные случаи. [2]
Происхождение и формулировка
Во время Второй мировой войны венгерский математик Пал Туран был вынужден работать на кирпичном заводе, перевозя вагоны кирпичей из печей на склады. На фабрике были пути от каждой печи до каждого места хранения, и вагоны было труднее толкать в точках пересечения путей. Эта ситуация вдохновила Турана спросить, как можно перестроить фабрику, чтобы минимизировать количество переходов между этими путями. [1]
Математически, эта проблема может быть оформлена как просить граф рисунок из более полного двудольного графа , вершины которого представляют печи и место хранения, а ребра представляют собой дорожку из каждой печи для каждого места хранения. Граф должен быть нарисован на плоскости с каждой вершиной как точкой, каждым ребром как кривой, соединяющей два его конца, и ни одной вершиной, помещенной на ребро, к которому он не инцидентен. Пересечение считается, если два ребра, которые не пересекаются в графе, имеют непустое пересечение на плоскости. Тогда возникает вопрос, какое минимальное количество пересечений на таком чертеже? [2] [3]
Формулировка этой проблемы Тураном часто считается одним из первых исследований числа пересечений графов . [4] (Другая независимая формулировка той же концепции произошла в социологии, в методах построения социограмм , [5] и гораздо более старая головоломка, проблема трех коммунальных служб , может рассматриваться как частный случай проблемы кирпичного завода с тремя печами. и три хранилища. [6] ) Число пересечений с тех пор приобрело большее значение, как центральный объект исследования при рисовании графов [7] и как важный инструмент в проектировании СБИС [8] и дискретной геометрии . [9]
Верхняя граница
И Заранкевич, и Казимеж Урбаник видели, как Туран говорил о проблеме кирпичного завода на различных переговорах в Польше в 1952 году [3], и независимо опубликовали попытки решения проблемы с эквивалентными формулами для количества переходов. [10] [11] Как они оба показали, всегда можно нарисовать полный двудольный граф K m, n (граф с m вершинами на одной стороне, n вершинами на другой стороне и mn ребрами, соединяющими две стороны ) с числом переходов, равным
Конструкция проста: разместите m вершин на оси x плоскости, избегая начала координат , с равным или почти равным количеством точек слева и справа от оси y . Точно так же разместите n вершин на оси y плоскости, избегая начала координат, с равным или почти равным количеством точек выше и ниже оси x . Затем соедините каждую точку на оси x отрезком прямой линии с каждой точкой на оси y . [3]
Однако их доказательства того, что эта формула оптимальна, то есть не может быть чертежей с меньшим количеством пересечений, были ошибочными. Пробел был обнаружен только через одиннадцать лет после публикации, почти одновременно Герхардом Рингелем и Полем Кайненом . [12] Тем не менее, предполагается, что формула Заранкевича и Урбаника оптимальна. Это стало известно как гипотеза числа скрещивания Заранкевича. Хотя известно, что некоторые частные его случаи верны, общий случай остается открытым. [2]
Нижние границы
Поскольку K m, n и K n, m изоморфны, достаточно рассмотреть случай, когда m ≤ n . Кроме того, при m ≤ 2 конструкция Заранкевича не дает пересечений, которые, конечно, не могут быть преодолены. Таким образом, единственными нетривиальными случаями являются те, для которых m и n оба ≥ 3 .
Попытка доказательства гипотезы Заранкевича, хотя и неверна для общего случая K m , n , работает для случая m = 3 . С тех пор она была распространена на другие малые значения m , и известно, что гипотеза Заранкевича верна для полных двудольных графов K m, n с m ≤ 6 . [13] Гипотеза также известна для K 7,7 , K 7,8 и K 7,9 . [14] Если существует контрпример, то есть граф K m, n, требующий меньшего количества пересечений, чем граница Заранкевича, то в наименьшем контрпримере и m, и n должны быть нечетными. [13]
Для каждого фиксированного выбора m истинность гипотезы для всех K m, n может быть проверена путем проверки только конечного числа вариантов выбора n . [15] В более общем плане было доказано, что каждый полный двудольный граф требует количества пересечений, которое (для достаточно больших графов) составляет не менее 83% от числа, заданного границей Заранкевича. Устранение разрыва между этой нижней и верхней границами остается открытой проблемой. [16]
Номера прямолинейных пересечений
Если требуется рисовать ребра как отрезки прямых линий, а не как произвольные кривые, то для некоторых графов требуется больше пересечений, чем при рисовании с изогнутыми ребрами. Однако верхняя граница, установленная Заранкевичем для числа пересечений полных двудольных графов, может быть достигнута с использованием только прямых ребер. Следовательно, если гипотеза Заранкевича верна, то полные двудольные графы имеют прямолинейные числа пересечений, равные их номерам пересечений. [17]
Рекомендации
- ^ a b Turán, P. (1977), «Приветственное письмо», Journal of Graph Theory , 1 : 7–9, doi : 10.1002 / jgt.3190010105.
- ^ а б в Пах, Янош ; Шарир, Миха (2009), «5.1 Пересечения - проблема кирпичного завода», комбинаторная геометрия и ее алгоритмические приложения: лекции Алкалы , математические обзоры и монографии, 152 , Американское математическое общество , стр. 126–127.
- ^ а б в Бейнеке, Лоуэлл ; Уилсон, Робин (2010), "Ранняя история проблемы кирпичный завод", Математическая Интеллидженсер , 32 (2): 41-48, DOI : 10.1007 / s00283-009-9120-4 , MR 2657999 , S2CID 122588849.
- ^ Фулдс, Л. Р. (1992), Приложения теории графов , Universitext, Springer, стр. 71, ISBN 9781461209331.
- ^ Бронфенбреннер, Ури (1944), "Графическое представление данных социометрического", Социометрия , 7 (3): 283-289, DOI : 10,2307 / 2785096 , JSTOR 2785096 ,
Расположение предметов на диаграмме, в то время как бессистемно частично, определяется в основном методом проб и ошибок с целью минимизации количества пересекающихся линий.
- ^ Бона, Миклош (2011), Прогулка по комбинаторике: Введение в теорию перечисления и графов , World Scientific, стр. 275–277, ISBN 9789814335232. Бона представляет загадку (в виде трех домов, соединенных с тремя колодцами) на стр. 275 и пишет на стр. 277, что это «эквивалентно задаче рисования K 3,3 на плоской поверхности без пересечений».
- ^ Шефер, Маркус (2014), «Число пересечений графа и его варианты: обзор», Электронный журнал комбинаторики : # DS21
- ^ Лейтон, Т. (1983), Проблемы сложности в СБИС , Основы вычислительной серии, Кембридж, Массачусетс: MIT Press
- ^ Секей, Л. (1997), "номера Пересечение и сложные проблемы Erdős в дискретной геометрии", Комбинаторика, Вероятность и вычисления , 6 (3): 353-358, DOI : 10,1017 / S0963548397002976 , MR 1464571
- ^ Zarankiewicz, К. (1954), "Об одной задаче П. Туран относительно графиков", Fundamenta Mathematicae , 41 : 137-145, DOI : 10,4064 / фм-41-1-137-145 , MR 0063641.
- ^ Урбаник, К. (1955), "Решение проблемы посе пар П. Туран", Colloq. Математика. , 3 : 200–201. Как цитирует Секели, Ласло А. (2001) [1994], "Гипотеза числа скрещивания Заранкевича" , Энциклопедия математики , EMS Press
- ^ Гай, Ричард К. (1969), «Упадок и падение теоремы Заранкевича», Методы доказательства в теории графов (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) , Academic Press, New York, стр. 63–69, MR 0253931.
- ^ а б Клейтмана, Daniel J. (1970), "Число пересечения K 5, п ", Журнал комбинаторной теории , 9 : 315-323, DOI : 10.1016 / s0021-9800 (70) 80087-4 , МР 0280403.
- ^ Woodall, DR (1993), "графы Циклический порядка и кроссинговер номер гипотезы Zarankiewicz в" Журнал теории графов , 17 (6): 657-671, DOI : 10.1002 / jgt.3190170602 , MR 1244681.
- ^ Кристиан, Робин; Рихтер, Р. Брюс; Салазар, Gelasio (2013), "гипотеза Zarankiewicz является конечной при каждом фиксированном т ", Журнал комбинаторной теории , Series B, 103 (2): 237-247, DOI : 10.1016 / j.jctb.2012.11.001 , MR 3018068.
- ^ de Klerk, E .; Maharry, J .; Пасечник, ДВ; Рихтер, РБ; Салазар, Г. (2006), «Улучшенные оценки для чисел пересечения K m, n и K n », Журнал SIAM по дискретной математике , 20 (1): 189–202, arXiv : math / 0404142 , doi : 10.1137 / S0895480104442741 , МР 2257255 , S2CID 1509054.
- ^ Kainen, Paul C. (1968), "Об одной задаче П. Эрдеша", Журнал комбинаторной теории , 5 (4): 374-377, DOI : 10.1016 / s0021-9800 (68) 80013-4 , MR 0231744
Внешние ссылки
- Вайсштейн, Эрик В. , "Гипотеза Заранкевича" , MathWorld