Трекл
Трекл — вкладення графа в площину так, що кожне ребро є кривою Жордана і кожна пара ребер зустрічається один раз. Ребра можуть мати спільну кінцеву точку, або, якщо спільних кінцевих точок немає, перетинатися у внутрішніх точках. В останньому випадку перетин має бути трансверсальним[1].
Лінійні трекли ред.
Лінійний трекл — трекл, намальований відрізками прямих. Будь-який лінійний трекл має не більше ребер, ніж вершин, що виявив Пал Ердеш. Він помітив, що якщо в лінійному треклі вершина v з'єднана з трьома і більше ребрами vw, vx і vy, то щонайменше одне з цих ребер лежить на прямій, що розділяє два інші ребра. Без втрати загальності припустимо, що таким ребром є vw і точки x і y лежать по різні боки від замкнутих напівпросторів, обмежених прямою vw. Тоді вершина w повинна мати степінь одиниця, оскільки ніяке інше ребро, відмінне від vw, не може мати спільних точок як з vx, так і з vy. Видалення w з трекла дає менший трекл без зміни різниці числа ребер та вершин. З іншого боку, якщо будь-яка вершина має максимум два сусіди, то за лемою про рукостискання число ребер не перевищує числа вершин[2]. Ґрунтуючись на доведенні Ердеша, можна зробити висновок, що будь-який лінійний трекл є псевдолісом. Будь-який цикл непарної довжини можна перетворити в лінійний трекл, але це неможливо для циклів парної довжини, оскільки, якщо вибрати довільне ребро, інші вершини мають лежати по черзі по різні боки від цього ребра.
Міша Перлес[en] навів інше просте доведення, що лінійний трекл має максимум n ребер, ґрунтуючись на факті, що в лінійному треклі будь-яке ребро має кінцеву вершину, в якій усі ребра лежать усередині кута, що не перевищує 180°, для якого дане ребро є початковим (якщо дивитися за годинниковою стрілкою). Якщо це не так, мають бути два ребра, інцидентні протилежним кінцевим вершинам ребра, які лежать по різні боки від прямої, на якій лежить ребро. Але кожна вершина може мати цю властивість лише відносно одного ребра, тому кількість ребер не перевищує кількості вершин[3].
Ердеш також помітив, що множина пар точок, на яких досягається діаметр множини точок, має бути лінійним треклом — ніякі два діаметри не можуть не мати спільних точок, оскільки серед чотирьох кінців цих діаметрів дві точки тоді мають лежати на відстані, більшій за діаметр. З цієї причини будь-яка множина з n точок на площині може мати максимум n діаметральних пар, що є відповіддю на питання, яке поставили 1934 року Хайнц Хопф[ru] і Еріка Панвіц[en][4]. Ендрю Вашоні[en] висловив гіпотезу про межі числа діаметральних пар у вищих розмірностях, узагальнивши проблему[2].
В обчислювальній геометрії за допомогою обертового кронциркуля[en] можна побудувати лінійний трекл із будь-якої множини точок у опуклій позиції[en], з'єднавши пари точок, на які спираються паралельні прямі, дотичні до опуклої оболонки точок. Цей граф містить як підграф трекл діаметральних точок[5]. Перелік лінійних треклів можна використати для розв'язання задачі про найбільший многокутник одиничного діаметра, тобто задача пошуку n-кутника найбільшої площі відносно його діаметра[6].
Гіпотеза про трекл ред.
 |
