Соңы (графтар теориясы) - Википедия - End (graph theory)

Ішінде математика туралы шексіз графиктер, an Соңы график интуитивті түрде графиктің шексіздікке дейін созылатын бағытын білдіреді. Аяқталуы математикалық жолмен ресімделуі мүмкін эквиваленттік сыныптар шексіз жолдар, сияқты паналар стратегияларын сипаттайтын іздеу-жалтару графиктегі ойындар немесе (жергілікті шектеулі графиктер жағдайында) сияқты топологиялық ұштар туралы топологиялық кеңістіктер графикамен байланысты.

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

Анықтама және сипаттама

Графиктердің соңы анықталды Рудольф Халин  (1964 ) шексіз жолдардың эквиваленттік кластары тұрғысынан.[1] A сәуле шексіз графикте жартылай шексіз қарапайым жол; яғни бұл шыңдардың шексіз бірізділігі v0, v1, v2, ... онда әр шың ең көбі ретпен пайда болады және тізбектегі әрбір екі шың графикте жиектің екі соңғы нүктесі болып табылады. Халиннің анықтамасы бойынша екі сәуле р0 және р1 егер басқа сәуле болса, эквивалентті болады р2 әрқайсысында шексіз көптеген шыңдарды қамтитын (алғашқы екі сәуленің екеуінен де міндетті емес) р0 және р1. Бұл эквиваленттік қатынас: әрбір сәуле өзіне тең, анықтамасы екі сәуленің ретіне қатысты симметриялы және оны көрсетуге болады өтпелі. Сондықтан ол барлық сәулелердің жиынтығын бөледі эквиваленттік сыныптар, және Халин соңын осы эквиваленттік кластардың бірі ретінде анықтады.

Сол эквиваленттік қатынастың альтернативті анықтамасы да қолданылды:[2] екі сәуле р0 және р1 егер шекті жиын болмаса, эквивалентті болады X бұл шыңдар бөледі шексіз көптеген шыңдары р0 шексіз көптеген шыңдарынан р1. Бұл Халиннің анықтамасына тең: егер сәуле болса р2 Халиннің анықтамасына сәйкес, кез келген бөлгіште шексіз көп нүктелер болуы керек р2 сондықтан шектеулі бола алмайды, және керісінше болса р2 онда мүмкін емес бірнеше рет ауысып тұратын жол жоқ р0 және р1 қажетті шекті сепараторды құруы керек.

Сондай-ақ, ұштар нақты сипаттамаға ие паналар, үшін жалтару стратегияларын сипаттайтын функциялар іздеу-жалтару графиктегі ойындар G.[3] Қарастырылып отырған ойында қарақшы полицейлердің тобынан жалтаруға тырысып, шыңнан шыңға қарай жиек бойымен қозғалады G. Полицияда тікұшақтар бар, сондықтан олардың шетін қадағалаудың қажеті жоқ; дегенмен, қарақшы полицияның келе жатқанын көріп, тікұшақтар қонғанға дейін қайда қозғалатындығын таңдай алады. Панах - бұл әр жиынтығын бейнелейтін a функциясы X полиграфиялық полигондарды жою арқылы құрылған подграфтың құрамдас бөліктерінің біріне X; қарақшы ойынның әр кезеңінде осы компоненттің шыңына өту арқылы полициядан жалтаруы мүмкін. Қонақтар тұрақтылық қасиетін қанағаттандыруы керек (қарақшы полицейлер қонған шыңдардан өтіп кете алмайды деген талапқа сәйкес): егер X ішкі бөлігі болып табылады Yжәне екеуі де X және Y берілген полиция жиынтығы үшін жарамды орындар жиынтығы, содан кейін β (X) болуы керек sup ()Y). Панада тәртіп бар к егер ол полицейлердің қашып кету стратегиясын ұсынатын орындар жиынтығына қарағанда кіші барлық ішкі жиындарды қамтыса к графиктегі шыңдар; атап айтқанда, оның тәртібі бар 0 егер ол әрбір ақырғы жиынтықты бейнелейтін болса X компоненттеріне арналған шыңдар G \ X. Әр сәуле G a тәртіптің панасына сәйкес келеді0, атап айтқанда, әрбір ақырлы жиынтықты бейнелейтін the функциясы X бірегей компонентіне дейін G \ X сәуленің шексіз көптеген шыңдарын қамтиды. Керісінше, тәртіптің әр панасы n0 сәулемен осылай анықтауға болады.[4] Екі сәуле егер олар бірдей пананы анықтаған жағдайда ғана эквивалентті болады, сондықтан графиктің ұштары оның order реттік ұяларымен бір-біріне сәйкес келеді.0.

