WikiSort.ru - Не сортированное

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

Также известна как проблема Тура́на о кирпичной фабрике (англ. Turan's brick factory problem) — в честь венгерского математика Пала Турана, который сформулировал эту задачу, работая на кирпичной фабрике во время Второй мировой войны.

Польским математиков Казимежем Заранкевичем (польск. Kazimierz Zarankiewicz) была высказана гипотеза, что некоторое простое изображение графа имеет минимальное количество пересечений, однако, за исключений частных случаев, его оптимальность остаётся недоказанной.^[2]

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

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

С точки зрения математики это задача изображения графа на плоскости: печи и склады задают вершины графа, а железнодорожные пути — его рёбра. Поскольку между каждой печью и каждым складом проложен ровно один путь, такой граф является полным двудольным. Если печей p, а складов s, то такой граф обозначается ${\displaystyle K_{p,s}}$ . Проблема Турана состоит в том, чтобы расположить вершины и рёбра графа ${\displaystyle K_{p,s}}$ на плоскости так, чтобы никакая вершина не лежала на ребре, концом которого она не является, и при этом было у ребёр графа минимальное число пересечений, отличных от вершин. При этом рёбра не обязательно должны быть прямолинейными, хотя в решении, которое предполагается минимальным, это так.^[2]

Проблема Турана считается одной из первых задач о минимальном числа пересечений графов.^[3] Частным случаем является классическая математическая задача «Домиков и колодцев», в которой роль печей и складов играют дома и колодцы, каждых — по три штуки.

Попытки решения

Заранкевич и Казимеж Урбаник (польск. Kazimierz Urbanik) присутствовали на докладах Турана в Польше в 1952 году^[4] и независимо опубликовали попытки решения проблемы.^[5]

В обоих случаях они предлагали нарисовать полный двудольный граф следующим образом (см. изображение в начале статьи): нарисовать вершины одного цвета («печи») вдоль вертикальной оси, вершины другого цвета («склады») — вдоль горизонтальной оси, а точку пересечения осей выбрать так, чтобы с каждой стороны находилось поровну (если вершин данного цвета чётно) или почти поровну (если их нечётно). В результате оба получили следующее число пересечений для рёбер графа:

${\displaystyle {\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 }.}$

Этот пример даёт ограничение на число пересечений сверху, однако оба доказательство его минимальности, дающие ограничение снизу, оказались неверны: они были опровергнуты Герхардом Рингелем и Полом Кайненом (англ. Paul Kainen) почти одновременно, в 1965 году^[6]

Хотя в общем случае вопрос минимальности до сих пор остаётся гипотезой, частные случаи были успешно доказаны: случай ${\displaystyle K_{p,s}}$ при ${\displaystyle p\leqslant 3}$ самим Заранкевичем, а позже ${\displaystyle K_{p,s}}$ при ${\displaystyle p\leqslant 6}$ .^[7] Поскольку для любых двух p, s доказательство минимальности требует конечного числа проверок, оно было произведено при достаточно малых p, s.^[8] Также было доказано, что минимальное число пересечений составляет хотя бы 83 % от оценки Заранкевича.^[9]

Примечания

Ссылки

• Weisstein, Eric W. Zarankiewicz's Conjecture (англ.) на сайте Wolfram MathWorld.