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

Оптимальное расположения для графа K _4,7 имеет 18 пересечений

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

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

Польским математиком была высказана гипотеза, что некоторое простое изображение графа имеет минимальное количество пересечений, однако, за исключением частных случаев, его оптимальность остаётся недоказанной .

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

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

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

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

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

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

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

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

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

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

Примечания

↑ (1977), "A note of welcome", , 1 : 7—9, doi : .
↑ ; (2009), "5.1 Crossings—the Brick Factory Problem", Combinatorial Geometry and Its Algorithmic Applications: The Alcala Lectures , Mathematical Surveys and Monographs, vol. 152, American Mathematical Society , pp. 126—127 .
Foulds, L. R. (1992), , Universitext, Springer, p. 71, ISBN 9781461209331 от 12 июля 2022 на Wayback Machine .
; (2010), "The early history of the brick factory problem", The Mathematical Intelligencer , 32 (2): 41—48, doi : , MR .
(1955), "Solution du probleme pose par P. Turan", Colloq. Math. , 3 : 200—201 . As cited by Szekely, Laszlo A. (2001), , in Hazewinkel, Michiel (ed.), Encyclopedia of Mathematics , Springer , ISBN 978-1-55608-010-4
Guy, Richard K. (1969), "The decline and fall of Zarankiewicz's theorem", Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) , Academic Press, New York, pp. 63—69, MR .
(1970), "The crossing number of K _{5,

n} ", Journal of Combinatorial Theory , 9 : 315—323, doi : , MR {{ citation }} : templatestyles stripmarker в |title= на позиции 24 ( справка ) .
Christian, Robin; Richter, R. Bruce; Salazar, Gelasio (2013), "Zarankiewicz's conjecture is finite for each fixed m ", Journal of Combinatorial Theory , Series B, 103 (2): 237—247, doi : , MR {{ citation }} : templatestyles stripmarker в |title= на позиции 52 ( справка ) .
de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G. (2006), "Improved bounds for the crossing numbers of K _m,n and K _n ", , 20 (1): 189—202, doi : , MR {{ citation }} : templatestyles stripmarker в |title= на позиции 45 ( справка ) .