Флейшнер теоремасы - Fleischners theorem - Wikipedia

2 шыңға байланысты график, оның квадраты және квадраттағы Гамильтон циклі

Жылы графтар теориясы, математика бөлімі, Флейшнер теоремасы а-ны қамтуы үшін графикке жеткілікті шарт береді Гамильтон циклі. Онда, егер G Бұл 2 шыңға байланысты график, содан кейін шаршы G Гамильтондық. ол аталған Герберт Флейшнер, оның дәлелін 1974 жылы жариялаған.

Анықтамалар мен мәлімдеме

Ан бағытталмаған граф G егер ол а цикл бұл оның әрбір шыңына дәл бір рет тиетін. Егер ол артикуляция шыңы болмаса, оны жою арқылы қалған графикті ажыратып тастайтын шың болмаса, ол 2 шыңмен байланысты. Әрбір 2 шыңға байланысты график Гамильтондық емес; қарсы мысалдарға Питерсен графигі және толық екі жақты график Қ_2,3.

Квадраты G бұл график G² бірдей шыңға ие Gжәне егер екі төбенің қашықтығы ең көп дегенде екі дюйм болса ғана шектеседі G. Флейшнер теоремасы кемінде үш төбесі бар ақырлы 2-шыңға байланысты графиктің квадраты әрқашан Гамильтондық болуы керек деп айтады. Эквивалент бойынша, әр 2 шыңға байланысты графиктің шыңдары G а түрінде орналасуы мүмкін циклдік тәртіп Көршілес шыңдар осы тәртіппен бір-бірінен ең көп дегенде екі қашықтықта орналасқан G.

Кеңейтімдер

Флейшнер теоремасында Гамильтон циклын шектеуге болады G² сондықтан берілген шыңдар үшін v және w туралы G оның екі шетін қамтиды G оқиға v және бір шеті G оқиға w. Сонымен қатар, егер v және w ішінде орналасқан G, онда бұл үш түрлі шеттер G.^[1]

Гамильтондық циклдан басқа, 2 шыңға байланысты графиктің квадраты G сонымен бірге Гамильтондық байланысты болуы керек (оның а бар екенін білдіреді) Гамильтондық жол кез-келген екі төбесінде басталатын және аяқталатын) және 1-гамильтондық (егер кез-келген шың жойылса, қалған графикте гамильтон циклі бар дегенді білдіреді).^[2] Ол сондай-ақ шың болуы керек панциклді, бұл әрбір шыңға арналған v және барлық бүтін сан к 3 withк ≤ |V(G), ұзындық циклі барк құрамындаv.^[3]

Егер график болса G 2-төбеге байланысты емес, оның квадратында Гамильтон циклі болуы немесе болмауы мүмкін, ал оның бар-жоғын анықтау NP аяқталды.^[4]

Шексіз графта Гамильтон циклі бола алмайды, өйткені кез-келген цикл шектеулі, бірақ Карстен Томассен егер дәлелдеді G бір шегі бар шексіз жергілікті ақырлы 2-шыңға байланысты график Соңы содан кейін G² міндетті түрде екі есе шексіз Гамильтондық жолы бар.^[5] Жалпы, егер G жергілікті ақырлы, 2 шыңға байланысты және кез-келген шегі бар, содан кейін G² Гамильтон шеңбері бар. Ішінде ықшам топологиялық кеңістік графикті а түрінде қарау арқылы қалыптасады қарапайым кешен және оның әр ұшына шексіздікте қосымша нүкте қосып, Гамильтон шеңбері ішкі кеңістік ретінде анықталады. гомеоморфты Евклид шеңберіне және барлық шыңдарды қамтиды.^[6]

Алгоритмдер

Ан квадратындағы Гамильтон циклы n-vertex 2-ге байланысты графикті сызықтық уақытта табуға болады,^[7] Лаудың алғашқы алгоритмдік шешімімен жетілдіру^[8] жұмыс уақыты O (n²)Флейшнер теоремасын а 2-жуықтау дейін тар сатушы проблемасы жылы метрикалық кеңістіктер.^[9]

Тарих

Флейшнер теоремасының дәлелі жарияланды Герберт Флейшнер 1971 ж. және ол 1974 ж. болжамды шешіп, 1974 ж. жариялады Криспин Нэш-Уильямс өз бетінше жасаған Бейнеке және Майкл Д.Плуммер.^[10] Нэш-Уильямс Флейшнердің қағазына шолу жасап, «бірнеше жылдан бері басқа граф-теоретиктердің тапқырлығын жеңіп келе жатқан белгілі мәселені» шешті деп жазды.^[11]

