Гомеоморфизм (график теориясы) - Homeomorphism (graph theory) - Wikipedia

Жылы графтар теориясы, екі график және болып табылады гомеоморфты егер бар болса графикалық изоморфизм кейбіреулерінен бөлу туралы кейбіреулеріне бөлу туралы . Егер графиктің шеттері бір шыңнан екінші шыңға жүргізілген сызықтар ретінде қарастырылса (әдетте олар иллюстрацияларда бейнеленген болса), онда екі граф граф-теоретикалық мағынада бір-біріне гомеоморфты, егер олар дәл болса гомеоморфты термині қолданылатын мағынада топология.[1]

Бөлу және тегістеу

Жалпы, а бөлу график G (кейде кеңейту[2]) - бұл жиектерді бөлу нәтижесінде пайда болған график G. Бір шетінен бөлу e соңғы нүктелермен {сен,v} бір жаңа шыңы бар графикті шығарады wжәне жиек жиынтығын ауыстыру арқылы e екі жаңа шетінен, {сен,w} және {w,v}.

Мысалы, шеті e, соңғы нүктелермен {сен,v}:

Графиктің бөлімшесі step1.svg

екі жиекке бөлуге болады, e1 және e2, жаңа шыңға қосылу w:

Графиктің бөлімшесі step2.svg

Кері операция, тегістеу немесе тегістеу шың w жиектерге қатысты (e1, e2) оқиға w, бар екі жиекті де алып тастайды w және ауыстырады (e1, e2) жұптың басқа соңғы нүктелерін байланыстыратын жаңа шеті бар. Мұнда тек 2 валентті шыңдарды тегістеуге болатындығы атап көрсетілген.

Мысалы, қарапайым байланысты екі шеті бар график, e1 {сен,w} және e2 {w,v}:

Графиктің бөлімшесі step2.svg

шыңы бар (атап айтқанда wтегістеуге болатын, нәтижесінде:

Графиктің бөлімшесі step1.svg

Графикке қатысты екенін анықтау G және H, H тармағымен гомеоморфты болып табылады G, болып табылады NP аяқталды проблема.[3]

Бариентрлік бөлімшелер

The бариентрлік бөлімше графиктің әр шетін бөледі. Бұл ерекше бөлімше, өйткені ол әрқашан а екі жақты граф. Бұл процедураны қайталауға болады, осылайша nмың бариентрлік бөлімше n−1мың графиктің бариентрлік бөлімшесі. Екінші осындай бөлу әрқашан а қарапайым график.

Бетіне ендіру

Графты бөлу жоспарлылықты сақтайтыны анық. Куратовский теоремасы дейді

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

Шынында, геомоморфты график Қ5 немесе Қ3,3 а деп аталады Куратовский субографиясы.

Келесіден қорытындылау Робертсон - Сеймур теоремасы, бұл әрбір бүтін сан үшін ж, ақырғы бар кедергі жиынтығы графиктердің график сияқты H бетіне ендірілген түр ж егер және егер болса H кез келгенінің гомеоморфты көшірмесін қамтымайды . Мысалға, Куратовскийдің ішкі графиктерінен тұрады.

Мысал

Келесі мысалда график G және график H гомеоморфты.

График G
График H

Егер G ' сыртқы жиектерін бөлу арқылы құрылған график болып табылады G және H ' ішкі жиегін бөлу арқылы құрылған график болып табылады H, содан кейін G ' және H ' ұқсас графикалық сызбасы бар:

График G ', H '

Демек, арасында изоморфизм бар G ' және H ', мағынасы G және H гомеоморфты.

Сондай-ақ қараңыз

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

  1. ^ Archdeacon, Dan (1996), «Топологиялық графикалық теория: шолу», Графтар теориясы бойынша зерттеулер (Сан-Франциско, Калифорния, 1995), Конгрессус Нумерантиум, 115, 5-54 б., МЫРЗА  1411236, Атауы пайда болады және егер олар топологиялық кеңістіктер ретінде гомеоморфты болса ғана, графиктер сияқты гомеоморфты болады
  2. ^ Трюдо, Ричард Дж. (1993). Графикалық теорияға кіріспе (Түзетілген, кеңейтілген республика. Ред.). Нью-Йорк: Dover Pub. б. 76. ISBN  978-0-486-67870-2. Алынған 8 тамыз 2012. Анықтама 20. Егер графиктің кейбір шеттеріне 2 дәрежелі кейбір шыңдар қосылса G, алынған график H деп аталады кеңейту туралы G.
  3. ^ Субтографиялық гомеоморфизм проблемасы деген атаумен әдебиетте жиі зерттелетін мәселе - H тармақшасына изоморфты болып табылады G. Іс қашан H болып табылады n-vertex циклі -ге тең Гамильтон циклі проблема, сондықтан NP аяқталған. Алайда, бұл тұжырымдама тек қана сұраққа баламалы H тармағымен гомеоморфты болып табылады G қашан H екі дәрежелі шыңдар жоқ, өйткені ол тегістеуге мүмкіндік бермейді H. Берілген есепті Гамильтон циклін азайтудың кішігірім модификациясы арқылы NP аяқталған деп көрсетуге болады: әрқайсысына бір шың қосыңыз H және G, барлық басқа шыңдарға іргелес. Осылайша, графиктің бір төбелі күшейтуі G гомеоморфты субографияны қамтиды (n + 1) -текс доңғалақ графигі, егер және егер болса G Гамильтондық. Субтограф гомеоморфизмінің қаттылығы туралы, мысалы, қараңыз. ЛаПо, Андреа С .; Ривест, Рональд Л. (1980), «Гомеоморфизм субографиясы мәселесі», Компьютерлік және жүйелік ғылымдар журналы, 20 (2): 133–149, дои:10.1016/0022-0000(80)90057-4, МЫРЗА  0574589.
  • Йеллен, Джей; Гросс, Джонатан Л. (2005), Графикалық теория және оның қолданылуы, Дискретті математика және оның қолданылуы (екінші басылым), Бока Ратон: Чэпмен және Холл / CRC, ISBN  978-1-58488-505-4