Просмотр кода страницы Проблема Заранкевича

[[Файл:Zarankiewicz K4,7.svg|thumb|upright=1.3|Оптимальное расположения для графа {{math|''K''<sub>4,7</sub>}} имеет 18 пересечений]]
'''Проблема Заранке́вича''' — задача [[Теория графов|теории графов]], связанная с нахождением [[Число пересечений (теория графов)|минимального числа пересечений]] при изображении на плоскости [[Полный двудольный граф|полного двудольного графа]].<ref name=turan>{{citation
 | last = Turan | first = P. | author-link = Pal Turan
 | doi = 10.1002/jgt.3190010105
 | journal = [[Journal of Graph Theory]]
 | pages = 7–9
 | title = A note of welcome
 | volume = 1
 | year = 1977}}.</ref>

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

Польским математиком {{iw|Заранкевич, Казимеж|Казимежем Заранкевичем|en|Kazimierz Zarankiewicz}} была высказана гипотеза, что некоторое простое изображение графа имеет минимальное количество пересечений, однако, за исключением частных случаев, его оптимальность остаётся недоказанной<ref name=ps>{{citation
 | last1 = Pach | first1 = Janos | author1-link = Janos Pach
 | last2 = Sharir | first2 = Micha | author2-link = Micha Sharir
 | contribution = 5.1 Crossings—the Brick Factory Problem
 | pages = 126–127
 | publisher = [[American Mathematical Society]]
 | series = Mathematical Surveys and Monographs
 | title = Combinatorial Geometry and Its Algorithmic Applications: The Alcala Lectures
 | volume = 152
 | year = 2009}}.</ref>.

== Происхождение и формулировка ==
Во время Второй мировой войны [[Венгрия|венгерский]] математик Пал Туран был отправлен на принудительную работу на кирпичную фабрику, где он возил [[Вагонетка|вагонетки]] с кирпичами из печей на склады. На фабрике между любой печью и любым складом были проложены [[Железнодорожный путь|железнодорожные пути]], при этом вагонетку было сложнее толкать там, где эти пути пересекались. Это вдохновило Турана на вопрос о том, как можно перерасположить пути, чтобы минимизировать число пересечений.<ref name=turan/>

С точки зрения математики это задача [[Визуализация графов|изображения графа]] на [[Плоскость|плоскости]]: печи и склады задают вершины графа, а железнодорожные пути — его рёбра. Поскольку между каждой печью и каждым складом проложен ровно один путь, такой граф является [[Полный двудольный граф|полным двудольным]]. Если печей p, а складов s, то такой граф обозначается <math>K_{p, s}</math>. Проблема Турана состоит в том, чтобы расположить вершины и рёбра графа <math>K_{p, s}</math> на плоскости так, чтобы никакая вершина не лежала на ребре, концом которого она не является, и при этом у ребёр графа было минимальное число пересечений, отличных от вершин. При этом рёбра не обязательно должны быть [[Отрезок|прямолинейными]], хотя в решении, которое предполагается минимальным, это так.<ref name=ps/>

