Реферат тақырыбы: Гамильтондық тізбектер және циклдар Орындаған: Қыпшақбаева А. Тобы: 126-28 Қабылдаған: Байжұманов А



жүктеу 86.59 Kb.
бет3/4
Дата07.02.2022
өлшемі86.59 Kb.
#17045
түріРеферат
1   2   3   4
Арайлым реферат
Гамильтондық графтар.
Бағдарланбаған графтағы гамильтондық тізбе деп графтың әрбір төбесі арқылы бір-ақ рет, текқана бір-ақ рет өтетін тізбе айтылады. Бағдарланбаған графтағы гамильтондық цикл деп графтың әрбір төбесі арқылы бір рет, текқана бір рет өтетін цикл айтылады. Бағдарланған графтағы гамильтондық жол деп бграфтың барлық төбелері арқылы бір рет, текқана бір рет өтетін S(x1,…,xn) жол айтылады. Бағдарланған графтағы гамильтондық контур деп оның барлық төбелері арқылы бір рет, текқана бір рет өтетін M(x0,x1,…,xn,x0) контурын айтады.

Гамильтондық цикл туралы көп мәселелер бар: Түскі ас дөңгелек столға жасалған. Шақырылған қонақтардың арасында кейбіреулері достар. Қандай жағдайда барлық қонақтарды, столдың екі жағында әрбір қатысушының (қонақтың) достары отыратындай етіп отырғызуға (орналастыруға) болады?







1

2

1






2








Сызба.4.
Графтардың әртүрлі ойындарда қолдануларында төбелерге позициялар сәйкес келеді. Гамильтондық циклдің бар болуы әрбір позицияны (төбелерді) бір-ақ рет қамтитын жүрістердің циклдік тізбектерінің бар болуымен тең. Оған мысалы белгілі шахмат аты туралы мәселе қарастыруымыз мүмкін. Шахмат тақтасының кез келген өрісінен (клеткасынан) бастап атпенен оның барлық алпыс төрт клеткасын жүріп өтіп бастапқы позицияға (клеткаға) келуге болама?

Гамильтондық циклдерге сол сияқты “Кезбе сатушы тұралы мәселе” жатады. Сатушы сауда жасайтын ауданда n қала бар. Қалалардың бір - бірінен ара қашықтығы белгілі. Барлық қалаларды аралап шығып, қайтадан бастапқы нүктеге әкелетін ең қысқа жолды табу. Бұл есеп экономикада, операцияларды зерттеуде қолданылады, мысалға транспорттық мәселе.

Енді гамильтондық тізбектердің, циклдердің, жолдардың және контурлардың бар болуының бірнеше жеткілікті шарттарын тұжырымдайық.

Айталық δ(xi), δ(xj) мәндер xi және xj төбелерінің дәрежелері болсын. Онда кезектегі тұжырым ақиқат.



Теорема. Егер n төбесі бар G(X) графында кез келген xi және x­j төбелері үшін δ(xi)+δ(xj)≥n-1 теңсіздігі орынды болса, онда G(X) графының гамильтондық тізбесі болады.

Эйлерлік және гамильтондық циклдер анықтамаларының ұқсастығына қарамастан сәйкес теориялардың осы ұғымдарға қатысты ортақтығы шамалы. Эйлерлік циклдің бар болу критериі өте қарапайым, ал гамильтондық цикл үшін осы уақытқа дейін жалпы ереже белгісіз. Сондықтан “Кейбір нақты граф үшін мұндай цикл табу мүмкін ба?”-деген сұрақта туындайды. Әрине, бұл мәселе графтың төбелерінің санына байланысты болғандықтан мәселені барлық мүмкіндіктерді талдау әдісі арқылы шешуге болады, бірақ ең тиімді алгоритм белгісіз. Осы мәселе негізінде АҚШ-ның астанасын осы елдің штаттарымен қосатын ең қысқа әуе жолын Данцич, Джексон және Фалкерсон сияқты математиктер есептен шығарған. Ал ол мемлекет экономикасына осы күнге дейін өте үлкен пайда келтіруде.




жүктеу 86.59 Kb.

Поделитесь с Вашими друзьями:
1   2   3   4




©emirb.org 2022
әкімшілігінің қараңыз

    Басты бет