eyler va gamilton graflari

DOC 70,5 KB Bepul yuklash

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1447857542_62285.doc eyler va gamilton graflari graf, uch, qirra, sikl, eyler zanjiri, eyler sikli, eyler graft, yarim eyler graft, oriyentirlangan eyler yo 4i, oriyentirlangan eyler graft, flyori algoritmi, gamilton zanjiri, gamilton sikli, gamilton graft, yarim gamilton graft, kommivoyajer masalasi. eyler graflari. graflar nazariyasining shakllanishi kyonig-sberg ko'priklari haqidagi masala bilan bog'liq ekanligi yaxshi malum. l. eyler 1736-yilda bu masalaning yechimga ega emasligini isbotladi. u graflar nazariyasining ancha umumiy hisoblangan quyidagi savoliga ham javob topdi: qanday shartlar bajarilganda, bog'lamli grafda barcha qirralardan faqat bir marta o'tadigan sikl mavjud bo'ladi? grafning har bir qirrasidan faqat bir marta o'tadigan zanjir eyler zanjiri, deb ataladi. yopiq eyler zanjiriga (ya'ni eyler sik~ liga) ega graf eyler graft, deb ataladi. agar grafda yopiq bo'lmagan eyler zanjiri topilsa, u holda bunday graf yarim eyler graft, deb ataladi. 1-teorema. bog'lamli graf eyler graft bo'lishi uchun undagi barcha uchlarning darajalari juft bo 'lishi zarur va yetarlidir. isboti.zarurligi.g eyler grafida c—eyler sikli …

a bo'ylab harakatlanamiz va uning boshqa uchiga o'tamiz. har safar, imkoniyati boricha, yangi qirra tanlab va bu qirradan o'tib, uning boshqa uchiga boramiz. shuni ta'kidlash zarurki, bunday o'tishlar jarayonida faqat qirraning yangisini tanlashga harakat qilinadi, uchlar esa istalgancha takrorlanishi mumkin. har bir uchga insident qirralar soni juft bo'lgani uchun cxsiklni qurish jarayoni faqat vxuchga borgandagina tugaydi. bu yerda ikki hoi bo'lishi mumkin: 1) cxsikl g grafning barcha qirralaridan o'tadi yoki 2) cxsikl g grafnir.p barcha qirralaridan o'tmaydi. , birinchi holda teorema isbotlandi deyish mumkin. ikkinchi holda g grafdan cxsiklga tegishli barcha qirralarni olib tashlaymiz vanatijada hosil bo'lgan grafni cxdeb belgilaymiz. bu yerda yakkalanib qolgan uchlarni olib tashlash yoki olib tashlamaslik muhim emas.agar yakkalanib qolgan uchlar olib tashlanmasa, natijada bog'lamli bo'lmagan gxgrafni hosil qilishimiz ham mumkin.grafdan qirralarni bunday olib tashlash amali, tabiiyki, grafning qirralari sonini kamaytiradi, lekin grafdagi uchlarning darajalari juftligi xossasini o'zgartirmaydi. g grafning bog'lamliligiga ko'ra, cxsikl va gxgraf hech …

bilan yakunlanadi.■ 1-natija. bog'lamli graf yarim eyler graft bo'lishi uchun undagi ikkitadan ко'p bo 'imagan uchning darajalari toq bo lishi zarur va yetarlidir. isboti 1-teoremaning isbotidan ba'zi o'zgartirishlar natijasida hosil qilinishi mumkin.■ 1-teorema asosida kyonigsberg ko'priklari haqidagi masalaning (ushbu bobning 1-paragrafiga qarang) yechimi mayjud emas, degan xulosaga kelamiz, ya'ni kyonigsberg shahrining ixtiyoriy qismida joylashgan uydan chiqib, pregel daryosi ustiga qurilgan yetti ko'prikdan faqat bir martadan o'tgan holda yana o'sha uyga qaytib kelish mumkin emas. oriyentirlangan graflarda oriyentirlangan eyler yo'lini izlash bilan shug'ullanish mumkin. har bir yoydan faqat bir marta o'tadigan yo'l oriyentirlangan eyler yo'li, deb ataladi. tarkibida oriyentirlangan eyler yo'li bor bo'lgan oriyentirlangan graf oriyentirlangan eyler grafi, deb ataladi. endi qirralari soni n ga teng bo'lgan berilgan eyler grafida eyler zanjirini tuzishning flyori algoritmini1keltiramiz. bualgoritmga ко'ra, grafning qirralari eyler siklida uchrashi tartibi bo'yicha 1 dan n gacha raqamlab chiqiladi. berilgan eyler grafi uchun flyori algoritmiga binoan quyidagi ikkita qoida asosida …

