Roberts va Floresning ro'yxatga olish usuli. 2
- r- bosqichda bizda S={ v 1 , a, b, c ,. .., v r-1 , v r } . Keyingi cho'qqining kiritilishiga to'sqinlik qiladigan ikkita sabab bor:
- Ustun ichida vr _ mumkin bo'lmagan tepalik ;
- S to'plami bilan aniqlangan zanjir uzunligi n-1 ga ega , ya'ni. Demak, bu Gamiltoniandir
a) grafikda (v r ,v 1 ) yopilish yoyi mavjud , shuning uchun Gamilton sikli topildi;
b) grafikda yopilish yoyi yo'q (v r ,v 1 ) , shuning uchun, Gamilton siklini olish mumkin emas.
1 va 2b) hollarda qaytarish amalga oshirilishi kerak.
Hozirgacha topilgan Gamilton sikllari grafikdagi barcha Gamilton sikllaridir
Ro'yxatga olish usulini amalga oshirish namunasi
- G= grafigi uchun M o’tish matritsasi
- O'tish matritsasi asosida a tepasidan Gamilton zanjirlari tuziladi
a bdce a
a dcbe a
Gamilton grafiklarini qo'llash. Sayohatchi sotuvchi muammosi bilan bog'liq
- Og'irlangan grafikda Gamilton siklini topish muammosi sayohatchi sotuvchi muammosi sifatida tanilgan.
Ilovalar:
- operatsiyalarni buyurtma qilish yoki rejalashtirish vazifalari;
- rejalashtirish;
- kompyuterda operatsiyalarni bajarish;
- elektr va kompyuter tarmoqlarini loyihalash;
- avtomatlashtirilgan liniyalarni boshqarish;
- RAM va taqsimlangan xotira testi;
- raqamli tizimlarni tekshirish uchun testlarni sintez qilish;
- kompyuter tizimlari va tarmoqlaridagi nosozliklarni bartaraf etish
Eyler grafiklari - Eyler sikllarining mavjudligi uchun zarur va yetarli shartlar aniqlanadi
- Eyler sikllarini topish uchun samarali algoritmlar mavjud
- Eyler grafiklari kam uchraydi
- Eyler grafiklari kamroq talabga ega
Gamilton grafiklari - Mezonlar noma'lum, ammo etarli shartlar mavjud
- Grafikda Gamilton siklini topish algoritmlari ancha mashaqqatli
- Nazariya va amaliyotda uchraydigan deyarli barcha grafiklar Gamilton grafiklaridir
- Gamilton grafiklari amaliyotda ko'proq talabga ega
Eyler va Gamilton grafiklarining qiyosiy tahlili va ulanishi
Do'stlaringiz bilan baham: |
