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

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

Оптимальное расположения для графа $\text{[math]}$ K_4,7 имеет 18 пересечений

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

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

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

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

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

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

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

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

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

\text{[math]}

{\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]

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

ПримечанияПравить

↑ ¹ ² Turan, P. (1977), A note of welcome, Journal of Graph Theory Т. 1: 7–9, DOI 10.1002/jgt.3190010105 .
↑ ¹ ² Pach, Janos & Sharir, Micha (2009), 5.1 Crossings—the Brick Factory Problem, Combinatorial Geometry and Its Algorithmic Applications: The Alcala Lectures, vol. 152, Mathematical Surveys and Monographs, American Mathematical Society, с. 126–127 .
↑ Foulds, L. R. (1992), Graph Theory Applications, Universitext, Springer, с. 71, ISBN 9781461209331, <https://books.google.com/books?id=5G4QBwAAQBAJ&pg=PA71> Архивная копия от 12 июля 2022 на Wayback Machine.
↑ 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 .
↑ 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, 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, с. 63–69 .
↑ Kleitman, Daniel J. (1970), The crossing number of $\text{[math]}$ K_5,n, Journal of Combinatorial Theory Т. 9: 315–323, DOI 10.1016/s0021-9800(70)80087-4 .
↑ Christian, Robin; Richter, R. Bruce & Salazar, Gelasio (2013), Zarankiewicz's conjecture is finite for each fixed $\text{[math]}$ m, Journal of Combinatorial Theory, Series B Т. 103 (2): 237–247, DOI 10.1016/j.jctb.2012.11.001 .
↑ de Klerk, E.; Maharry, J.; Pasechnik, D. V. & Richter, R. B. (2006), Improved bounds for the crossing numbers of $\text{[math]}$ K_m,n and $\text{[math]}$ K_n, SIAM Journal on Discrete Mathematics Т. 20 (1): 189–202, DOI 10.1137/S0895480104442741 .

СсылкиПравить

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

[turan-1] ¹ ² Turan, P. (1977), A note of welcome, Journal of Graph Theory Т. 1: 7–9, DOI 10.1002/jgt.3190010105 .

[ps-2] ¹ ² Pach, Janos & Sharir, Micha (2009), 5.1 Crossings—the Brick Factory Problem, Combinatorial Geometry and Its Algorithmic Applications: The Alcala Lectures, vol. 152, Mathematical Surveys and Monographs, American Mathematical Society, с. 126–127 .

[foulds-3] Foulds, L. R. (1992), Graph Theory Applications, Universitext, Springer, с. 71, ISBN 9781461209331, <https://books.google.com/books?id=5G4QBwAAQBAJ&pg=PA71> Архивная копия от 12 июля 2022 на Wayback Machine.

[early-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 .

[urbanik-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, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4

[fall-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, с. 63–69 .

[kleitman-7] Kleitman, Daniel J. (1970), The crossing number of $\text{[math]}$ K_5,n, Journal of Combinatorial Theory Т. 9: 315–323, DOI 10.1016/s0021-9800(70)80087-4 .

[crs-8] Christian, Robin; Richter, R. Bruce & Salazar, Gelasio (2013), Zarankiewicz's conjecture is finite for each fixed $\text{[math]}$ m, Journal of Combinatorial Theory, Series B Т. 103 (2): 237–247, DOI 10.1016/j.jctb.2012.11.001 .

[kmprs-9] Klerk, E.; Maharry, J.; Pasechnik, D. V. & Richter, R. B. (2006), Improved bounds for the crossing numbers of $\text{[math]}$ K_m,n and $\text{[math]}$ K_n, SIAM Journal on Discrete Mathematics Т. 20 (1): 189–202, DOI 10.1137/S0895480104442741 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]