В математике рисования графов задача кирпичного завода Турана требует минимального числа пересечений в рисунке полного двудольного графа . Задача названа в честь Пала Турана , который сформулировал ее , будучи вынужденным работать на кирпичном заводе во время Второй мировой войны. [1]
Метод рисования, найденный Казимежем Заранкевичем, был выдвинут как гипотеза, дающая правильный ответ для каждого полного двудольного графа, и утверждение, что это верно, стало известно как гипотеза Заранкевича о числе пересечений . Гипотеза остается открытой, и решены только некоторые частные случаи. [2]
Во время Второй мировой войны венгерский математик Пал Туран был вынужден работать на кирпичном заводе, толкая вагоны с кирпичами от печей к местам хранения. На заводе были рельсы от каждой печи к каждому месту хранения, и вагоны было труднее толкать в точках, где рельсы пересекались. Туран был вдохновлен этой ситуацией, чтобы задаться вопросом, как можно перепроектировать завод, чтобы минимизировать количество пересечений между этими рельсами. [1]
Математически эта задача может быть формализована как запрос на чертеж полного двудольного графа , вершины которого представляют печи и места хранения, а ребра представляют пути от каждой печи к каждому месту хранения. Граф должен быть нарисован на плоскости, где каждая вершина является точкой, каждое ребро — кривой, соединяющей две его конечные точки, и ни одна вершина не должна быть размещена на ребре, которому она не принадлежит. Пересечение считается всякий раз, когда два ребра, которые не пересекаются в графе, имеют непустое пересечение на плоскости. Тогда возникает вопрос, каково минимальное количество пересечений на таком чертеже? [2] [3]
Формулировка этой проблемы Тураном часто признается одним из первых исследований чисел пересечения графов . [4] (Другая независимая формулировка той же концепции появилась в социологии, в методах построения социограмм , [5] и гораздо более старая головоломка, задача о трех полезностях , может рассматриваться как частный случай задачи о кирпичном заводе с тремя печами и тремя складскими помещениями. [6] ) С тех пор числа пересечения приобрели большую значимость как центральный объект изучения в рисовании графов [7] и как важный инструмент в проектировании СБИС [8] и дискретной геометрии . [9]
И Заранкевич, и Казимеж Урбаник видели, как Туран говорил о задаче о кирпичном заводе в разных докладах в Польше в 1952 году [3] , и независимо друг от друга опубликовали попытки решения этой задачи с эквивалентными формулами для числа пересечений. [10] [11] Как они оба показали, всегда можно нарисовать полный двудольный граф K m,n (граф с m вершинами на одной стороне, n вершинами на другой стороне и mn ребрами, соединяющими две стороны) с числом пересечений, равным
Конструкция проста: поместите m вершин на оси x плоскости, избегая начала координат , с равным или почти равным количеством точек слева и справа от оси y . Аналогично, поместите n вершин на оси y плоскости, избегая начала координат, с равным или почти равным количеством точек выше и ниже оси x . Затем соедините каждую точку на оси x отрезком прямой линии с каждой точкой на оси y . [3]
Однако их доказательства того, что эта формула оптимальна, то есть что не может быть рисунков с меньшим количеством пересечений, были ошибочными. Разрыв был обнаружен только через одиннадцать лет после публикации, почти одновременно Герхардом Рингелем и Полом Кайненом . [12] Тем не менее, предполагается, что формула Заранкевича и Урбаника оптимальна. Это стало известно как гипотеза Заранкевича о числе пересечений. Хотя некоторые ее частные случаи, как известно, верны, общий случай остается открытым. [2]
Поскольку K m,n и K n,m изоморфны, достаточно рассмотреть случай, когда m ≤ n . Кроме того, при m ≤ 2 конструкция Заранкевича не дает никаких пересечений, что, конечно, не может быть превзойдено. Так что единственными нетривиальными случаями являются те, для которых m и n оба ≥ 3 .
Попытка доказательства Заранкевичем этой гипотезы, хотя и недействительная для общего случая K m , n , работает для случая m = 3 . С тех пор она была распространена на другие малые значения m , и известно, что гипотеза Заранкевича верна для полных двудольных графов K m,n с m ≤ 6 . [13] Известно также, что гипотеза верна для K 7,7 , K 7,8 и K 7,9 . [14] Если существует контрпример, то есть граф K m,n , требующий меньшего количества пересечений, чем граница Заранкевича, то в наименьшем контрпримере и m , и n должны быть нечетными. [13]
Для каждого фиксированного выбора m истинность гипотезы для всех K m,n может быть проверена путем проверки только конечного числа выборов n . [15] В более общем смысле, было доказано, что каждый полный двудольный граф требует числа пересечений, которое (для достаточно больших графов) составляет по крайней мере 83% от числа, заданного границей Заранкевича. Закрытие разрыва между этой нижней границей и верхней границей остается открытой проблемой. [16]
Если ребра должны быть нарисованы как прямолинейные сегменты, а не как произвольные кривые, то некоторым графам требуется больше пересечений, чем при рисовании с изогнутыми ребрами. Однако верхняя граница, установленная Заранкевичем для чисел пересечений полных двудольных графов, может быть достигнута с использованием только прямых ребер. Следовательно, если гипотеза Заранкевича верна, то полные двудольные графы имеют прямолинейные числа пересечений, равные их числам пересечений. [17]
Расположение субъектов на диаграмме, хотя и бессистемно отчасти, в значительной степени определяется методом проб и ошибок с целью минимизации количества пересекающихся линий.
