Топологиялық график - Topological graph

Бұл мақала жазықтыққа салынған, қиылыстары бар графиктер туралы. Басқа беттерге графикалық ендіру туралы ақпаратты қараңыз топологиялық графизм теориясы.
13 тақ тақтасымен және 15 жұптық қиылысумен график.[1]

Жылы математика, а топологиялық график болып табылады график ішінде ұшақ, қайда төбелер графиктің нақты нүктелері және шеттері арқылы Иордан доғалары (байланыстырылған бөліктер) Иордания қисықтары ) сәйкес нүктелер жұбын біріктіру. Графтың төбелерін бейнелейтін нүктелер және оның шеттерін бейнелейтін доғалар деп аталады төбелер және шеттері топологиялық график. Әдетте топологиялық графиктің кез-келген екі шеті ақырғы рет кесіп өтеді, оның шетінен өзгеше шыңнан бірде-бір шеті өтпейді және екі шеті бір-біріне тиіп кетпейді (қиылыспай) деп есептеледі. Топологиялық графикті а деп те атайды сурет салу график.

Топологиялық графиктің маңызды арнайы класы - класы геометриялық графиктер, жиектері көрсетілген сызық сегменттері. (Термин геометриялық график кейде кеңірек, біршама түсініксіз мағынада қолданылады.)

Топологиялық графиктердің теориясы - графтар теориясы, негізінен қатысты комбинаторлық топологиялық графиктердің қасиеттері, атап айтқанда олардың шеттерінің айқасу заңдылықтары. Бұл тығыз байланысты графикалық сурет, неғұрлым қолдануға бағытталған өріс, және топологиялық графизм теориясы, ол графиктің беттерге енуіне (яғни қиылысусыз сызбаларға) бағытталған.

Топологиялық графиктер үшін экстремалды мәселелер

Ішіндегі негізгі проблема экстремалды графтар теориясы келесі: графиктің ең көп шеттері қаншаға тең n егер оның берілген класына жататын подограф болмаса, шыңдар болуы мүмкін тыйым салынған ішкі суреттер? Мұндай нәтижелердің прототипі болып табылады Туран теоремасы, онда бір тыйым салынған ішкі графика бар: толық график к шыңдар (к бекітілген) Топологиялық және геометриялық графиктерге ұқсас сұрақтар қоюға болады, олардың айырмашылықтары қазір анық геометриялық ішкі конфигурациялар тыйым салынған.

Тарихи тұрғыдан мұндай теореманың бірінші сатысы байланысты Paul Erdős, кім нәтиже берді Хайнц Хопф және Эрика Паннвиц.[2] Ол геометриялық графиктің жиектерінің максималды санын дәлелдеді n > 2 шыңды қамтуы мүмкін екі шеті (бұл тіпті соңғы нүктемен бөлісе алмайды) n. Джон Конвей бұл тұжырымды қарапайым топологиялық графиктермен жалпылауға болады деп болжайды. Топологиялық график «қарапайым» деп аталады, егер оның шеттерінің кез-келген жұбы ең көп дегенде бір нүктеге ие болса, бұл не шеткі немесе екі жиек дұрыс қиылысатын жалпы ішкі нүкте болса. Конвейдікі тарсылдау болжамды келесідей түрде қайта құруға болады: қарапайым топологиялық график n > 2 шың, ал екі шеті де көп емес n шеттері.

Мұндай графиктің жиектерінің бірінші сызықтық жоғарғы шегі бойынша белгіленді Ловаш т.б..[3]Ең жақсы белгілі жоғарғы шекара, 1.428n, Фулек және Пач.[4] Геометриялық графиктерден басқа, Конвейдің трекклиникалық болжамдары шындыққа сәйкес келеді х-монотонды топологиялық графиктер.[5] Топологиялық график деп аталады х-монотонды егер әрбір тік сызық әр жиекті ең көп дегенде бір нүктемен қиып өтсе.

