WikiDer > Проблема кирпичного завода Турана - Википедия

Нерешенная проблема в математике: Можно ли нарисовать полный двудольный граф с меньшим числом пересечений, чем число, указанное Заранкевичем? (больше нерешенных задач по математике)

Оптимальный рисунок K_4,7, с 18 переходами (красные точки)

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

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

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

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

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

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

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

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

${ displaystyle operatorname {cr} (K_ {m, n}) leq { biggl lfloor} { frac {n} {2}} { biggr rfloor} { biggl lfloor} { frac { n-1} {2}} { biggr rfloor} { biggl lfloor} { frac {m} {2}} { biggr rfloor} { biggl lfloor} { frac {m-1} {2}} { biggr rfloor}.}$

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

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

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

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

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

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

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

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

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

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

• Вайсштейн, Эрик В., «Гипотеза Заранкевича», MathWorld