Мысалдар

Шексіз бөлігі тор сызбасы, екі тор сызығы түйісетін нүктелерде төбелерімен. Көптеген түрлі сәулелер болғанымен, оның бір ғана ұшы бар.

Егер шексіз график болса G бұл өзі сәуле, содан кейін шексіз көптеген әр субтографиясы бар, әр шыңынан басталады G. Алайда, бұл сәулелердің барлығы бір-біріне эквивалентті, сондықтан G тек бір ұшы бар.

Егер G - бұл орман (яғни шектеулі циклдары жоқ график), онда кез-келген екі сәуленің қиылысы не жол, не сәуле болады; егер олардың қиылысы сәуле болса, екі сәуле эквивалентті болады. Егер әрбір жалғанған компонентте негізгі шың таңдалса G, содан кейін әр соңы G базалық төбелердің бірінен басталатын ерекше сәулені қамтиды, сондықтан ұштарды осы канондық сәулелермен бір-біріне сәйкестікте орналастыруға болады. Әрбір есептелетін график G бар созылып жатқан орман сияқты ұштар жиынтығымен G.[5] Алайда, бір ғана ұшымен есептелетін шексіз графиктер бар, оларда әр ағаштың ұштары шексіз көп.[6]

Егер G шексіз тор сызбасы, содан кейін оның көптеген сәулелері және шыңы-дизъюнт сәулелерінің ерікті түрде үлкен жиынтығы бар. Алайда оның бір ғана ұшы бар. Мұны ұштар сипаттамасын пейзаждар тұрғысынан қолдану оңай көрінеді: кез-келген ақырлы шыңдар жиынтығын алып тастау дәл бір шексіз байланысқан компонент қалдырады, сондықтан тек бір панал бар (әр ақырлы жиынды бірегей шексіз байланысқанға бейнелейтін) компонент).

Топологиялық ұштармен байланыс

Жылы нүктелік топология, әлдеқайда ертерек пайда болған, граф теориясының соңы ұғымына ұқсас, бірақ онымен бірдей емес ұғым тұжырымдамасы бар. Фрейденталь (1931). Егер топологиялық кеңістікті кірістірілген реттілік қамтуы мүмкін болса ықшам жиынтықтар , онда кеңістіктің соңы - бұл компоненттер тізбегі ықшам жиынтықтардың толықтауыштары. Бұл анықтама ықшам жиынтықтардың таңдауына тәуелді емес: осындай таңдаудың біреуімен анықталған ұштар кез келген басқа таңдау арқылы анықталған ұштармен бір-біріне сәйкес келуі мүмкін.

Шексіз график G топологиялық кеңістікте екі түрлі, бірақ өзара байланысты болуы мүмкін:

  • Графиктің әр шыңын нүктеге, ал графаның әр шетін ашыққа ауыстыру бірлік аралығы шығарады Хаусдорф кеңістігі жиынтығы бар графиктен S әрбір қиылысы ашық болған сайын анықталады S графиктің жиегімен бірлік интервалының ашық ішкі жиыны болады.
  • Графиктің әр шыңын нүктеге, ал графаның әр шетін нүктеге ауыстыру Хаусдорф емес кеңістікті тудырады, онда ашық жиындар жиындар болады S қасиетімен, егер ол шың болса v туралы G тиесілі S, содан кейін әрбір шеті бар v оның соңғы нүктелерінің бірі ретінде.

