Проблема кирпичного завода Турана - Википедия - Turáns brick factory problem

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Можно ли нарисовать полный двудольный граф с меньшим числом пересечений, чем число, указанное Заранкевичем?
(больше нерешенных задач по математике)
Оптимальный рисунок K4,7, с 18 переходами (красные точки)

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

Метод рисования, найденный Казимеж Заранкевич была выдвинута гипотеза, чтобы дать правильный ответ для каждого полного двудольного графа, и утверждение, что это верно, стало известно как Гипотеза о числе пересечения заранкевича. Гипотеза остается открытой, решены лишь некоторые частные случаи.[2]

Происхождение и формулировка

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

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

Формулировка этой проблемы Тураном часто считается одним из первых исследований числа пересечений графиков.[4](Другая самостоятельная формулировка той же концепции произошла в социологии, в методах рисования социограммы,[5] и гораздо более старая головоломка, проблема трех инженерных сетей, можно рассматривать как частный случай проблемы кирпичного завода с тремя печами и тремя хранилищами.[6]) Число переходов с тех пор приобрело большее значение как центральный объект исследования в рисунок графика[7]и как важный инструмент в СБИС дизайн[8]и дискретная геометрия.[9]

Верхняя граница

И Заранкевич, и Казимеж Урбаник видел, как Туран говорил о проблеме кирпичного завода на различных переговорах в Польше в 1952 году,[3]и независимо опубликованные попытки решения проблемы с эквивалентными формулами для количества переходов.[10][11]Как они оба показали, всегда можно построить полный двудольный граф Kм, н (график с м вершины с одной стороны, п вершины на другой стороне, и мин ребер, соединяющих две стороны) с числом пересечений, равным

Конструкция проста: место м вершины на Иксось самолета, избегая источник, с равным или почти равным количеством точек слева и справа от уось. п вершины на у- ось плоскости, минуя начало координат, с равным или почти равным количеством точек над и под Икс-оси. Затем соедините все точки на Икс- ось отрезком прямой до каждой точки на у-ось.[3]

Однако их доказательства того, что эта формула оптимальна, то есть не может быть чертежей с меньшим количеством пересечений, были ошибочными. Пробел был обнаружен только через одиннадцать лет после публикации, почти одновременно Герхард Рингель и Пол Кайнен.[12]Тем не менее предполагается, что формула Заранкевича и Урбаника оптимальна. Это стало известно как гипотеза числа скрещивания Заранкевича. Хотя известно, что некоторые частные его случаи верны, общий случай остается открытым.[2]

Нижние границы

С Kм, н и Kп, м изоморфны, достаточно рассмотреть случай, когда м ≤ п. Кроме того, для м ≤ 2 Конструкция Заранкевича не дает перекрестков, которые, конечно, невозможно преодолеть. Таким образом, единственными нетривиальными случаями являются те, для которых м и п оба ≥ 3.

Попытка доказательства этой гипотезы Заранкевичем, хотя и неверна для общего случая Kм,п, работает на случай м = 3С тех пор он был распространен на другие небольшие значения м, а гипотеза Заранкевича, как известно, верна для полных двудольных графов Kм, н с м ≤ 6.[13]Известно также, что гипотеза верна для K7,7, K7,8, и K7,9.[14]Если существует контрпример, то есть граф Kм, н требуя меньшего количества пересечений, чем граница Заранкевича, то в самом маленьком контрпримере оба м и п должно быть странно.[13]

Для каждого фиксированного выбора м, истинность гипотезы для всех Kм, н можно проверить, проверив только конечное число вариантов выбора п.[15]В более общем плане было доказано, что каждый полный двудольный граф требует количества пересечений, которое (для достаточно больших графов) составляет не менее 83% от числа, заданного границей Заранкевича. Сокращение разрыва между этим нижняя граница и оценка сверху остается открытой проблемой.[16]

Прямолинейные пересечения чисел

