Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Трекл вкладення графа в площину так що кожне ребро є кривою Жордана і кожна пара ребер зустрічається один раз Ребра можу

Трекл

Трекл

Трекл — вкладення графа в площину так, що кожне ребро є кривою Жордана і кожна пара ребер зустрічається один раз. Ребра можуть мати спільну кінцеву точку, або, якщо спільних кінцевих точок немає, перетинатися у внутрішніх точках. В останньому випадку перетин має бути трансверсальним.

Лінійні трекли

Лінійний трекл — трекл, намальований відрізками прямих. Будь-який лінійний трекл має не більше ребер, ніж вершин, що виявив Пал Ердеш. Він помітив, що якщо в лінійному треклі вершина v з'єднана з трьома і більше ребрами vw, vx і vy, то щонайменше одне з цих ребер лежить на прямій, що розділяє два інші ребра. Без втрати загальності припустимо, що таким ребром є vw і точки x і y лежать по різні боки від замкнутих напівпросторів, обмежених прямою vw. Тоді вершина w повинна мати степінь одиниця, оскільки ніяке інше ребро, відмінне від vw, не може мати спільних точок як з vx, так і з vy. Видалення w з трекла дає менший трекл без зміни різниці числа ребер та вершин. З іншого боку, якщо будь-яка вершина має максимум два сусіди, то за лемою про рукостискання число ребер не перевищує числа вершин. Ґрунтуючись на доведенні Ердеша, можна зробити висновок, що будь-який лінійний трекл є псевдолісом. Будь-який цикл непарної довжини можна перетворити в лінійний трекл, але це неможливо для циклів парної довжини, оскільки, якщо вибрати довільне ребро, інші вершини мають лежати по черзі по різні боки від цього ребра.

[en] навів інше просте доведення, що лінійний трекл має максимум n ребер, ґрунтуючись на факті, що в лінійному треклі будь-яке ребро має кінцеву вершину, в якій усі ребра лежать усередині кута, що не перевищує 180°, для якого дане ребро є початковим (якщо дивитися за годинниковою стрілкою). Якщо це не так, мають бути два ребра, інцидентні протилежним кінцевим вершинам ребра, які лежать по різні боки від прямої, на якій лежить ребро. Але кожна вершина може мати цю властивість лише відносно одного ребра, тому кількість ребер не перевищує кількості вершин.

Ердеш також помітив, що множина пар точок, на яких досягається діаметр множини точок, має бути лінійним треклом — ніякі два діаметри не можуть не мати спільних точок, оскільки серед чотирьох кінців цих діаметрів дві точки тоді мають лежати на відстані, більшій за діаметр. З цієї причини будь-яка множина з n точок на площині може мати максимум n діаметральних пар, що є відповіддю на питання, яке поставили 1934 року [ru] і [en]. [en] висловив гіпотезу про межі числа діаметральних пар у вищих розмірностях, узагальнивши проблему.

В обчислювальній геометрії за допомогою [en] можна побудувати лінійний трекл із будь-якої множини точок у [en], з'єднавши пари точок, на які спираються паралельні прямі, дотичні до опуклої оболонки точок. Цей граф містить як підграф трекл діаметральних точок. Перелік лінійних треклів можна використати для розв'язання задачі про найбільший многокутник одиничного діаметра, тобто задача пошуку n-кутника найбільшої площі відносно його діаметра.

Гіпотеза про трекл

