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

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

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

Примечания

1. Turan, P. (1977), "A note of welcome", Journal of Graph Theory, 1: 7—9, doi:10.1002/jgt.3190010105.
2. Pach, Janos; Sharir, Micha (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.
3. Foulds, L. R. (1992), Graph Theory Applications, Universitext, Springer, p. 71, ISBN 9781461209331, Архивировано из оригинала 12 июля 2022, Дата обращения: 28 сентября 2017.
4. Beineke, Lowell; Wilson, Robin (2010), "The early history of the brick factory problem", The Mathematical Intelligencer, 32 (2): 41—48, doi:10.1007/s00283-009-9120-4, MR 2657999.
5. Urbanik, K. (1955), "Solution du probleme pose par P. Turan", Colloq. Math., 3: 200—201. As cited by Szekely, Laszlo A. (2001), "Zarankiewicz crossing number conjecture", in Hazewinkel, Michiel (ed.), Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
6. 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 0253931.
7. Kleitman, Daniel J. (1970), "The crossing number of K_5,n", Journal of Combinatorial Theory, 9: 315—323, doi:10.1016/s0021-9800(70)80087-4, MR 0280403 {{citation}}: templatestyles stripmarker в |title= на позиции 24 (справка).
8. 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:10.1016/j.jctb.2012.11.001, MR 3018068 {{citation}}: templatestyles stripmarker в |title= на позиции 52 (справка).
9. 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", SIAM Journal on Discrete Mathematics, 20 (1): 189—202, doi:10.1137/S0895480104442741, MR 2257255 {{citation}}: templatestyles stripmarker в |title= на позиции 45 (справка).

Ссылки

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