Если требуется рисовать ребра как отрезки прямых, а не как произвольные кривые, то для некоторых графов требуется больше пересечений, чем при рисовании с изогнутыми ребрами. Однако верхняя граница, установленная Заранкевичем для числа пересечений полных двудольных графов, может быть достигается за счет использования только прямых кромок. Следовательно, если гипотеза Заранкевича верна, то полные двудольные графы имеют прямолинейные числа пересечений, равные их номерам пересечений.[17]

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

  1. ^ а б Туран, П. (1977), «Приветствие», Журнал теории графов, 1: 7–9, Дои:10.1002 / jgt.3190010105.
  2. ^ а б c Пах, Янош; Шарир, Миха (2009), «5.1 Переходы - проблема кирпичного завода», Комбинаторная геометрия и ее алгоритмические приложения: лекции по Алкале, Математические обзоры и монографии, 152, Американское математическое общество, стр. 126–127.
  3. ^ а б c Бейнеке, Лоуэлл; Уилсон, Робин (2010), «Ранняя история проблемы кирпичного завода», Математический интеллект, 32 (2): 41–48, Дои:10.1007 / s00283-009-9120-4, МИСТЕР  2657999.
  4. ^ Фулдс, Л. Р. (1992), Приложения теории графов, Universitext, Springer, стр. 71, ISBN  9781461209331.
  5. ^ Бронфенбреннер, Ури (1944), «Графическое представление социометрических данных», Социометрия, 7 (3): 283–289, Дои:10.2307/2785096, JSTOR  2785096, Расположение предметов на диаграмме, хотя отчасти случайное, определяется в основном методом проб и ошибок с целью минимизировать количество пересекающихся линий.
  6. ^ Бона, Миклош (2011), Обзор комбинаторики: введение в теорию перечисления и графов, World Scientific, стр. 275–277, ISBN  9789814335232. Бона представляет головоломку (в виде трех домов, соединенных с тремя колодцами) на стр. 275, и пишет на стр. 277, что это «эквивалентно проблеме рисования. K3,3 на ровной поверхности без пересечений ».
  7. ^ Шефер, Маркус (2014), «Число пересечений графа и его варианты: обзор», Электронный журнал комбинаторики: # DS21CS1 maint: ref = harv (связь)
  8. ^ Лейтон, Т. (1983), Проблемы сложности в СБИС, Основы вычислительной серии, Кембридж, Массачусетс: MIT Press
  9. ^ Секели, Л. А. (1997), "Пересечения чисел и сложные задачи Эрдеша в дискретной геометрии", Комбинаторика, теория вероятностей и вычисления, 6 (3): 353–358, Дои:10.1017 / S0963548397002976, МИСТЕР  1464571
  10. ^ Заранкевич, К. (1954), «К проблеме П. Турана о графах», Fundamenta Mathematicae, 41: 137–145, МИСТЕР  0063641.
  11. ^ Урбаник, К. (1955), "Решение проблемы после П. Турана", Коллок. Математика., 3: 200–201. Как цитирует Секели, Ласло А. (2001) [1994], "Гипотеза числа скрещивания Заранкевича", Энциклопедия математики, EMS Press
  12. ^ Гай, Ричард К. (1969), «Упадок и падение теоремы Заранкевича», Методы доказательства в теории графов (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, New York, pp. 63–69, МИСТЕР  0253931.
  13. ^ а б Клейтман, Дэниел Дж. (1970), «Число пересечений K5,п", Журнал комбинаторной теории, 9: 315–323, Дои:10.1016 / с0021-9800 (70) 80087-4, МИСТЕР  0280403.
  14. ^ Вудал, Д. Р. (1993), "Графы циклического порядка и гипотеза о пересечении чисел Заранкевича", Журнал теории графов, 17 (6): 657–671, Дои:10.1002 / jgt.3190170602, МИСТЕР  1244681.
  15. ^ Кристиан, Робин; Рихтер, Р. Брюс; Салазар, Геласио (2013), «Гипотеза Заранкевича конечна для каждого фиксированного м", Журнал комбинаторной теории, Серия B, 103 (2): 237–247, Дои:10.1016 / j.jctb.2012.11.001, МИСТЕР  3018068.
  16. ^ de Klerk, E .; Maharry, J .; Пасечник, Д. В .; Richter, R. B .; Салазар, Г. (2006), "Улучшенные оценки числа пересечений Kм, н и Kп", Журнал SIAM по дискретной математике, 20 (1): 189–202, arXiv:математика / 0404142, Дои:10.1137 / S0895480104442741, МИСТЕР  2257255.
  17. ^ Кайнен, Пол К. (1968), «К проблеме П. Эрдеша», Журнал комбинаторной теории, 5: 374–377, Дои:10.1016 / с0021-9800 (68) 80013-4, МИСТЕР  0231744

внешняя ссылка