Проблема кирпичного завода Турана
В математике рисования графов требует задача Турана о кирпичном заводе минимального количества пересечений при рисовании полного двудольного графа . Проблема названа в честь Пала Турана , который сформулировал ее, когда был вынужден работать на кирпичном заводе во время Второй мировой войны. [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]
Ссылки
[ редактировать ]- ^ Jump up to: а б Туран, П. (1977), «Приветственное письмо», Журнал теории графов , 1 : 7–9, doi : 10.1002/jgt.3190010105 .
- ^ Jump up to: а б с Пах, Янош ; Шарир, Миха (2009), «5.1 Пересечения — проблема кирпичного завода», Комбинаторная геометрия и ее алгоритмические приложения: Лекции в Алькале , Математические обзоры и монографии, том. 152, Американское математическое общество , стр. 126–127 .
- ^ Jump up to: а б с Бейнеке, Лоуэлл ; Уилсон, Робин (2010), «Ранняя история проблемы кирпичного завода», The Mathematical Intelligencer , 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, что это «эквивалентно задаче о рисовании К 3,3 на плоской поверхности без пересечений».
- ^ Шефер, Маркус (2014), «Число пересечений графа и его варианты: обзор», Электронный журнал комбинаторики : # DS21
- ^ Лейтон, Т. (1983), Проблемы сложности в СБИС , Основы вычислительной серии, Кембридж, Массачусетс: MIT Press
- ^ Секели, Л.А. (1997), «Числа пересечения и сложные проблемы Эрдеша в дискретной геометрии», Combinatorics, Probability and Computing , 6 (3): 353–358, CiteSeerX 10.1.1.134.9842 , doi : 10.1017/S0963548397002976 , MR 14645 71 , S2CID 36602807
- ^ Заранкевич, К. (1954), «К проблеме П. Турана относительно графов», Fundamenta Mathematicae , 41 : 137–145, doi : 10.4064/fm-41-1-137-145 , MR 0063641 .
- ^ Урбаник, К. (1955), «Решение проблемы, поставленной П. Тураном», Colloq. Математика. , 3 : 200–201 . Как цитирует Секели, Ласло А. (2001) [1994], «Гипотеза о числе пересечений Заранкевича» , Энциклопедия математики , EMS Press
- ^ Гай, Ричард К. (1969), «Упадок и падение теоремы Заранкевича», Методы доказательства в теории графов (Труды Второй конференции по теории графов в Анн-Арборе, Анн-Арбор, Мичиган, 1968) , Academic Press, Нью-Йорк, С. 63–69, МР 0253931 .
- ^ Jump up to: а б Клейтман, Дэниел Дж. (1970), «Число пересечения K 5, n », Журнал комбинаторной теории , 9 (4): 315–323, doi : 10.1016/s0021-9800(70)80087-4 , MR 0280403 .
- ^ Вудалл, Д.Р. (1993), «Графы циклического порядка и гипотеза Заранкевича о числе пересечений», Journal of Graph Theory , 17 (6): 657–671, doi : 10.1002/jgt.3190170602 , MR 1244681 .
- ^ Кристиан, Робин; Рихтер, Р. Брюс; Салазар, Геласио (2013), «Гипотеза Заранкевича конечна для каждого фиксированного m », Journal of Combinatorial Theory , Series B, 103 (2): 237–247, doi : 10.1016/j.jctb.2012.11.001 , MR 3018068 .
- ^ де Клерк, Э.; Махарри, Дж.; Пасечник, Д.В.; Рихтер, РБ; Салазар, Г. (2006), «Улучшенные оценки чисел пересечения K m,n и K n », SIAM Journal on Discrete Mathematics , 20 (1): 189–202, arXiv : math/0404142 , doi : 10.1137/ S0895480104442741 , MR 2257255 , S2CID 1509054 .
- ^ Кайнен, Пол К. (1968), «К проблеме П. Эрдеша», Журнал комбинаторной теории , 5 (4): 374–377, doi : 10.1016/s0021-9800(68)80013-4 , MR 0231744