Екі жағдайда да әрбір ақырғы подграфиясы G топологиялық кеңістіктің ықшам кіші кеңістігіне сәйкес келеді, және кез-келген ықшам кіші кеңістік Хаусдорф жағдайында шеттердің көптеген жинақы тиісті ішкі жиындарымен бірге ақырлы субографқа сәйкес келеді. Осылайша, графикті ықшам жиындардың кірістірілген дәйектілігі қамтуы мүмкін, егер ол тек жергілікті шекті болса және әр шыңда шеттері шектеулі болса.

Егер график болса G жалғанған және жергілікті деңгейде, содан кейін оның жиынтығы κ болатын ықшам қақпағы бармен - бұл ең көп қашықтықтағы шыңдардың жиынтығы мен кейбір ерікті таңдалған бастапқы шыңнан. Бұл жағдайда кез-келген n топологиялық кеңістіктің соңын анықтайды . Және, керісінше, егер бастап анықталған топологиялық кеңістіктің соңы болып табылады G, ол n болатын пананы анықтайды (X) құрамдас бөлігі болып табылады Uмен, қайда мен any болатын кез келген санмен қамтиды X. Сонымен, байланысты және жергілікті ақырлы графиктер үшін топологиялық ұштар графикалық-теоретикалық ұштармен бір-біріне сәйкес келеді.[7]

Жергілікті шектеулі болмауы мүмкін графиктер үшін графиктен және оның ұштарынан топологиялық кеңістікті анықтауға болады. Бұл кеңістікті а түрінде ұсынуға болады метрикалық кеңістік егер және егер графикте a болса қарапайым ағаш, тамырлы ағаш әрбір граф жиегі ата-баба ұрпағын байланыстыратындай. Егер кәдімгі созылатын ағаш болса, оның берілген графикамен бірдей ұштары болады: графиктің әр ұшында ағашта бір шексіз жол болуы керек.[8]

Ұштардың ерекше түрлері

Ақысыз ұштар

Соңы E график G а деп анықталған ақыр соңында егер шектеулі жиынтық болса X қасиеттері бар шыңдар X бөледі E графиктің барлық басқа ұштарынан. (Яғни, паналар тұрғысынан, βE(X) β -дан бөлінедіД.(X) кез келген басқа мақсат үшін Д..) Ұшы көп графикте әр ұшы бос болуы керек. Халин (1964) дәлелдейді, егер G ұштары шексіз көп, сонда не бос емес шегі бар, не жалпы шыңымен басталатын және басқаша түрде бір-бірінен алшақтайтын шексіз сәулелер отбасы болады.

Қалың ұштар

A қалың ұшы график G бұл шексіз жұптыбөлу сәулелер. Халин торының теоремасы құрамында қалың ұштары бар графиктерді сипаттайды: олар а-да болатын графиктер бөлу туралы алты бұрышты плитка подограф ретінде.[9]

Графиктердің ерекше түрлері

Симметриялық және симметриялы графиктер

Мохар (1991) жалғанған жергілікті ақырлы графикті, егер шың болса, «дерлік симметриялы» деп анықтайды v және сан Д. кез келген басқа шың үшін w, бар автоморфизм кескіні берілген графиктің v қашықтықта орналасқан Д. туралы w; эквивалентті түрде, байланысқан жергілікті ақырлы график симметриялы болады, егер оның автоморфизм тобында көптеген орбиталар болса. Ол көрсеткендей, әрбір байланысты жергілікті ақырлы симметриялы график үшін ұштар саны ең көп дегенде екі немесе есептелмейді; егер ол есептелмесе, ұштары а топологиясына ие Кантор орнатылды. Сонымен қатар, Мохар ұштардың саны басқарылатынын көрсетеді Чигер тұрақты

қайда V графикалық шектердің барлық ақысыз бос жиынтықтарына және басқа жерлерге қатысты бір шеткі нүктесі бар жиектер жиынын білдіреді V. Ұзындығы көп симметриялы графиктер үшін, сағ > 0; дегенмен, тек екі шеті бар симметриялы графиктер үшін, сағ = 0.

Кейли графиктері

Cayley графигі тегін топ екі генераторда а және б. Топтың ұштары сәйкестендіру элементінің сәулелерімен (шексіз жолдармен) бір-біріне сәйкес келеді e сызбаның шетіне дейін.