Проблема Турана считается одной из первых [[Число пересечений (теория графов)|задач о минимальном числе пересечений графов]].<ref name=foulds>{{citation|title=Graph Theory Applications|first=L. R.|last=Foulds|publisher=Springer|series=Universitext|year=1992|isbn=9781461209331|url=https://books.google.com/books?id=5G4QBwAAQBAJ&pg=PA71|page=71|access-date=2017-09-28|archive-date=2022-07-12|archive-url=https://web.archive.org/web/20220712082150/https://books.google.com/books?id=5G4QBwAAQBAJ&pg=PA71|url-status=dead}}.</ref> Частным случаем является классическая математическая задача «[[Домики и колодцы|Домиков и колодцев]]», в которой роль печей и складов играют дома и колодцы, каждых — по три штуки.

== Попытки решения ==
Заранкевич и Казимеж Урбаник ({{lang-pl|[[:en:Kazimierz Urbanik|Kazimierz Urbanik]]}}) присутствовали на докладах Турана в [[Польша|Польше]] в 1952 году<ref name=early>{{citation
 | last1 = Beineke | first1 = Lowell | author1-link = L. W. Beineke
 | last2 = Wilson | first2 = Robin | author2-link = Robin Wilson (mathematician)
 | doi = 10.1007/s00283-009-9120-4
 | issue = 2
 | journal = [[The Mathematical Intelligencer]]
 | mr = 2657999
 | pages = 41–48
 | title = The early history of the brick factory problem
 | volume = 32
 | year = 2010}}.</ref> и независимо опубликовали попытки решения проблемы.<ref name=urbanik>{{citation
 | last = Urbanik | first = K. | authorlink = Kazimierz Urbanik
 | journal = Colloq. Math.
 | pages = 200–201
 | title = Solution du probleme pose par P. Turan
 | volume = 3
 | year = 1955}}. As cited by {{SpringerEOM|title=Zarankiewicz crossing number conjecture|id=Zarankiewicz_crossing_number_conjecture&oldid=18710|first=Laszlo A.|last=Szekely}}</ref>

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

: <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.</math>

Этот пример даёт ограничение на число пересечений сверху, однако оба доказательства его минимальности, дающие ограничение снизу, оказались неверны: они были опровергнуты [[Герхард Рингель|Герхардом Рингелем]] и Полом Кайненом ({{lang-en|[[:en:Paul Chester Kainen|Paul Kainen]]}}) почти одновременно, в 1965 году<ref name=fall>{{citation
 | last = Guy | first = Richard K. | authorlink = Richard K. Guy
 | contribution = The decline and fall of Zarankiewicz's theorem
 | mr = 0253931
 | pages = 63–69
 | publisher = Academic Press, New York
 | title = Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968)
 | year = 1969}}.</ref>

Хотя в общем случае вопрос минимальности до сих пор остаётся гипотезой, частные случаи были успешно доказаны: случай <math>K_{p, s}</math> при <math>p \leqslant 3</math> самим Заранкевичем, а позже <math>K_{p, s}</math> при <math>p \leqslant 6</math>.<ref name=kleitman>{{citation
 | last = Kleitman | first = Daniel J. | authorlink = Daniel Kleitman
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 0280403
 | pages = 315–323
 | title = The crossing number of {{math|''K''<sub>5,''n''</sub>}}
 | volume = 9
 | year = 1970
 | issue = 4 | doi=10.1016/s0021-9800(70)80087-4}}.</ref>
Поскольку для любых двух p, s доказательство минимальности требует конечного числа проверок, оно было произведено при достаточно малых p, s.<ref name=crs>{{citation
 | last1 = Christian | first1 = Robin
 | last2 = Richter | first2 = R. Bruce
 | last3 = Salazar | first3 = Gelasio
 | doi = 10.1016/j.jctb.2012.11.001
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 3018068
 | pages = 237–247
 | series = Series B
 | title = Zarankiewicz's conjecture is finite for each fixed {{mvar|m}}
 | volume = 103
 | year = 2013}}.</ref>
Также было доказано, что минимальное число пересечений составляет хотя бы 83 % от оценки Заранкевича.<ref name=kmprs>{{citation
 | last1 = de Klerk | first1 = E.
 | last2 = Maharry | first2 = J.
 | last3 = Pasechnik | first3 = D. V.
 | last4 = Richter | first4 = R. B.
 | last5 = Salazar | first5 = G.
 | doi = 10.1137/S0895480104442741
 | issue = 1
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 2257255
 | pages = 189–202
 | title = Improved bounds for the crossing numbers of {{mvar|K<sub>m,n</sub>}} and {{mvar|K<sub>n</sub>}}
 | volume = 20
 | year = 2006| arxiv = math/0404142
 }}.</ref>

== Примечания ==
{{примечания}}

== Ссылки ==
* {{mathworld|urlname=ZarankiewiczsConjecture|title=Zarankiewicz's Conjecture}}

{{DEFAULTSORT:Заранкевич}}
[[Категория:Визуализация графов]]
[[Категория:Топологическая теория графов]]