hunihamta'kidlashkerakki, flyorialgoritminiqo'llashjarayonidaqirralarnitanlashimkoniyatlariko'pbo'lganiuchun, bundayvaziyatlarda, algoritmniqo'llashmavjudeylersikllaridanbirinitopishbilancheklanadi.tushu-narliki, flyorialgoritminitakrorqo'llab (bundaqirralarnitanlashjaroyonialgoritminiawalgiqo'llashlardagidekaynantakror-lanmasligikerak) grafdamavjudbo'lganbarchaeylersikllarinitopishmumkin. 1-misol.1-shaklda tasvirlangan grafni qaraymiz.awalo, bu grafning eyler grafi bo'lishi shartini, ya'ni 1-teorema shartlarining bajarilishini tekshiramiz. berilgan grafda to'qqizta uch bo'lib, 1, 3, 7, 9 belgili uch-larning darajasi ikkiga, 2, 4, 6, 8 belgili uchlarning darajasi to'rtga, 5 belgili uchning darajasi esa oltiga teng.xullas, bu grafdagi barcha uchlarning darajalarijuftdir. shu-ning uchun, 1-teoremaga ko'ra, 1 -shaklda tasvirlangan graf eyler grafidir va uning tarkibida eyler sikli mavjud. berilgan grafga flyori algoritmini qo'llab, mavjud eyler sikllaridan birini aniqlaymiz. dastlabki uch sifatida grafdagi 1 belgili uch olingan bo'lsin. bu uchdan ikki yo'nalishda: (1;2) qirra bo'ylab yoki (1;4) qirra bo'ylab harakatlanish mumkin. masalan, (1;2) qirra bo'ylab harakatlanib 2 belgili uchga o'tamiz. endi harakatni 3 yo'nalishda: yo (2;3) qirra bo'ylab, yo (2;4) qirra bo'ylab, yoki (2;5) qirra bo'ylab davom ettirish mumkin. aytaylik, (2;3) qirra bo'ylab harakatlanib 3 belgiliuchgao'tganbo'laylik. shuusuldadavometishmumkinbo'lganeylersikllaridanbirini, masalan, quyidagisiklnihosilqilamiz: ((1,2), (2,3),(3,5), (5,4), (4,6), (6,9), (9,8), (8,6), (6,5),(5,8), (8,7), …

a shu asosda 1859-yilda «olam bo'ylab sayohat» nomli o'yirmi topgan. grafning har bir uchidan faqat bir marta o'tadigan zanjir gamilton zanjiri, deb ataladi. yopiq gamilton zanjiriga (ya'ni gamilton sikliga) ega graf gamilton graft, deb ataladi. agar grafda yopiq bo'lmagan gamilton zanjiri to-pilsa, u holda bunday graf yarim gamilton graft, deb ataladi. oriyentirlangan graflarda ham grafning har bir uchidan faqat bir marta o'tuvchi oriyentirlangan sikllarni qarash mumkin. eyler va gamilton graflari bir-birlariga o'xshash ta'riflansa-da, grafning gamilton grafi ekanligini tasdiqlaydigan alomat (mezon) topish masalasi ancha murak-kab hisoblanadi. hozirgi vaqtgacha graflar nazariyasida grafning gamilton grafi ekanligini tasdiqlovchi shartlarni o'rganish bo'yicha izlanishlar davom etib, bu sohadagi ishlar hanuzgacha dolzarbligini yo'qotmasdan kelmoqda. qandaydir shartlarga bo'ysunuvchi graflarda gamilton sikli mavjudligi haqida bir necha tasdiqlar mavjud. qator hollarda bu tasdiqlarning isbotlari konstraktiv bo'lganligidan, gamilton siklini tuzishga doir samarali algoritmlar ham yaratilgan.1952-yilda g. e. dirak1 quyidagi teoremani isbotladi. 2-teorema (dirak). uchlari soni uchtadan kam bo'lmagan grafdagi istalgan uchning …

Ko'proq o'qimoqchimisiz?

Faylni Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"eyler va gamilton graflari" haqida

1447857542_62285.doc eyler va gamilton graflari graf, uch, qirra, sikl, eyler zanjiri, eyler sikli, eyler graft, yarim eyler graft, oriyentirlangan eyler yo 4i, oriyentirlangan eyler graft, flyori algoritmi, gamilton zanjiri, gamilton sikli, gamilton graft, yarim gamilton graft, kommivoyajer masalasi. eyler graflari. graflar nazariyasining shakllanishi kyonig-sberg ko'priklari haqidagi masala bilan bog'liq ekanligi yaxshi malum. l. eyler 1736-yilda bu masalaning yechimga ega emasligini isbotladi. u graflar nazariyasining ancha umumiy hisoblangan quyidagi savoliga ham javob topdi: qanday shartlar bajarilganda, bog'lamli grafda barcha qirralardan faqat bir marta o'tadigan sikl mavjud bo'ladi? grafning har bir qirrasidan faqat bir marta o'tadigan zanjir eyler zanjiri, deb ataladi. yopiq eyler...

DOC format, 70,5 KB. "eyler va gamilton graflari"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: eyler va gamilton graflari DOC Bepul yuklash Telegram