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