Әрқайсысы топ және топқа арналған генераторлар жиынтығы а Кейли графигі, шыңдары топ элементтері, ал шеттері элементтер жұбы болатын график (х,gx) қайда ж генераторлардың бірі болып табылады. Жағдайда түпкілікті құрылған топ, топтың ұштары генераторлардың ақырғы жиынтығы үшін Кейли графигінің ұштары ретінде анықталған; бұл анықтама генераторлардың таңдауы бойынша инвариантты, егер екі түрлі ақырлы генераторлар жиыны таңдалса, Кейлидің екі графигінің ұштары бір-біріне сәйкес келеді.

Мысалы, әрқайсысы тегін топ ағаш болып табылатын Cayley графигі бар (оның еркін генераторлары үшін). Бір генератордағы еркін топтың Cayley графигі ретінде екі шексіз жолы бар, оның екі шеті бар. Кез-келген басқа топтың шегі жоқ.

Әрбір шексіз құрылған шексіз топтың не 1, 2, не шексіз көп ұштары болады, және Топтардың аяқталуы туралы сталлингтер теоремасы бірнеше ұшы бар топтардың ыдырауын қамтамасыз етеді.[10] Сондай-ақ:

  1. Шексіз құрылған шексіз топтың 2 ұшы болады, егер ол а болса циклдік кіші топ ақырлы индекс.
  2. Шексіз құрылған шексіз топтың шексіз көп аяғы болады, егер ол тек нривиальды болса біріктіру бар тегін өнім немесе HNN-кеңейту ақырғы бірігуімен.
  3. Барлық басқа шексіз топтардың дәл бір ұшы бар.

Ескертулер

  1. ^ Алайда, қалай Krön & Möller (2008) сызбалардың соңын қазірдің өзінде қарастырғанын көрсетіңіз Фрейденталь (1945).
  2. ^ Мысалы, бұл қолданған эквиваленттік қатынас формасы Diestel & Kühn (2003).
  3. ^ Пананың номенклатурасы және екі сәуленің бірдей пананы анықтауы, егер олар тек эквивалентті болса ғана, Робертсон, Сеймур және Томас (1991). Diestel & Kühn (2003) әр пананың аяғынан шығатындығын, ұштар мен паналар арасындағы биекцияны аяқтай отырып, оларды номенклатураны қолдана отырып, оларды «бағыттар» деп атады.
  4. ^ Дәлел Diestel & Kühn (2003) әрбір пананы сәулемен анықтауға болатындығы нривиальды емес және екі жағдайдан тұрады. Егер жиынтық болса (қайда X барлық ақырлы шыңдар жиынтығы бойынша диапазондар) шексіз, онда шексіз көптеген шыңдардан өтетін сәуле бар S, бұл міндетті түрде β анықтайды. Екінші жағынан, егер S ақырлы, сонда Diestel & Kühn (2003) бұл жағдайда ақырлы жиындар тізбегі болатындығын көрсетіңіз Xмен соңын ерікті таңдалған бастапқы нүктеден қашықтығы барлық нүктелерден бөледі G \ S болып табылады мен. Бұл жағдайда панахана кез-келген сәулемен анықталады, оның артынан қарақшы пананы пайдаланып, белгіленген жерге қонған полицейлерден қашып кетеді Xмен дөңгелек түрінде мен іздеу-жалтару ойыны.
  5. ^ Дәлірек айтсақ, бұл тұжырымның түпнұсқасында Халин (1964) онда ұштар сәулелердің эквиваленттік кластары, әрбір сәулелердің эквиваленттік класы ретінде анықталады G қамтитын орман сәулелерінің бірегей бос эквиваленттілік класын қамтиды. Пәтерлерге келетін болсақ, have тәртіпті пышақтардың бір-біріне сәйкестігі бар0 арасында G және оның ағашы Т ол үшін әрбір соңғы жиынтық үшін X және әрбір тиісті жұп ofТ және βG.
  6. ^ Сеймур және Томас (1991); Томассен (1992); Диестель (1992).
  7. ^ Diestel & Kühn (2003).
  8. ^ Диестель (2006).
  9. ^ Халин (1965); Диестель (2004).
  10. ^ Аялдамалар (1968, 1971 ).

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