Трекл
Тракл — это вложение графа жордановой в плоскость, в котором каждое ребро является дугой и каждая пара ребер пересекается ровно один раз. Ребра могут встречаться либо в общей конечной точке, либо, если у них нет общих конечных точек, в некоторой точке внутри них. В последнем случае они должны пересечься в точке пересечения: пересечение должно быть поперечным . [1]
Особый случай треклов, линейные треклы, ограничивает рисование ребер в виде сегментов прямых линий. Одним из методов построения линейного трекла с любым заданным набором точек в качестве вершин является формирование ребра между каждой самой дальней парой точек. Для линейного трекла каждая компонента связности содержит не более одного цикла, откуда следует, что число ребер не более чем равно числу вершин.
Джон Х. Конвей предположил в более общем плане, что каждый трекл имеет не более чем столько же ребер, сколько и вершин. Известно, что количество ребер не более чем постоянное число вершин.
Линейные треклы
[ редактировать ]
Линейный трекл — это трекл, нарисованный таким образом, что его края представляют собой отрезки прямых линий. Как заметил Пол Эрдеш , каждый линейный трекл имеет не более рёбер, чем вершин. Если вершина v соединена с тремя или более ребрами vw , vx и vy , по крайней мере одно из этих ребер (скажем, vw ) лежит на линии, разделяющей два других ребра. Тогда w должен иметь степень один, потому что ни один отрезок линии, заканчивающийся на w , кроме vw , не может касаться одновременно vx и vy . Удаление w и vw дает меньший трекл без изменения разницы между количеством ребер и вершин. После того, как подобные удаления приводят к треклу, в котором каждая вершина имеет не более двух соседей, согласно лемме о согласовании количество ребер не превышает количества вершин. [2] На основании доказательства Эрдёша можно сделать вывод, что каждый линейный трекл является псевдолесом . Каждый цикл нечетной длины может быть организован так, чтобы сформировать линейный трекл, но это невозможно для цикла четной длины, потому что, если одно ребро цикла выбрано произвольно, тогда другие вершины цикла должны лежать попеременно на противоположных сторонах линии. через этот край.
Миша Перлз предоставил еще одно простое доказательство того, что линейные треклы имеют не более n ребер, основанное на том факте, что в линейных треклах каждое ребро имеет конечную точку, в которой ребра охватывают угол не более 180 ° и для которой это направление наиболее повернуто по часовой стрелке. край внутри этого промежутка. В противном случае существовало бы два ребра, инцидентных противоположным концам ребра и лежащих по разные стороны от прямой, проходящей через ребро, которые не могли бы пересекать друг друга. Но каждая вершина может обладать этим свойством только по отношению к одному ребру, поэтому количество ребер не более чем равно числу вершин. [3]
Как также заметил Эрдеш, набор пар точек, реализующих диаметр набора точек, должен образовывать линейный трекл: никакие два диаметра не могут быть не пересекающимися друг с другом, потому что если бы они были такими, то их четыре конечные точки имели бы пару на большем расстоянии друг от друга. чем два непересекающихся ребра. По этой причине каждый набор из n точек на плоскости может иметь не более n пар диаметров, что отвечает на вопрос, заданный в 1934 году Хайнцем Хопфом и Эрикой Паннвиц . [4] Эндрю Вассони выдвинул гипотезу об ограничении количества пар диаметров в более высоких измерениях, обобщив эту проблему. [2]
В вычислительной геометрии метод вращающихся штангенциркулей можно использовать для формирования линейного трекла из любого набора точек, находящихся в выпуклом положении , путем соединения пар точек, поддерживающих параллельные линии, касательные к выпуклой оболочке точек. [5] Этот граф содержит в качестве подграфа цепочку пар диаметров. [6]
Диаметры многоугольников Рейнхардта образуют линейные треклы. Перечисление линейных треклов можно использовать для решения самой большой задачи о маленьких многоугольниках : найти n -угольник с максимальной площадью относительно его диаметра. [7]
Гипотеза Тракла
[ редактировать ]
Джон Х. Конвей предположил, что в любом трекле количество ребер не более чем равно числу вершин. Сам Конвей использовал терминологию «пути» и «пятна» (для ребер и вершин соответственно), поэтому гипотеза Конвея о трекле. первоначально была сформулирована в форме, что каждый трекл имеет по крайней мере столько же пятен, сколько и дорожек. Конвей предложил приз в размере 1000 долларов за доказательство или опровержение этой гипотезы в рамках набора призовых задач, включая задачу Конвея о 99 графах , минимальное расстояние между наборами Данцера и победителя чеканки монет Сильвера после 16-го хода. [8]
Аналогичным образом можно сформулировать гипотезу о трекле, поскольку каждый трекл является псевдолесом . Более конкретно, если гипотеза о треклах верна, то треклы могут быть точно охарактеризованы с помощью результата Вудала: это псевдолеса, в которых нет цикла длины четыре и не более одного нечетного цикла. [1] [9]
Было доказано, что каждый граф циклов, кроме C 4, имеет вложение трекла, что показывает, что гипотеза точна . То есть существуют траклы, имеющие такое же количество пятен, как и дорожки. С другой стороны, наихудший сценарий состоит в том, что количество пятен в два раза превышает количество путей; это тоже достижимо.
Гипотеза о трекле, как известно, верна для треклов, нарисованных таким образом, что каждое ребро представляет собой x -монотонную кривую, пересекаемую не более одного раза каждой вертикальной линией. [3]
Известные границы
[ редактировать ]Ловас, Пах и Сегеди (1997) доказали, что каждый двудольный трекл представляет собой планарный граф , хотя и не нарисованный плоско. [1] Как следствие, они показывают, что каждый контролируемый граф с n вершинами имеет не более 2 n − 3 ребер. С тех пор эта граница несколько раз улучшалась. Во-первых, оно было улучшено до 3( n − 1)/2, [10] и еще одно улучшение привело к границе примерно 1,428 n . [11] Более того, метод, использованный для доказательства последнего результата, дает для любого ε > 0 конечный алгоритм, который либо улучшает оценку (1 + ε) n или опровергает гипотезу. Текущий рекорд принадлежит Сюй (2021) , который доказал предел 1,393 n . [12]
Если гипотеза неверна, минимальный контрпример будет иметь форму двух четных циклов, имеющих общую вершину. [9] Поэтому для доказательства гипотезы достаточно доказать, что графы такого типа нельзя нарисовать в виде траклов.
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б с Ловас, Л. ; Пах, Дж .; Сегеди, М. (1997), «О гипотезе Конвея о колее», Дискретная и вычислительная геометрия , 18 (4): 369–376, doi : 10.1007/PL00009322 , MR 1476318 . Предварительная версия этих результатов была рассмотрена в О'Рурк, Дж. (1995), «Столбец 26 по вычислительной геометрии», ACM SIGACT News , 26 (2): 15–17, arXiv : cs/9908007 , doi : 10.1145/202840.202842 .
- ^ Jump up to: Перейти обратно: а б Эрдеш, П. (1946), «О наборах расстояний из n точек» (PDF) , American Mathematical Monthly , 53 (5): 248–250, doi : 10.2307/2305092 , JSTOR 2305092 .
- ^ Jump up to: Перейти обратно: а б Пах, Янош ; Стерлинг, Итан (2011), «Гипотеза Конвея о монотонных траклах», American Mathematical Monthly , 118 (6): 544–548, doi : 10.4169/amer.math.monthly.118.06.544 , MR 2812285 , S2CID 17558559 .
- ^ Хопф, Х .; Панвиц, Э. (1934), «Задание № 167», Годовой отчет Ассоциации немецких математиков , 43 : 114 .
- ^ Эппштейн, Дэвид (май 1995 г.), «График вращающегося штангенциркуля» , «Свалка геометрии»
- ^ О том, что график вращающегося штангенциркуля содержит все пары диаметров, см. Шамос, Майкл (1978), Вычислительная геометрия (PDF) , Докторская диссертация, Йельский университет . О том, что пары диаметров образуют трекл, см., например, Pach & Sterling (2011) .
- ^ Грэм, Р.Л. (1975), «Самый большой маленький шестиугольник» (PDF) , Журнал комбинаторной теории , серия A, 18 (2): 165–170, doi : 10.1016/0097-3165(75)90004-7 .
- ^ Конвей, Джон Х. , Пять задач на 1000 долларов (обновление 2017 г.) (PDF) , Интернет-энциклопедия целочисленных последовательностей , получено 12 февраля 2019 г.
- ^ Jump up to: Перейти обратно: а б Вудалл, Д.Р. (1969), «Треклз и тупик», на валлийском языке, DJA (редактор), «Комбинаторная математика и ее приложения» , Academic Press, стр. 335–348, MR 0277421 .
- ^ Кэрнс, Г.; Николаевский Ю. (2000), «Границы для обобщенных треклов», Дискретная и вычислительная геометрия , 23 (2): 191–206, doi : 10.1007/PL00009495 , MR 1739605 .
- ^ Фулек Р.; Пах, Дж. (2011), «Вычислительный подход к гипотезе Конвея о колее», Computational Geometry , 44 (6–7): 345–355, arXiv : 1002.3904 , doi : 10.1007/978-3-642-18469-7_21 , МР 2785903 .
- ^ Сюй, Янь (15 января 2021 г.). «Новая верхняя граница для Траклза Конвея». Прикладная математика и вычислительная техника . 389 : 125573. doi : 10.1016/j.amc.2020.125573 . S2CID 222111854 .
Внешние ссылки
[ редактировать ]- thrackle.org — сайт о проблеме