Флейшнердің алғашқы дәлелі күрделі болды. Вацлав Чватал, ол өзі ойлап тапқан жұмыста графикалық қаттылық, а квадраты екенін байқадық к-vertex-ге байланысты график міндетті түрде болуы керек к-қатал; ол болжамды бұл 2 қатал графиктер - Гамильтондық, одан Флейшнер теоремасының тағы бір дәлелі пайда болар еді.^[12] Осы болжамға қарсы мысалдар кейінірек табылды,^[13] бірақ қаттылықпен шектелген Гамильтондылықты білдіруі ықтималдығы графика теориясының маңызды проблемасы болып қала береді. Флейшнер теоремасының және оның кеңеюінің қарапайым дәлелі Чартран және т.б. (1974), берген (Íha (1991),^[14] және теореманың тағы бір жеңілдетілген дәлелі келтірілген Джоргакопулос (2009a).^[15]

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

Ескертулер

Бастапқы көздер

• Альструп, Стивен; Джоргакопулос, Агелос; Ротенберг, Ева; Томассен, Карстен (2018), «Сызықтық уақыттағы 2 қосылған график алаңындағы гамильтондық цикл», Жиырма тоғызыншы жыл сайынғы ACM-SIAM дискретті алгоритмдер симпозиумының материалдары, 1645–1649 б., дои:10.1137/1.9781611975031.107, ISBN  978-1-61197-503-1
• Бауэр, Д .; Брерсма, Х. Дж .; Велдман, Х. Дж. (2000), «Әрбір қатал график Гамильтондық емес», Графиктер мен комбинаторлық оңтайландыру бойынша Твенттің 5-ші семинарының материалдары (Enschede, 1997), Дискретті қолданбалы математика, 99 (1–3): 317–321, дои:10.1016 / S0166-218X (99) 00141-9, МЫРЗА  1743840.
• Бонди, Дж. А. (1971), «Панциклдік графиктер», Комбинаторика, график теориясы және есептеу бойынша екінші Луизиана конференциясының материалдары (Луизиана штатының университеті, Батон Руж, Ла., 1971), Батон Руж, Луизиана: Луизиана мемлекеттік университеті, 167–172 бет, МЫРЗА  0325458.
• Чартран, Г.; Хоббс, Артур М.; Джунг, Х.А .; Капур, С. Ф .; Нэш-Уильямс, Сент-Дж. А. (1974), «Блоктың квадраты Гамильтонмен байланысты», Комбинаторлық теория журналы, B сериясы, 16 (3): 290–292, дои:10.1016/0095-8956(74)90075-6, МЫРЗА  0345865.
• Чваталь, Вацлав (1973), «Қатал графиктер және Гамильтон схемалары», Дискретті математика, 5 (3): 215–228, дои:10.1016 / 0012-365X (73) 90138-6, МЫРЗА  0316301.
• Флейшнер, Герберт (1974), «Әрбір екі қосылған графиктің квадраты - Гамильтон», Комбинаторлық теория журналы, B сериясы, 16: 29–34, дои:10.1016/0095-8956(74)90091-4, МЫРЗА  0332573.
• Флейшнер, Х. (1976), «Графиктер квадратында Гамильтондылық пен панциклділік, Гамильтондық байланыс пен түйісу - баламалы ұғымдар», Monatshefte für Mathematik, 82 (2): 125–149, дои:10.1007 / BF01305995, МЫРЗА  0427135.
• Георгакопулос, Агелос (2009а), «Флейшнер теоремасының қысқаша дәлелі», Дискретті математика, 309 (23–24): 6632–6634, дои:10.1016 / j.disc.2009.06.024, МЫРЗА  2558627.
• Джоргакопулос, Агелос (2009б), «Жергілікті ақырлы график квадраттарындағы шексіз Гамильтон циклдары», Математикадағы жетістіктер, 220 (3): 670–705, дои:10.1016 / j.aim.2008.09.014, МЫРЗА  2483226.
• Хоббс, Артур М. (1976), «Блоктың квадраты - шыңның панциклі», Комбинаторлық теория журналы, B сериясы, 20 (1): 1–4, дои:10.1016/0095-8956(76)90061-7, МЫРЗА  0416980.
• Хохбаум, Дорит С.; Шмойс, Дэвид Б. (1986), «Тығырыққа тірелген мәселелер бойынша алгоритмдерге бірыңғай көзқарас», ACM журналы, Нью-Йорк, Нью-Йорк, АҚШ: ACM, 33 (3): 533–550, дои:10.1145/5925.5933.
• Lau, H. T. (1980), Блок квадратында Гамильтон циклін табу., Ph.D. диссертация, Монреаль: МакГилл университеті. Келтірілгендей Хохбаум және Шмойс (1986).
• Мюттел, Жанина; Ротенбах, Дитер (2012), «Флейшнер теоремасының жан-жақты нұсқасының қысқаша дәлелі», Дискретті математика, 313 (19): 1929–1933, дои:10.1016 / j.disc.2012.07.032.
• Паркер, Р.Гарей; Рардин, Рональд Л. (1984), «Бөтелкедегі саяхатшылар мәселесі үшін кепілдендірілген өнімділік эвристикасы», Операцияларды зерттеу хаттары, 2 (6): 269–272, дои:10.1016/0167-6377(84)90077-4.
• Staníha, Станислав (1991), «Флейшнер теоремасының жаңа дәлелі», Комбинаторлық теория журналы, B сериясы, 52 (1): 117–123, дои:10.1016/0095-8956(91)90098-5, МЫРЗА  1109427.
• Томассен, Карстен (1978), «шексіз жергілікті ақырлы блоктардың квадраттарындағы гамильтондық жолдар», in Боллобас, Б. (ред.), Графика теориясының жетістіктері (Кембридж Комбинаторлық Конф., Тринити Колледжі, Кембридж, 1977), Дискретті математиканың жылнамалары, 3, Elsevier, б.269–277, дои:10.1016 / S0167-5060 (08) 70512-0, ISBN  978-0-7204-0843-0, МЫРЗА  0499125.
• Жер асты, Полли (1978), «Гамильтон квадраттары бар графиктер туралы», Дискретті математика, 21 (3): 323, дои:10.1016 / 0012-365X (78) 90164-4, МЫРЗА  0522906.

Екінші көздер

• Бонди, Дж. А. (1995), «Графиктің негізгі теориясы: жолдар мен тізбектер», Комбинаторика анықтамалығы, т. 1, 2, Амстердам: Эльзевье, 3–110 бет, МЫРЗА  1373656.
• Чартран, Гари; Лесняк, Линда; Чжан, Пинг (2010), Графиктер мен диграфтар (5-ші басылым), CRC Press, б. 139, ISBN  9781439826270.
• Диестел, Рейнхард (2012), «10. Гамильтондық циклдар», Графикалық теория (PDF) (түзетілген 4-ші электронды ред.)