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



жүктеу 86.59 Kb.
бет2/4
Дата07.02.2022
өлшемі86.59 Kb.
#17045
түріРеферат
1   2   3   4
Арайлым реферат
Негізгі бөлім

Гамильтондық циклдар. 

Онда графтың әрбір төбесін қамтитын  цикл бар болса, граф гамильтондық деп аталады. Циклдің өзі де гамильтондық деп аталады. Барлық байланысқан графтар гамильтондық емес.



Сурет 15. Гамильтондық емес байланыс графының мысалы

Гамильтондық циклді іздеу. Байланысқан бағытталмаған граф берілген. Барлық гамильтондық циклдарды табу керек, егер олар болса. Шешу тәсілі – қайтаруыменен жинау.

Мысалы, шешімді іздеуді бірінші графтың төбесінен бастайық. Шешімнің бірінші k компонеттерінің шешімі табылды деп болжайық. Соңғы төбеден шығатын қабырғаларды қарастырамыз. Егер алдында қарастырылмаған төбелерде ондайлар болса, онда бұл төбені шешімге енгіземіз және қарастырылған деп белгілейміз. k+1 шешімнің компоненті алынды.



 Егер ондай компонент болмаса, онда алдындағы төбеге қайтып келеміз де, осыдан басқа төбеге шығатын қабырғаларды табуға тырысамыз.

 Шешім графтың барлық төбелері және соңғы төбеден біріншіге жету мүмкіндігі қарастырылған кезде алынды. Шешім шығарылады және келесі циклдерді табу процесі жалғаса береді. Гамильтондық цикл табу процедурасы рекурсивті болып табылады.

Сурет 16. Байланысқан граф              Сурет 17. Ағаш бөлігі,

         мысалы.                                          берілген механизімнің

                                                                жұмыс істеу тәсілі.



жүктеу 86.59 Kb.

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




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

    Басты бет