Алон және Ердо[6] тыйым салынған конфигурациядан тұратын жағдайға жоғарыдағы сұрақты жалпылауды тергеуді бастады к аралық шеттер (к > 2). Геометриялық графигінің жиектерінің саны екенін дәлелдеді n3 шегі жоқ шыңдар O(n). Шамамен 2,5 шекті шекараn Черныймен анықталды.[7]Үлкен мәндері үшін к, бірінші сызықтық жоғарғы шекара, , Pach және Töröcsik құрды.[8] Мұны Tóth жетілдірді .[9]Жоқ қарапайым топологиялық графиктің жиектерінің саны үшін к шеттер, тек қана жоғарғы шекара белгілі.[10] Бұл дегеніміз - әрбір қарапайым топологиялық график n шыңдарда кем дегенде бар жақсартылған шеттерін екі-екіден қиып өту Руис-Варгас.[11] Бұл төменгі шекараны одан әрі жақсартуға болатын шығар cn, қайда в > 0 тұрақты.

Квази-жоспарлы графиктер

Бірінші жиек екінші жиектің бір жағынан екінші шетіне өтетін екі жиектің жалпы ішкі нүктесі а деп аталады өту. Топологиялық графиктің екі шеті крест егер олар өткелді анықтаса, бір-біріне. Кез келген бүтін сан үшін к > 1, топологиялық немесе геометриялық график деп аталады k-квази-жазықтық егер ол жоқ болса к Осы терминологияны қолданып, егер топологиялық график 2 квази-жазықтық болса, онда ол жазықтық график.Ол келесіден шығады Эйлердің көпжақты формуласы әрбір жазықтық график n > 2 шыңда ең көп дегенде 3 боладыn - 6 шеті. Сондықтан әрбір 2 квази-жоспарлы график n > 2 шыңда ең көп дегенде 3 боладыn - 6 шеті.

Оны Пач және басқалар жорамалдаған.[12] бұл әрқайсысы к- квази-жоспарлы топологиялық график n шыңдар ең көп дегенде в(к)nшеттері, қайда в(к) тек тәуелді тұрақты болып табылады к. Бұл болжам шындыққа сәйкес келетіні белгілі к = 3[13][14] және к = 4.[15] Ол үшін де шындық екені белгілі дөңес геометриялық графиктер (бұл геометриялық графиктер үшін, олардың төбелері дөңес шыңдар жиынын құрайды n-жон),[16] және үшін к- жиектері сызылған квази-жоспарлы топологиялық графиктер х-монотонды қисықтар, олардың барлығы тік сызықты кесіп өтеді.[17][18]Соңғы нәтиже әрқайсысын білдіреді к- квази-жоспарлы топологиялық график n шеттері ретінде сызылған төбелер х-монотонды қисықтар максимумға ие в(к)n журналn тұрақты шектер үшін в(к). Геометриялық графиктер үшін мұны Вальтр ертерек дәлелдеді.[19] Ең танымал генерал жоғарғы шекара а жиектерінің саны үшін к- квази-жоспарлы топологиялық график .[20]

Сандарды айқастыру

Содан бері Пал Туран ойлап тапқан оның кірпіш зауытының проблемасы[21] кезінде Екінші дүниежүзілік соғыс, графиктердің қиылысқан сандарын анықтау немесе бағалау графика теориясында және алгоритмдер теориясында танымал тақырып болды.[22] Алайда тақырыптағы басылымдарда (анық немесе жасырын түрде) айқас сандардың бірнеше бәсекелес анықтамалары қолданылған. Мұны Пач пен Тот атап өтті,[23] келесі терминологияны кім енгізген.

Айқасу нөмірі (графиктің) G): Барлық сызбалар бойынша өту нүктелерінің минималды саны G жазықтықта (яғни оның барлық көріністері топологиялық граф ретінде) бір нүктеден үш шеті өтпейтін қасиеті бар. Ол cr (G).

Жұптасу нөмірі: Барлық сызбалардың үстінен қиылысатын жұп жиектердің минималды саны G. Ол жұппен белгіленеді-cr (G).

Тақ айқасқан нөмір: Барлық сызбалардың үстінен тақ сан рет кесіп өтетін шеттердің жұптарының минималды саны G. Ол тақ-cr арқылы белгіленеді (G).

