Dirak va Ore teoremalari asosida






![qismlari sifatida ko rib chiqish qiziq. ʻ
Regulyar graflar. 2-rasmdagi ?????? 1, ?????? 3, ?????? 8, ?????? 11 graflari ularning har
birida barcha uchlar bir xil darajaga ega ekanligi bilan ajralib turadi.
Bunday graflar regulyar yoki bir jinsli deb nomlanadi. 4-rasmda
uchinchi, to rtinchi va beshinchi darajadagi muntazam sakkizta uchli
ʻ
graflar ko rsatilgan.
ʻ
4-rasm. Regulyar graflar.
Uchinchi darajali graflar kubik deb nomlanganiga e’tibor bering. –
rasmdagi ?????? 11 va –rasmdagi ?????? 1. Shubhasiz, d darajali regulyar grafdagi
qirralarning soni ?????? = ????????????/2 ga teng. Bundan kelib chiqadiki, toq sonli
uchlar uchun regulyar graf faqat juft darajaga, toq daraja uchun esa faqat
uchlar soni bo lishi mumkin. Shuning uchun har qanday kubik graf
ʻ
uchlarning juft soniga ega.
Qo shnilik matritsasi. Qo shnilik matritsasini n-tartibli
ʻ ʻ
?????? =[ ???????????? , ???????????? ] nosimmetrik kvadrat matritsa sifatida aniqlaymiz, unda ???????????? , ??????
elementlar 1 ga teng, agar grafda { ???????????? , ???????????? } qirrasi bo lsa, ya’ni
ʻ ???????????? va ????????????
qo shni bo lsa, 0 ga teng, agar bunday qirra mavjud bo lmasa.
ʻ ʻ ʻ
5-rasm. Grafni qo’shnilik matritsasi orqali tasvirlash.
Insidentlik matritsasi. Insidentlik matritsasi - bu grafning
elementlari (qirra - uch) orasidagi bog lanishlar ko rsatiladigan grafni
ʻ ʻ
tasvirlash shakli. Matritsaning ustunlari qirralarga, satrlar uchlarga
to g ri keladi. Demak, matritsa kvadrat bo lmaydi. Matritsa
ʻ ʻ ʻ
yacheykasidagi nolga teng bo lmagan qiymat uch va qirra (ularning
ʻ
insidentligi) o rtasidagi munosabatni bildiradi.
ʻ
6-rasm. Grafning insidentlik matritsasi.
Yo naltirilgan graf holatida tegishli ustundagi har bir uch chiquvchi
ʻ](/data/documents/693d74e7-b329-4aa9-bfdc-be98ca0f4a82/page_7.png)


![qolgan uchlami olib tashlash yoki olib tashlamaslik muhim emas.
Agar yakkalanib qolgan uchlar olib tashlanmasa, natijada bog‘lamli
bo'lmagan Gl grafni hosil qilishimiz ham mumkin. Grafdan
qirralami bunday olib tashlash amali, tabiiyki, grafning qirralari
sonini kamaytiradi, lekin grafdagi uchlaming darajalari juftligi
xossasini o‘zgartirmaydi. С grafning bog‘lamliligiga ko‘ra, C, sikl va G] graf
hech bo‘lmasa,bitta umumiy uchga ega bo‘lishlari kerak. Shu sababli, C, siklda
G] grafning qirralariga ham insident bo‘lgan qandaydir v 2 uch bor.
Bu v 2 uchdan boshlab faqat Gx grafning qirralaridan tashkil topgan yangi C'
siklni qurish mumkin. C' siklni qurish jarayoni faqat v 2 uchga kelib tugashi
mumkin.
Oldin qurilgan Cl siklni ikki qismga ajratamiz:
1) C, siklning v, uchidan boshlanib v 2 uchida tugovchi qismi (bu oddiy
zanjimi Cj(v1,v2) bilan belgilaymiz) va
2) Cj siklning v 2 uchidan boshlanib, v, uchida tugovchi qolgan qismi (C,
(v2 ,vj)).
U holda v, uchdan boshlab Cj(v1,v2) zanjiming qirralari bo‘ylab v2 uchga
boruvchi, keyin C'siklning barcha qirralaridan o‘tuvchi va, nihoyat, C,(v2 ,vj)
zanjiming qirralari bo‘ylab v[ uchga qaytib keluvchi yangi
C2=Cl(vl,v2) U C' U Cl(v2,vl)
siklni hosil qilish mumkin. Agar C 2 sikl Eyler sikli bo‘lsa,
teoremaning tasdig‘i isbotlandi desa b o ‘ladi. Aks holda yuqorida bayon
etilgan jarayonni takrorlaymiz.
Berilgan G grafdagi qirralar soni chekli bo‘lganligidan, bu jarayon
chekli jarayondir. Bu jarayonni yetarUcha takrorlagandan so‘ng, albatta, u Eyler
siklini qurish bilan yakunlanadi.
1-natija. Bog ‘lamli graf yarim Eyler graft b o ‘lishi uchun
undagiikkitadan ко ‘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 yechimi
mavjud emas, degan xulosaga kelamiz, ya’ni Kyonigsberg shahrining ixtiyoriy
qismida joylashgan uydan chiqib, Pregel daiyosi ustiga qurilgan yetti
ko‘prikdan faqat bir martadan o‘tgan holda yana o‘sha uyga qaytib kelish
mumkin emas.
Oriyentirlangan graflarda oriyentirlangan Eyler yolini 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 nga teng bo‘lgan berilgan Eyler grafida Eyler
zanjirini tuzishning Flyori algoritmini1 keltiramiz. Bu algoritmga ko‘ra,
grafning qirralari Eyler siklida uchrashi tartibi bo‘yicha 1 dan ngacha raqamlab
chiqiladi.](/data/documents/693d74e7-b329-4aa9-bfdc-be98ca0f4a82/page_10.png)










