А. Мырзахметов атында
Графтарға байланысты есептер
жүктеу/скачать 2,54 Mb.
|
Графтарға байланысты есептер.Мысалы, Бүкіләлемдік тұйық саяхат (Гамильтон). Жер шарынан кез келген 20 алайық: a, b, c,…,t. Қарапайымдылық үшін, бұл қалалар додекаэдрдің төбелерінде орналассын (20 төбелерімен және 12 бесбұрышты қабырғаларымен көпбұрыш) Жердің бейнелейтін. Бізідің мақсатымыз, әрбір қаладан тек қана бір рет өтіп және бастапқы қалаға қайтып келу, бірақ тек қана додекаэдрдің қабырғаларымен жүру керек. Бұл есеп симметриялық графқа гамилтондық контурды табуға әкеледі. 2 суретте бейнеленген. 
Сурет 2.
Саяхатшы шектік нүктеге келгесін үш жолдың біреуін таңдадау керек: оң жақта орналасқан доға арқылы оны П деп белгілейік, сол жақта орналасқан доға арқылы оны Л деп белгілейік, орнында қалса 1. Содан соң бұл операцияның туындысын анықтау керек: ПЛ бұл оң жақтан бастап жүру операциясы, содан солға. ЛЛП немесе Л2 П бұл екі рет солға және бір рет оңға жүру операциясы, т.с.с. Сонымен, екі операция да тең, егер екеуі де бір нүктеден бастап, сол нүктеге қайтып келеді. Бұл амал коммутативтік емес (мысалы, ПЛЛП), бірақ ассоциативтік (мысалы, (ЛЛ)П=Л(ЛП)).
Бұл туынды 20 әріптен тұрады т және бұдан кесіңдіні бөліп алуға болмайды, 1-ге тең болатын. Сондықтан туындыдан алынған көбейткіштерінің тізбегі гамильтондық контурды береді. Екінші контурды біз тізбекті кері оқығанда табамыз; басқа гамильтондық контурлар екі тізбекті де циклдік алмастырулар арқылы пайда болады. Бірақ бір нәрсені ескеру керек, саяхатты дөңгелекті контурдың әр түрлі нүктелерінен бастауға болады. Саяхатшы кездестіретін бастапқы бес қаланы белгілеп (a,b,c,d,e) және таңдалынатын жолдармен шектеліп ПЛП басталатын. Гамильтон 4 шешімді тапты. ПЛПЛПЛЛЛПППЛПЛПЛЛЛПП ПЛПЛЛЛПППЛПЛПЛЛЛПППЛ ПЛПЛПППЛЛЛПЛПЛПППЛЛЛ ПЛПППЛЛЛПЛПЛПППЛЛЛПЛ Мысал 2. Тұйық емес әлемдік саяхат.Егер алдыңғы мысалда бастапқы орынға қайтып келуді талап етпесек, онда саяхаттың саны біршама өседі: графтың барлық гамильтондық жолдарын табу керек. Туындылары бірінші П көбейткішімен болатын гамильтондық графтармен шектелеміз; қалған гамильтондық жолдар П және Л әріптерінің рөлдерін ауыстырсақ.
жүктеу/скачать 2,54 Mb. Достарыңызбен бөлісу:
|