Проблема Заранкевича

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

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

Польским математиком Казимежем Заранкевичем^[англ.] была высказана гипотеза, что некоторое простое изображение графа имеет минимальное количество пересечений, однако, за исключением частных случаев, его оптимальность остаётся недоказанной^[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.