Mavzu: “Dirak va Ore teoremalari asosida Gamilton siklini topish algoritmi” MUNDARIJA KIRISH ........................................................................................................... 2 Dastlab graflar haqida qisqacha tarixiy ma’lumotlar, grafning abstrakt ......... 2 matematik tushuncha sifatidagi ta’rifi va u bilan bog‘liq boshlang‘ich .......... 2 tushunchalar, graflarning geometrik ravishda, maxsus turdagi ....................... 2 ko‘phad yordamida, qo‘shnilik va insidentlik matritsalari vositasida ............. 2 berilishi yoritiladi. So‘ngra grafning elementlari, mar .................................... 2 shrutlar va zanjirlar, grafning bog‘lamliligi tushunchasi, Eyler va ................. 2 Gamilton graflari. ............................................................................................ 2 . ........................................................................................................................ 2 I Bob. Graflar nazariyasi. ................................................................................ 2 1.1 Tarixi. .................................................................................................. 2 1.2 Graf tushunchasi Grafning to’plam nazariyasi bo’yicha ta’rifi. .......... 3 ................................................................................................................... 4 1.3 Graflar nazariyasining asosiy tushunchalari.Graflarni tasvirlash. ....... 5 ......................................................................................................................... 9 II Bob. Eler va Gamilton graflari. ................................................................... 9 2.1. Eler graflari. ........................................................................................ 9 2.2. Gamilton graflari. ............................................................................. 12 2.3. Dirak teoremasi. .............................................................................. 13 2.4. Ore teoremasi. ................................................................................. 14 XULOSA ....................................................................................................... 17 ADABIYOTLAR RO’YXATI ...................................................................... 19 ILOVALAR ................................................................................................... 20 ILOVA 1. Modul N1 boshlang’ich kodi. ................................................ 20 ILOVA 2. Modul N2 boshlang’ich kodi. ................................................ 20 ILOVA 3. Modul N3 boshlang’ich kodi. ................................................ 20
KIRISH Dastlab graflar haqida qisqacha tarixiy ma’lumotlar, grafning abstrakt matematik tushuncha sifatidagi ta’rifi va u bilan bog‘liq boshlang‘ich tushunchalar, graflarning geometrik ravishda, maxsus turdagi ko‘phad yordamida, qo‘shnilik va insidentlik matritsalari vositasida berilishi yoritiladi. So‘ngra grafning elementlari, mar shrutlar va zanjirlar, grafning bog‘lamliligi tushunchasi, Eyler va Gamilton graflari. . I Bob. Graflar nazariyasi. 1.1 Tarixi . 1736-yildaL. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi.Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yetti ko‘prikning joylashuvi 1 -rasmdagi qadimiy xaritada tasvirlangan.Pregel daryosi Kyonigsberg shahrini o‘sha davrda to ‘rt — А,B,Cva D)qismgabo‘lgan. Shahaming ixtiyoriy qismida joylashgan uydan chiqib, yetti ko‘prikdan faqat bir martadan o‘tib, yana o‘sha uyga qaytib kelish mumkinmi?Kyonigsberg ko‘priklari haqidagi bu masa lani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut Eyler sikli nomi bi lan yuritiladi) mavjudligi shartlari ham topildi. L. Eyleming bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo'yicha yagona ilmiy ish bo‘lib keldi. 1-rasm. Graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining
turli sohalarida qo‘llaniladi. Ulardan ba’zilari quyidagilardir. boshqotirmalami hal qilish; qiziqarli o‘yinlar; yo‘llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; avtomatlar, blok-sxemalar va kompyuter uchun programmalami tadqiq qilish va hokazo. Savollar: 1. Qanday masalaning qo'yilishi va yechilishi graflar nazariya sining paydo bo'lishiga asos bo‘ldi? 2. «Graf» iborasi birinchi bo‘lib kim tomonidan va qachon kiritilgan? 1.2 Graf tushunchasi Grafning to’plam nazariyasi bo’yicha ta’rifi. Graflarni o rganish bilan shug ullanadigan diskret matematikaning ʻ ʻ bo limi “Graflar nazariyasi” deb ataladi. Graflar nazariyasida ushbu ʻ matematik obyektlarning asosiy tushunchalari, xususiyatlari, tasvirlash usullari va qo llanilish sohalari batafsil ko rib chiqilgan. Bizni faqat ʻ ʻ dasturlashda muhim bo lgan jihatlari qiziqtiradi. ʻ Graflar - bu chiziqlar bilan bog langan nuqtalar to plami. Nuqtalar ʻ ʻ uchlar (tugunlar) chiziqlar esa qirralar (yoylar) deb nomlanadi. Grafning ifodalanishi. Grafning to plam nazariya bo yicha ta’rifi. Bizga bo sh ʻ ʻ ʻ bo lmagan to plam berilgan, masalan { ʻ ʻ ?????? 1, ?????? 2, ?????? 3, ?????? 4, ?????? 5}. Uning barcha ikki elementli ?????? (2)ichki to plamlari to plamini ʻ ʻ yozamiz. Bizning misolimiz uchun ushbu to plam quyidagicha bo ladi: ʻ ʻ 〈?????? , ??????〉 juftligi yo naltirilmagan G grafi deb nomlanadi, unda ʻ -uchlar to plami, ʻ ?????? - qirralarning to plami, ʻ ?????? (2)to plamining ichki ʻ to plami hisoblanadi.Yuqoridagilardan kelib chiqib, ushbu ta’rif odatda ʻ quyidagicha shakllantiriladi: 〈?????? , ??????〉 oriyentirlanmagan graflar juftligi deb ataladi, agar ?????? uchlar deb ataladigan bo sh bo lmagan elementlar to plami bo lsa ʻ ʻ ʻ ʻ va ?????? – ?????? dagi qirralar deb ataluvchi turli elementlarning tartibsiz juftlari to plami bo lsa. ʻ ʻ Graflar nazariyasida turli xil munosabatlarni yozishda VG yoki V(G) yozuvlari, G graf qirralarining to plami uchun EG yoki E(G) ʻ
yozuvlari ishlatiladi. Grafni namoyish qilishning vizual usuli - bu chizmalar (diagramma), unda uchlar nuqta, doiralar yoki boshqa figuralar bilan tasvirlangan va qirralar juft uchlari tasvirlarini bir-biriga bog laydigan ʻ chiziqlar bilan tasvirlangan. 2-rasm. Graf turlari. Graf - bu abstrakt obyekt bo lib, uchlar to plami (tugunlar) va ʻ ʻ qirralarning to plami - uchlar juftliklari orasidagi bog lanishlardan ʻ ʻ tashkil topadi (ulanishlar). Graf mavzusi juda keng. Graflar diskret matematikaning o rganish mavzusidir (bu yerda graf tushunchasining ʻ aniqroq ta’rifi berilgan). Graf murakkab tuzilgan ma’lumotni tavsiflash uchun ishlatiladi va shuning uchun katta amaliy ahamiyatga ega. Matematikada graflar paydo bo lishiga Eyler asarlari yordam berdi. ʻ Graflar bilan qayerda uchrashamiz? Ehtimol, ular bilan qayerda uchrashmasligimizni aytish osonroq. Ya’ni biz graflarda juda ko p ʻ holatda uchratamiz. Misol qilib quyidagilarni keltirishimiz mumkin: • Lokal yoki global tarmoq modeli • Algoritmlarning blok-sxemasi • Elektr sxemalar • Oila daraxti (Shajara) • Metro xaritasi • Ma’lumotlar bazasi modeli • Aqlli xaritalar Savollar: 1. Grafning abstrakt matematik tushuncha sifatidagi ta’rifini bilasizmi? 2. Grafning abstrakt ta’rifidagi juftlikni tashkil etuvchilar birbiridan nima bilan farq qiladi?
1.3 Graflar nazariyasining asosiy tushunchalari. Graflarni tasvirlash. Grafdagi marshrut - bu har bir uch (oxirgisidan tashqari) ketmaketlikdagi keyingi uchga qirra bilan bog langan uchlarningʻ cheklangan ketma-ketligi. Yo l - bu qirralarning takrorlanmagan yo lidir. Oddiy zanjir - bu ʻ ʻ uchlarni takrorlamaydigan marshrut (bu oddiy zanjirda takrorlanadigan qirralarning yo qligini anglatadi) ʻ Orgrafdagi yo naltirilgan marshrut (yoki yo l) - bu har bir ʻ ʻ element oldingi va keyingi qismga tushadigan uchlar va yoylarning cheklangan ketma-ketligi. Birinchi va oxirgi uchlar bir-biriga to g ri keladigan zanjirlar sikl ʻ ʻ deb ataladi . Yo lning (yoki siklning) uzunligi uni tashkil etuvchi qirralarning ʻ soni deyiladi Agar uning qirralari takrorlanmasa, yo l (yoki sikl) oddiy deb ʻ nomlanadi; agar u sodda bo lsa va undagi tepaliklar takrorlanmasa u ʻ elementar deb nomlanadi.