Нерозв'язана проблема математики: Чи може трекл мати більше ребер, ніж вершин? (більше нерозв'язаних проблем математики)
|
Джон Конвей висловив гіпотезу, що в кожному треклі число ребер не перевищує числа вершин. Сам Конвей використав терміни paths (шляхи) і spots (плями) (замість ребер та вершин відповідно).
Еквівалентно, гіпотезу можна переформулювати як будь-який трекл є псевдолісом. Конкретніше, якщо гіпотеза про трекл істинна, належність до треклів можна точно виразити результатом Вудала — це псевдоліси, в яких немає циклів довжини 4 і є принаймні один непарний цикл[1][7].
Доведено, що будь-який циклічний граф, відмінний від C4 має вкладення у вигляді трекла, що показує, що гіпотеза строга в тому сенсі, що є трекли, в яких число вершин дорівнює числу ребер. Інший крайній випадок, коли число вершин удвічі більше від кількості ребер, також досяжний.
Відомо, що гіпотеза істинна для треклів, намальованих так, що будь-яке ребро є x-монотонною кривою, яка перетинається максимум один раз будь-якою вертикальною лінією[3].
Оцінки ред.
Ловас, Пач та Сегеді[8] довели, що будь-який двочастковий трекл є планарним графом, хоча він і не намальований у планарному вигляді[1]. Як наслідок, вони показали, що будь-який граф із n вершинами має максимум 2n − 3 ребер. З того часу межу покращено двічі. Спочатку її покращено до 3(n − 1)/2[9], а остання відома межа становить близько 1,428n[10]. Більш того, метод, що використовується для отримання результату, дає для будь-якого ε > 0 скінченний алгоритм, який поліпшує межу до (1 + ε)n, або спростовує гіпотезу.
Відомо, що якщо гіпотеза хибна, мінімальним контрприкладом була б пара парних циклів зі спільною вершиною[7]. Отже, на підтвердження гіпотези достатньо довести, що графи цього типу не можна намалювати як трекли.
Примітки ред.
- ↑ а б в Lovász, Pach, Szegedy, 1997, с. 369–376.
- ↑ а б Erdős, 1946, с. 248–250.
- ↑ а б Pach, Sterling, 2011, с. 544–548.
- ↑ Hopf, Pannwitz, 1934, с. 114.
- ↑ Toussaint, 2014, с. 372–386.
- ↑ Graham, 1975, с. 165–170.
- ↑ а б Woodall, 1969, с. 335–348.
- ↑ Lovász, Pach, Szegedy, 1997.
- ↑ Cairns, Nikolayevsky, 2000, с. 191–206.
- ↑ Fulek, Pach, 2011, с. 345–355.
Література ред.
- L. Lovász, J. Pach[en],M. Szegedy [en]. On Conway's thrackle conjecture // Discrete and Computational Geometry. — 1997. — Т. 18, вип. 4. — С. 369–376. — DOI:. Попредню версію цих результатів обговорено в статті
- J. O'Rourke[en]. Computational geometry column 26 // ACM SIGACT News. — 1995. — Т. 26, вип. 2. — С. 15–17. — DOI:.
- D. R. Woodall. Combinatorial Mathematics and Its Applications / D. J. A. Welsh. — Academic Press, 1969. — С. 335–348.
- P. Erdős. On sets of distances of n points // American Mathematical Monthly. — 1946. — Т. 53. — С. 248–250. — DOI:.
- R. L. Graham. The largest small hexagon // Journal of Combinatorial Theory. — 1975. — Т. 18. — С. 165–170. — (Series A). — DOI:.
- H. Hopf, E. Pannwitz[en]. Aufgabe Nr. 167 // Jahresbericht der Deutschen Mathematiker-Vereinigung. — 1934. — Т. 43. — С. 114.
- Godfried Toussaint[en]. Applications of the rotating calipers to geometric problems in two and three dimensions // International Journal of Digital Information and Wireless Communications. — 2014. — Т. 4, вип. 3. — С. 372–386.
- János Pach, Ethan Sterling. Conway's conjecture for monotone thrackles // American Mathematical Monthly. — 2011. — Т. 118, вип. 6. — С. 544–548. — DOI:.
- G. Cairns, Y. Nikolayevsky. Bounds for generalized thrackles // Discrete and Computational Geometry. — 2000. — Т. 23, вип. 2. — С. 191–206. — DOI:.
- R. Fulek, J. Pach. A computational approach to Conway's thrackle conjecture // Computational Geometry. — 2011. — Т. 44, вип. 6-7. — С. 345–355. — DOI:.
Посилання ред.
- thrackle.org — веб-сайт, присвячений треклам