Бұл параметрлер өзара байланысты емес. Біреуі тақ-кр (G≤ жұп-cr (G) ≤ cr (G) әрбір график үшін G. Cr (G) ≤ 2 (тақ-cr (G))2[23] және [24]және жұп-cr (үшін) шексіз көптеген графиктер барG≠ тақ-кр (G).[1] Өтпелі нөмір мен жұптасу нөмірі бірдей емес мысалдар белгілі емес. Бұл Ханани – Тутте теоремасы[25][26] сол тақ-Cr (G) = 0 білдіреді (G) = 0. Сонымен қатар тақ-Cr (G) = к білдіреді cr (G) = k үшін к = 1, 2, 3.[27]Жақсы зерттелген графиктің тағы бір параметрі келесі.

Түзу сызықты қиылысу нөмірі: Барлық түзу сызбалар бойынша қиылысу нүктелерінің минималды саны G жазықтықта (яғни оның барлық көріністері геометриялық график түрінде) бір нүктеден үш шеті өтпейтін қасиеті бар. Ол lin-cr арқылы белгіленеді (G).

Анықтама бойынша біреуінде cr (G≤ lin-cr (G) әрбір график үшін G. Биеншток пен декан 4 қиылысы бар графиктердің бар екенін және ерікті түрде үлкен сызықты қиылысу нөмірі бар екенін көрсетті.[28]

Геометриялық графикаға арналған рамзи типтес есептер

Дәстүрлі түрде графтар теориясы, типтік Рамзи түріндегі нәтиже егер біз жеткілікті үлкен толық графиктің шеттерін белгіленген түстер санымен боясақ, онда міндетті түрде а табамыз монохроматикалық белгілі бір типтегі субография.[29] Геометриялық (немесе топологиялық) графиктерге ұқсас сұрақтар қоюға болады, тек қазір біз белгілі бір геометриялық шарттарды қанағаттандыратын монохроматикалық (бір түсті) құрылымдарды іздейміз.[30]Осы түрдегі алғашқы нәтижелердің бірі, шеттері екі түске боялған әрбір толық геометриялық графикте қиылыспайтын монохроматтық болады ағаш.[31] Әрбір осындай геометриялық графикте болатыны ақиқат бірдей түсті жиектер.[31] Ең болмағанда қиылыспайтын монохроматтық жолдың болуы cn, қайда в > 0 - тұрақты, бұрыннан бар ашық мәселе. Әрбір толық геометриялық графиктің болатыны белгілі n шыңдарда ең болмағанда ұзындығы қиылыспайтын монохроматикалық жол бар .[32]

Топологиялық гиперография

Егер топологиялық графикті 1-өлшемді топологиялық іске асыру ретінде қарастырсақ қарапайым кешен, жоғарыда аталған экстремалды және Рамзи типтегі мәселелер топологиялық іске асырумен қалай жалпылайтындығы туралы сұрақ туындауы заңды г.-өлшемді жеңілдетілген кешендер. Бұл бағытта алғашқы нәтижелер бар, бірақ негізгі түсініктер мен проблемаларды анықтау үшін қосымша зерттеулер қажет.[33][34][35]

Екі шыңға бөлінетін қарапайым деп аталады крест егер олардың салыстырмалы интерьерінің ортақ нүктесі болса. Жиынтығы к > 3 қарапайым қатты айқасу егер олардың екеуі де шыңмен бөліспесе, бірақ олардың салыстырмалы интерьерінің нүктесі ортақ болса.

Жиынтығы екені белгілі г.- өлшемді қарапайымдылық n нүктелер Қарапайым қарапайым жұпсыз ең көп дегенде болуы мүмкін қарапайым және бұл шекара асимптоталық түрде тығыз.[36] Бұл нәтиже екі өлшемді қарапайым жиынтықтарына жинақталды үш қатты қиылысатын қарапайым.[37]Егер біз тыйым салсақ к Қарапайымдылықтарды кесіп өту, сәйкесінше ең жақсы белгілі жоғарғы шекара ,[36] кейбіреулер үшін . Бұл нәтиже түрлі-түсті болады Тверберг теоремасы.[38] Бұл болжамды шекарадан алыс .[36]

Кез келген бекітілген үшін к > 1, біз ең көп таңдай аламыз г.жиынтығынан тұратын өлшемді қарапайымдықтар n ұпай жоқ мүлкімен к олардың жалпы ішкі нүктесі бар.[36][39] Бұл асимптотикалық түрде тығыз.

Екі үшбұрыш деп айтылады дерлік бөлінеді егер олар бөлінген болса немесе олар тек бір шыңды бөліссе. Бұл ескі проблема Гил Калай және басқалары кейбір шыңдар жиынтығында таңдалатын дерлік үшбұрыштардың ең көп саны туралы шешім қабылдау n ұпай болып табылады . Жиындарының бар екендігі белгілі n бұл сан кем дегенде болатын ұпайлар қолайлы тұрақты үшін в > 0.[40]

Әдебиеттер тізімі

  1. ^ а б Пельсмажер, Майкл Дж .; Шефер, Маркус; Штефанкович, Даниэль (2008 ж.), «Тақ қиылысу нөмірі мен қиылысу нөмірі бірдей емес», Дискретті және есептеу геометриясы, 39 (1–3): 442–454, дои:10.1007 / s00454-008-9058-x Осы нәтижелердің алдын-ала нұсқасы қаралды Proc. Графикалық сурет салу бойынша 13-ші халықаралық симпозиум, 2005, 386-396 бет, дои:10.1007/11618058_35.
  2. ^ Хопф, Хайнц; Паннвиц, Эрика (1934), «Aufgabe nr. 167», Jahresbericht der Deutschen Mathematiker-Vereinigung, 43: 114
  3. ^ Ловас, Ласло; Пач, Янос; Сегеди, Марио (1997), «Конвейдің трек жорамалында», Дискретті және есептеу геометриясы, Springer, 18 (4): 369–376, дои:10.1007 / PL00009322
  4. ^ Фулек, Радослав; Пач, Янос (2011), «Конвейдің трекпектік болжамына есептеу әдісі», Есептеу геометриясы, 44 (6–7): 345–355, arXiv:1002.3904, дои:10.1007/978-3-642-18469-7_21, МЫРЗА  2785903
  5. ^ Пач, Янос; Стерлинг, Этан (2011 ж.), «Конвейдің монотонды трекпуль туралы болжамы», Американдық математикалық айлық, 118 (6): 544–548, дои:10.4169 / amer.math.monthly.118.06.544, МЫРЗА  2812285, S2CID  17558559
  6. ^ Алон, Нога; Эрдоус, Пауыл (1989), «Геометриялық графиктердегі жиектердің бөлінуі», Дискретті және есептеу геометриясы, 4 (4): 287–290, дои:10.1007 / bf02187731
  7. ^ Černý, Jakub (2005), «Үш шеті жоқ геометриялық графиктер», Дискретті және есептеу геометриясы, 34 (4): 679–695, дои:10.1007 / s00454-005-1191-1
  8. ^ Пач, Янос; Töröcsik, Jenö (1994), «Дилворт теоремасының кейбір геометриялық қосымшалары», Дискретті және есептеу геометриясы, 12: 1–7, дои:10.1007 / BF02574361
  9. ^ Тот, Геза (2000), «Геометриялық графиктер туралы ескерту», Комбинаторлық теория журналы, А сериясы, 89 (1): 126–132, дои:10.1006 / jcta.1999.3001
  10. ^ Пач, Янос; Tóth, Géza (2003), «Топологиялық графикадағы шеттер», Комбинаторлық геометрия және график теориясы: Индонезия-Жапония бірлескен конференциясы, IJCCGGT 2003, Бандунг, Индонезия, 2003 жылғы 13-16 қыркүйек, қайта қаралған таңдамалы мақалалар (PDF), Информатикадағы дәрістер, 3330, Springer-Verlag, 133–140 бб., дои:10.1007/978-3-540-30540-8_15
  11. ^ Дж. Руис-Варгас, Андрес (2015), Топологиялық графиктердегі көптеген шектер, 50, 29-34 бет, arXiv:1412.3833, дои:10.1016 / j.endm.2015.07.006
  12. ^ Пач, Янос; Шахрохи, Фархад; Сегеди, Марио (1996), «Өтетін нөмірдің қосымшалары», Алгоритмика, Springer, 16 (1): 111–117, дои:10.1007 / BF02086610, S2CID  20375896
  13. ^ Агарваль К., Панкай; Аронов, Борис; Пач, Янос; Поллак, Ричард; Шарир, Миха (1997), «квази-жоспарлы графиктердің жиектерінің сызықтық саны бар», Комбинаторика, 17: 1–9, дои:10.1007 / bf01196127, S2CID  8092013
  14. ^ Аккерман, Эял; Tardos, Gábor (2007), «квази-жоспарлы графиктердегі жиектердің максималды саны туралы», Комбинаторлық теория журналы, А сериясы, 114 (3): 563–571, дои:10.1016 / j.jcta.2006.08.002
  15. ^ Аккерман, Эял (2009 ж.), «Топологиялық графикадағы жиектердің максималды саны туралы, олардың төрт жұптық қиылысқан шеттері жоқ», Дискретті және есептеу геометриясы, 41 (3): 365–375, дои:10.1007 / s00454-009-9143-9
  16. ^ Капойлеас, Василис; Пач, Янос (1992), «Дөңес көпбұрыш аккордтарындағы Туран типтес теорема», Комбинаторлық теория журналы, B сериясы, 56 (1): 9–15, дои:10.1016 / 0095-8956 (92) 90003-G
  17. ^ Сук, Эндрю (2011) »к- квази-жоспарлы графиктер », Графикалық сурет: 19-халықаралық симпозиум, GD 2011, Эйндховен, Нидерланды, 21-23 қыркүйек, 2011, Қайта өңделген таңдалған құжаттар, Информатикадағы дәрістер, 7034, Springer-Verlag, 266–277 б., arXiv:1106.0958, дои:10.1007/978-3-642-25878-7_26, S2CID  18681576
  18. ^ Түлкі, Джейкоб; Пач, Янос; Сук, Эндрю (2013), «Шеттер саны к- квази-жоспарлы графиктер », Дискретті математика бойынша SIAM журналы, 27 (1): 550–561, arXiv:1112.2361, дои:10.1137/110858586, S2CID  52317.
  19. ^ Вальтр, Павел (1997), «Жоқ графикалық сурет к жиектерді жұптастыру », Графикалық сурет: 5-ші Халықаралық симпозиум, GD '97 Рим, Италия, 1997 ж. 18-20 қыркүйек, Процесс, Информатикадағы дәрістер, 1353, Springer-Verlag, 205–218 бб
  20. ^ Түлкі, Джейкоб; Пач, Янос (2012), «Бояу - геометриялық объектілердің жазықтықтағы қиылысу графиктері », Еуропалық Комбинаторика журналы, 33 (5): 853–866, дои:10.1016 / j.ejc.2011.09.021 Осы нәтижелердің алдын-ала нұсқасы жарияланды Proc. Есептеу геометриясы бойынша симпозиум (PDF), 2008, 346–354 б., дои:10.1145/1377676.1377735, S2CID  15138458
  21. ^ Туран, Павел (1977), «Қош келдіңіз», Графикалық теория журналы, 1: 7–9, дои:10.1002 / jgt.3190010105
  22. ^ Гарей, М.; Джонсон, Д.С. (1983 ж.), «Жолдың қиылысқан нөмірі толық», SIAM журналы алгебралық және дискретті әдістер туралы, 4 (3): 312–316, дои:10.1137/0604033, МЫРЗА  0711340CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме) CS1 maint: ref = harv (сілтеме)
  23. ^ а б Пач, Янос; Tóth, Géza (2000), «Бұл қай жолдың нөмірі?», Комбинаторлық теория журналы, B сериясы, 80 (2): 225–246, дои:10.1006 / jctb.2000.1978
  24. ^ Matoušek, Jiří (2014), «Жол графиктеріндегі оңтайлы сепараторлар», Комбин. Пробаб. Есептеу., 23, 135-139 бет, arXiv:1302.6482, дои:10.1017 / S0963548313000400, S2CID  2351522
  25. ^ Chojnacki (Hanani), Chaim (Haim) (1934), «Uber wesentlich unplattbar Kurven im dreidimensionale Raume», Fundamenta Mathematicae, 23: 135–142, дои:10.4064 / fm-23-1-135-142
  26. ^ Тютте, Уильям Т. (1970), «Сандарды айқындау теориясына», Комбинаторлық теория журналы, 8: 45–53, дои:10.1016 / s0021-9800 (70) 80007-2
  27. ^ Пельсмажер, Майкл Дж .; Шефер, Маркус; Штефанкович, Даниэль (2007), «Тіпті өткелдерді алып тастау», Комбинаторлық теория журналы, B сериясы, 97 (4): 489–500, дои:10.1016 / j.jctb.2006.08.001
  28. ^ Биенсток, Даниэль; Дин, Натаниэль (1993), «Сызықтардың қиылысу шекаралары», Графикалық теория журналы, 17 (3): 333–348, дои:10.1002 / jgt.3190170308
  29. ^ Грэм, Рональд Л .; Ротшильд, Брюс Л.; Спенсер, Джоэл Х. (1990), Рэмси теориясы, Вили
  30. ^ Каролий, Дюля (2013), «Геометриялық графиктерге арналған Рамси типтес есептер», in Пач, Дж. (ред.), Геометриялық графика теориясы бойынша отыз эссе, Springer
  31. ^ а б Каролий, Дюла Дж .; Пач, Янос; Тот, Геза (1997), «Геометриялық графикаға арналған Рамси түріндегі нәтижелер, мен», Дискретті және есептеу геометриясы, 18 (3): 247–255, дои:10.1007 / PL00009317
  32. ^ Каролий, Джюля Дж.; Пач, Янос; Тот, Геза; Вальтр, Павел (1998), «Геометриялық графиктер үшін Рамси типіндегі нәтижелер, II», Дискретті және есептеу геометриясы, 20 (3): 375–388, дои:10.1007 / PL00009391
  33. ^ Пач, Янос (2004), «Геометриялық графтар теориясы», in Гудман, Джейкоб Э.; О'Рурк, Джозеф (ред.), Дискретті және есептеу геометриясының анықтамалығы, Дискретті математика және оның қолданылуы (2-ші басылым), Чэпмен және Холл / CRC
  34. ^ Матушек, Джири; Танцер, Мартин; Вагнер, Ули (2009), Қарапайым кешендерді ендірудің қаттылығы , 855–864 беттер
  35. ^ Brass, Peter (2004), «Туран типті дөңес геометриялық гиперграфтарға арналған есептер», in Пач, Дж. (ред.), Геометриялық графиктер теориясына қарай, Қазіргі заманғы математика, американдық математикалық қоғам, 25–33 бб
  36. ^ а б в г. Дей, Тамал К.; Пач, Янос (1998), «Геометриялық гиперографтарға арналған экстремалды есептер», Дискретті және есептеу геометриясы, 19 (4): 473–484, дои:10.1007 / PL00009365
  37. ^ Сук, Эндрю (2013), «Геометриялық 3-гиперграфия туралы ескерту», ​​in Пач, Дж. (ред.), Геометриялық графика теориясының отыз очеркі, Springer arXiv: 1010.5716v3
  38. ^ Чивальевич, Раде Т .; Vrećica, Siniša T. (1992), «түрлі-түсті Тверберг мәселесі және инъекциялық функциялар кешені», Комбинаторлық теория журналы, А сериясы, 61 (2): 309–318, дои:10.1016 / 0097-3165 (92) 90028-S
  39. ^ Барани, Имре; Фюреди, Золтан (1987), «Евклид-кеңістіктегі бос қарапайымдылық», Канадалық математикалық бюллетень, 30 (4): 436–445, дои:10.4153 / cmb-1987-064-1, hdl:1813/8573
  40. ^ Каролий, Джула; Солимоси, Йозеф (2002), «3 кеңістіктегі дерлік үшбұрыштар», Дискретті және есептеу геометриясы, 28 (4): 577–583, дои:10.1007 / s00454-002-2888-z