image Нерозв'язана проблема математики:
Чи може трекл мати більше ребер, ніж вершин?
(більше нерозв'язаних проблем математики)
image
Вкладення 6-циклу як трекла.

Джон Конвей висловив гіпотезу, що в кожному треклі число ребер не перевищує числа вершин. Сам Конвей використав терміни paths (шляхи) і spots (плями) (замість ребер та вершин відповідно).

Еквівалентно, гіпотезу можна переформулювати як будь-який трекл є псевдолісом. Конкретніше, якщо гіпотеза про трекл істинна, належність до треклів можна точно виразити результатом Вудала — це псевдоліси, в яких немає циклів довжини 4 і є принаймні один непарний цикл.

Доведено, що будь-який циклічний граф, відмінний від C4 має вкладення у вигляді трекла, що показує, що гіпотеза строга в тому сенсі, що є трекли, в яких число вершин дорівнює числу ребер. Інший крайній випадок, коли число вершин удвічі більше від кількості ребер, також досяжний.

Відомо, що гіпотеза істинна для треклів, намальованих так, що будь-яке ребро є x-монотонною кривою, яка перетинається максимум один раз будь-якою вертикальною лінією.

Оцінки

Ловас, Пач та Сегеді довели, що будь-який двочастковий трекл є планарним графом, хоча він і не намальований у планарному вигляді. Як наслідок, вони показали, що будь-який граф із n вершинами має максимум 2n − 3 ребер. З того часу межу покращено двічі. Спочатку її покращено до 3(n − 1)/2, а остання відома межа становить близько 1,428n. Більш того, метод, що використовується для отримання результату, дає для будь-якого ε > 0 скінченний алгоритм, який поліпшує межу до (1 + ε)n, або спростовує гіпотезу.

Відомо, що якщо гіпотеза хибна, мінімальним контрприкладом була б пара парних циклів зі спільною вершиною. Отже, на підтвердження гіпотези достатньо довести, що графи цього типу не можна намалювати як трекли.

Примітки

  1. Lovász, Pach, Szegedy, 1997, с. 369–376.
  2. Erdős, 1946, с. 248–250.
  3. Pach, Sterling, 2011, с. 544–548.
  4. Hopf, Pannwitz, 1934, с. 114.
  5. Toussaint, 2014, с. 372–386.
  6. Graham, 1975, с. 165–170.
  7. Woodall, 1969, с. 335–348.
  8. Lovász, Pach, Szegedy, 1997.
  9. Cairns, Nikolayevsky, 2000, с. 191–206.
  10. Fulek, Pach, 2011, с. 345–355.

Література

  • L. Lovász, [en],[en]. On Conway's thrackle conjecture // . — 1997. — Т. 18, вип. 4. — С. 369–376. — DOI:10.1007/PL00009322. Попредню версію цих результатів обговорено в статті
    • [en]. Computational geometry column 26 // ACM SIGACT News. — 1995. — Т. 26, вип. 2. — С. 15–17. — DOI:10.1145/202840.202842.
  • 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:10.2307/2305092.
  • R. L. Graham. The largest small hexagon // . — 1975. — Т. 18. — С. 165–170. — (Series A). — DOI:10.1016/0097-3165(75)90004-7.
  • , [en]. Aufgabe Nr. 167 // Jahresbericht der Deutschen Mathematiker-Vereinigung. — 1934. — Т. 43. — С. 114.
  • [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:10.4169/amer.math.monthly.118.06.544.
  • G. Cairns, Y. Nikolayevsky. Bounds for generalized thrackles // Discrete and Computational Geometry. — 2000. — Т. 23, вип. 2. — С. 191–206. — DOI:10.1007/PL00009495.
  • R. Fulek, J. Pach. A computational approach to Conway's thrackle conjecture // Computational Geometry. — 2011. — Т. 44, вип. 6-7. — С. 345–355. — DOI:10.1007/978-3-642-18469-7_21.

Посилання

  • thrackle.org — веб-сайт, присвячений треклам

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Trekl vkladennya grafa v ploshinu tak sho kozhne rebro ye krivoyu Zhordana i kozhna para reber zustrichayetsya odin raz Rebra mozhut mati spilnu kincevu tochku abo yaksho spilnih kincevih tochok nemaye peretinatisya u vnutrishnih tochkah V ostannomu vipadku peretin maye buti transversalnim Linijni trekliLinijnij trekl trekl namalovanij vidrizkami pryamih Bud yakij linijnij trekl maye ne bilshe reber nizh vershin sho viyaviv Pal Erdesh Vin pomitiv sho yaksho v linijnomu trekli vershina v z yednana z troma i bilshe rebrami vw vx i vy to shonajmenshe odne z cih reber lezhit na pryamij sho rozdilyaye dva inshi rebra Bez vtrati zagalnosti pripustimo sho takim rebrom ye vw i tochki x i y lezhat po rizni boki vid zamknutih napivprostoriv obmezhenih pryamoyu vw Todi vershina w povinna mati stepin odinicya oskilki niyake inshe rebro vidminne vid vw ne mozhe mati spilnih tochok yak z vx tak i z vy Vidalennya w z trekla daye menshij trekl bez zmini riznici chisla reber ta vershin Z inshogo boku yaksho bud yaka vershina maye maksimum dva susidi to za lemoyu pro rukostiskannya chislo reber ne perevishuye chisla vershin Gruntuyuchis na dovedenni Erdesha mozhna zrobiti visnovok sho bud yakij linijnij trekl ye psevdolisom Bud yakij cikl neparnoyi dovzhini mozhna peretvoriti v linijnij trekl ale ce nemozhlivo dlya cikliv parnoyi dovzhini oskilki yaksho vibrati dovilne rebro inshi vershini mayut lezhati po cherzi po rizni boki vid cogo rebra en naviv inshe proste dovedennya sho linijnij trekl maye maksimum n reber gruntuyuchis na fakti sho v linijnomu trekli bud yake rebro maye kincevu vershinu v yakij usi rebra lezhat useredini kuta sho ne perevishuye 180 dlya yakogo dane rebro ye pochatkovim yaksho divitisya za godinnikovoyu strilkoyu Yaksho ce ne tak mayut buti dva rebra incidentni protilezhnim kincevim vershinam rebra yaki lezhat po rizni boki vid pryamoyi na yakij lezhit rebro Ale kozhna vershina mozhe mati cyu vlastivist lishe vidnosno odnogo rebra tomu kilkist reber ne perevishuye kilkosti vershin Erdesh takozh pomitiv sho mnozhina par tochok na yakih dosyagayetsya diametr mnozhini tochok maye buti linijnim treklom niyaki dva diametri ne mozhut ne mati spilnih tochok oskilki sered chotiroh kinciv cih diametriv dvi tochki todi mayut lezhati na vidstani bilshij za diametr Z ciyeyi prichini bud yaka mnozhina z n tochok na ploshini mozhe mati maksimum n diametralnih par sho ye vidpoviddyu na pitannya yake postavili 1934 roku ru i en en visloviv gipotezu pro mezhi chisla diametralnih par u vishih rozmirnostyah uzagalnivshi problemu V obchislyuvalnij geometriyi za dopomogoyu en mozhna pobuduvati linijnij trekl iz bud yakoyi mnozhini tochok u en z yednavshi pari tochok na yaki spirayutsya paralelni pryami dotichni do opukloyi obolonki tochok Cej graf mistit yak pidgraf trekl diametralnih tochok Perelik linijnih trekliv mozhna vikoristati dlya rozv yazannya zadachi pro najbilshij mnogokutnik odinichnogo diametra tobto zadacha poshuku n kutnika najbilshoyi ploshi vidnosno jogo diametra Gipoteza pro treklNerozv yazana problema matematiki Chi mozhe trekl mati bilshe reber nizh vershin bilshe nerozv yazanih problem matematiki Vkladennya 6 ciklu yak trekla Dzhon Konvej visloviv gipotezu sho v kozhnomu trekli chislo reber ne perevishuye chisla vershin Sam Konvej vikoristav termini paths shlyahi i spots plyami zamist reber ta vershin vidpovidno Ekvivalentno gipotezu mozhna pereformulyuvati yak bud yakij trekl ye psevdolisom Konkretnishe yaksho gipoteza pro trekl istinna nalezhnist do trekliv mozhna tochno viraziti rezultatom Vudala ce psevdolisi v yakih nemaye cikliv dovzhini 4 i ye prinajmni odin neparnij cikl Dovedeno sho bud yakij ciklichnij graf vidminnij vid C4 maye vkladennya u viglyadi trekla sho pokazuye sho gipoteza stroga v tomu sensi sho ye trekli v yakih chislo vershin dorivnyuye chislu reber Inshij krajnij vipadok koli chislo vershin udvichi bilshe vid kilkosti reber takozh dosyazhnij Vidomo sho gipoteza istinna dlya trekliv namalovanih tak sho bud yake rebro ye x monotonnoyu krivoyu yaka peretinayetsya maksimum odin raz bud yakoyu vertikalnoyu liniyeyu OcinkiLovas Pach ta Segedi doveli sho bud yakij dvochastkovij trekl ye planarnim grafom hocha vin i ne namalovanij u planarnomu viglyadi Yak naslidok voni pokazali sho bud yakij graf iz n vershinami maye maksimum 2n 3 reber Z togo chasu mezhu pokrasheno dvichi Spochatku yiyi pokrasheno do 3 n 1 2 a ostannya vidoma mezha stanovit blizko 1 428n Bilsh togo metod sho vikoristovuyetsya dlya otrimannya rezultatu daye dlya bud yakogo e gt 0 skinchennij algoritm yakij polipshuye mezhu do 1 e n abo sprostovuye gipotezu Vidomo sho yaksho gipoteza hibna minimalnim kontrprikladom bula b para parnih cikliv zi spilnoyu vershinoyu Otzhe na pidtverdzhennya gipotezi dostatno dovesti sho grafi cogo tipu ne mozhna namalyuvati yak trekli PrimitkiLovasz Pach Szegedy 1997 s 369 376 Erdos 1946 s 248 250 Pach Sterling 2011 s 544 548 Hopf Pannwitz 1934 s 114 Toussaint 2014 s 372 386 Graham 1975 s 165 170 Woodall 1969 s 335 348 Lovasz Pach Szegedy 1997 Cairns Nikolayevsky 2000 s 191 206 Fulek Pach 2011 s 345 355 LiteraturaL Lovasz en en On Conway s thrackle conjecture 1997 T 18 vip 4 S 369 376 DOI 10 1007 PL00009322 Poprednyu versiyu cih rezultativ obgovoreno v statti en Computational geometry column 26 ACM SIGACT News 1995 T 26 vip 2 S 15 17 DOI 10 1145 202840 202842 D R Woodall Combinatorial Mathematics and Its Applications D J A Welsh Academic Press 1969 S 335 348 P Erdos On sets of distances of n points American Mathematical Monthly 1946 T 53 S 248 250 DOI 10 2307 2305092 R L Graham The largest small hexagon 1975 T 18 S 165 170 Series A DOI 10 1016 0097 3165 75 90004 7 en Aufgabe Nr 167 Jahresbericht der Deutschen Mathematiker Vereinigung 1934 T 43 S 114 en Applications of the rotating calipers to geometric problems in two and three dimensions International Journal of Digital Information and Wireless Communications 2014 T 4 vip 3 S 372 386 Janos Pach Ethan Sterling Conway s conjecture for monotone thrackles American Mathematical Monthly 2011 T 118 vip 6 S 544 548 DOI 10 4169 amer math monthly 118 06 544 G Cairns Y Nikolayevsky Bounds for generalized thrackles Discrete and Computational Geometry 2000 T 23 vip 2 S 191 206 DOI 10 1007 PL00009495 R Fulek J Pach A computational approach to Conway s thrackle conjecture Computational Geometry 2011 T 44 vip 6 7 S 345 355 DOI 10 1007 978 3 642 18469 7 21 Posilannyathrackle org veb sajt prisvyachenij treklam

Дата публікації:
Топ