logo
  1. Bosh sahifa
  2. Diplom ishlar
  3. Umumiy
  4. Dirak va Ore teoremalari asosida

Dirak va Ore teoremalari asosida

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

1641.9609375 KB
Ko'chirib olish
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. Graf turlari. Yo naltirilgan graf-(qisqacha orgraf)-qirralariʻ yo naltirilgan graf. ʻ Yo naltirilmagan graf - uchlar juftligi tartiblanmagan graf. ʻ Bog langan graf-bu har qanday uch juftligi o rtasida kamida bitta ʻ ʻ yo l mavjud bo lgan graf. ʻ ʻ Bog langan va bog lanmagan graflar. 2-rasmda ko rsatilganlar ʻ ʻ ʻ graflarni ikki guruhga bo lish mumkin (kesilgan chiziq bilan ajratilgan): ʻ bog lanmagan ( ʻ ?????? 1− ?????? 5) va bog langan ( ʻ ?????? 6− ?????? 11). Bog lanmagan graflarda qirralar bilan ulanmagan ikki yoki undan ʻ ortiq qismlar mavjud bo ladi. Ushbu qismlar bog lanish komponentlari ʻ ʻ deb ataladi. Yuqorida keltirilgan graflarda ?????? 1 da to rtta komponent, ʻ ?????? 2 da uchta komponent, ?????? 3, ?????? 4 ????????????⁡?????? 5 da 2 ta komponent mavjud, qolganlarida esa bittadan komponent mavjud. ?????? 6 va ?????? 11 graflari o rtasida ʻ ?????? 11 grafini alohida ajratib ko rsatish mumkin, chunki to rtinchi darajali graf uchun ʻ ʻ maksimal sondagi qirralarga ega. Umuman olganda zanjir – uchlar va qirralarning ( ?????? 0, ?????? 1, ?????? 1, ?????? 2, ?????? 2, … , ???????????? −1, ???????????? , ???????????? ) o zgaruvchan ketma-ketligi. ʻ Bu yerda ???????????? −1 va ???????????? ???????????? qirraning oxirlari hisoblanadi. Ushbu yozuvni qisqacha shaklda quyidagicha yozishimiz mumkin: ( ?????? 0, ?????? 1, … , ???????????? −1, ???????????? ) yoki ( ?????? 1, ?????? 2, … , ???????????? −1, ???????????? ). Umumiy turdagi oddiy zanjirdan farqli o laroq, u ʻ takrorlanadigan uchlarni o z ichiga olishi mumkin. Masalan, quyida ʻ keltirilgan graflarda ( ?????? 1, ?????? 2, ?????? 5, ?????? 4, ?????? 3) – oddiy zanjir, ( ?????? 1, ?????? 2, ?????? 5, ?????? 4, ?????? 1, ?????? 3) – zanjir. 3-rasm. Odatda zanjir mustaqil graf sifatida emas, balki ba’zi bir graflarning bir qismi sifatida qaraladi. Zanjirning uzunligi - uni tashkil etuvchi qirralarning soni. Oddiy zanjirning uzunligi o z ichiga olgan graf uchlari ʻ sonidan, umumiy zanjirning uzunligi esa ushbu graf qirralarining sonidan oshmasligi aniq. Graflar nazariyasida zanjir tushunchasi keng qo llaniladi. Masalan, ʻ bog langan grafni har qanday uchlar juftligi kamida bitta zanjir bilan ʻ bog langan graf sifatida belgilash mumkin. ʻ Sikllar. Sikl (oddiy sikl) - bu yopiq zanjir (oddiy zanjir). Oddiy siklga ?????? 8 grafi misol bo la oladi. Oddiy siklni ifodalovchi graf ʻ ???????????? ⁡ bilan belgilanadi. Zanjirlarda bo lgani kabi, sikllarni ba’zi bir graflarning ʻ 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 ʻ x vertikal qatorida "−1" va kiruvchi y uch qatorida "1" qiymatiga ega; agar uch va qirra o rtasida hech qanday bog liqlik bo lmasa, unda mos ʻ ʻ ʻ keladigan katak "0" qiymatiga ega bo ladi. ʻ 7-rasm. Yo’naltirilgan grafning insidentlik matritsasi. Savollar: 1. Grafning uchi deganda nimani tushunasiz? 2. Grafning qirrasi nima? 3. Grafning elementlari deganda nimani tushunasiz? 4. Grafdagi yoy bilan qirra bir-biridan nima bilan farq qiladi? 5. Qanday holda uchlar tutashtirilgan deyiladi? 6. Qo‘shni uchlarning qo'shni bo‘lmagan uchlardan qanday farqi bor? 7. Insidentlik tushunchasini bilasizmi? 8. Yo‘naltirilmagan graf va orgraf bir-biridan nima bilan farq II Bob. Eler va Gamilton graflari. 2.1. Eler graflari. Eyler graflari.Graflar nazariyasining shakllanishi Kyonigsberg ko‘priklari haqidagi masala bilan bog‘liq ekanligi yaxshi ma’lum. 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’madi? Grafning har bir qirrasidan faqat bir marta o‘tadigan zanjir Eyler zanjiri, deb ataladi. Yopiq Eyler zanjiriga (ya’ni Eyler sikliga) 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 uchlaming darajalari juft bo‘lishi zarur va yetarlidir. Isb o ti. Zarurligi. G Eyler graflda C —Eyler sikli bo‘lsin. U holda С sikl bo‘ylab harakatlanganda grafning har bir uchidan o ‘tish uchun bir juft qirradan foydalaniladi — bu qirralardan biri uchga kirish uchun, ikkinchisi esa uchdan chiqish uchun zarur bo‘ladi. Bu yerda har bir uch darajasining juftligi С sikldagi har bir qirraning bir marta uchrashi mumkinligidan kelib chiqadi. Yetarliligi. Endi Ggrafning har bir uchi darajasi juft bo‘lsin, deb faraz qilamiz. G graf bog‘lamli bo‘lgani uchun undagi har bir uchning darajasi ikkidan kichik emas. Ma’lumki, agar grafda har bir uchning darajasi ikkidan kichik bo‘lmasa, u holda bunday graf tarkibida sikl mavjud . Demak, G grafning qirralaridan tashkil etilgan qandaydir Cj sikl bor. Bu siklni uning ixtiyoriy Vj uchidan boshlab quramiz. Dastlab v, uchga insident bolgan ixtiyoriy bir qirrani tanlab, bu qirra 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 mum kin.Har bir uchga insident qirralar soni juft bo‘lgani uchun C, siklni qurish jarayoni faqat v, uchga borgandagina tugaydi. Bu yerda ikki hoi bo‘lishi mumkin: 1) Cj sikl Ggrafning barcha qirralaridan o ‘tadi yoki 2) C, sikl G grafning barcha qirralaridan o‘tmaydi. Birinchi holda teorema isbotlandi deyish mumkin. Tkkinchi holda Ggrafdan Cl siklga tegishli barcha qirralami olib tashlaymiz va natijada hosil bo‘lgan grafni Cx deb belgilaymiz. Bu yerda yakkalanib 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. Berilgan Eyler grafi uchun Flyori algoritmiga binoan quyidagi ikkita qoida asosida ishlar ketma-ket bajariladi: 1. Grafning ixtiyoriy v uchidan boshlab, bu uchga insident bo‘lgan istalgan qirraga (rnasalan,vv/ qirraga) 1 raqami beriladi. Bu qirra grafdan olib tashlanadi va v uchdan Vuchga (ya’ni olib tashlangan qirraga insident uchga) o ‘tiladi. 2. Oxirgi o‘tishdan oldingi o‘tish natijasida hosil bo‘lgan uch w bo‘lsin va oxirgi o‘tishda biror qirraga к raqami berilgan deylik. w uchga insident istalgan qirra imkoniyati boricha shunday tanlanadiki, bu qirrani olib tashlash grafdagi bog‘lamlilikni buzmasin. Tanlangan qirraga navbatdagi ( k + 1) raqami beriladi va bu qirra grafdan olib tashlanadi. Flyori algoritmiga ko‘ra, ish yuritish Eyler grafi uchun doimo chekli jarayon ekanligi va bu jarayon doimo grafdan barcha qirralarning olib tashlanishi, ya’ni Eyler zanjirini tuzish bilan tugashi isbotlangan. 1-misol. 8-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 uchlaming darajasi ikkiga, 2, 4, 6, 8 belgili uchlaming darajasi to‘rtga, 5 belgili uchning darajasi esa oltiga teng. Xullas, bu grafdagi barcha uchlaming darajalari juftdir. Shuning uchun, 1 -teoremaga ko‘ra, 8-rasmda tasvirlangan graf Eyler grafidir va uning tarkibida Eyler sikli mavjud. 8-rasm. Berilgan grafga flyori algo ritmini qo‘llab, mavjud Eyler sikllaridan birini aniqlaymiz. Dast- labki uch sifatida grafdagi 1 belgili uch olingan b o ‘lsin. Bu uchdan ikki y o ‘nalishda: (1;2) qirra b o ‘ylab yoki (1;4) qirra b o ‘ylab harakatlanish mumkin. Masalan, (1;2) qirra b o ‘ylab harakatlanib 2 belgili uchga o ‘tamiz. Endi harakatni 3 y o ‘nalishda: yo (2;3) qirra b o ‘ylab, yo (2;4) qirra b o ‘ylab, yoki (2;5) qirra b o ‘ylab davom ettirish mumkin. Aytaylik, (2;3) qirra b o ‘ylab harakatlanib 3 belgili uchga o ‘tgan boiaylik. Shu usulda davom etish mumkin b o ‘lgan Eyler sikllaridan birini, masalan, quyidagi siklni hosil qilamiz: ( (1 ,2 ) , ( 2 ,3 ) ,( 3 ,5 ) , (5 ,4 ), (4 ,6 ), ( 6 ,9 ), (9 ,8 ), (8 ,6 ), (6 ,5 ),( 5 ,8 ), (8 ,7 ), (7 ,5 ), (5 ,2 ), (2 ,4 ),(4 ,1 )). Savollar: 1. Eyler zanjiri deb nimaga aytiladi? 2. Yarim Eyler grafi Eyler grafidan nimasi bilan farqi qiladi? 3. Berilgan graf Eyler grafi bo‘lishligining zaruriy va yetarli sharti qanday ifodalanadi? 4. Berilgan graf yarim Eyler grafi bo‘lishligining zaruriy va yetarli sharti qanday ifodalanadi? 5. Oriyentirlangan Eyler grafi qanday aniqlanadi? 6. Lotin alifbosi bosma harflaming har biriga graf sifatida qarab ular orasidan Eyler grafi bo‘la olmay- diganlarini aniqlang. 2.2. Gamilton graflari. Gamilton (William Rowan Hamilton, 1805-1865) -Irlandiya matematigi, fizigi va astronomi. Gamilton graflari. Graflar nazariyasining natijalari muayya shartlarni qanoatlantiruvchi marshrutlarni topish masalasiga keltiriluvchi bir qator muammolarni hal etishda qo lla n ilishi mumkin. Shunday muammolardan biri sifatida Uilyam Gamilton nomi bilan bog‘liq masalani keltiramiz. U. Gamilton dodekaedmi tekshirib,uning har bir uchidan faqat bir marta o ‘tadigan siklni izlab topgan va shu asosda 1859-yilda «Olam b o ‘ylab sayohat» nomli o ‘yinni topgan.Grafning har bir uchidan faqat bir marta o ‘tadigan zanjir Gamilton zanjiri, deb ataladi. Yopiq G amilton zanjiriga (ya’ni Gamilton sikliga) ega graf Gamilton grafi, deb ataladi. Agar grafda yopiq b o ‘lmagan G am ilton zanjiri topilsa, u holda bunday graf yarim Gamilton grafi, deb ataladi. Oriyentirlangan graflarda ham grafning har bir uchidan faqat bir marta o ‘tuvchi oriyentirlangan sikllami qarash mumkin. Eyler va Gamilton graflari bir-birlariga o‘xshash ta ’riflansa-da, grafning Gamilton grafi ekanligini tasdiqlaydigan alomat (mezon) topish masalasi ancha murakkab hisoblanadi. Hozirgi vaqtgacha graflar nazariyasida grafning Gamilton grafi ekanligini tasdiqlovchi shartlami o ‘rganish b o ‘yicha izlanishlar davom etib, bu sohadagi ishlar hanuzgacha dolzarbligini y o ‘qotmasdan kelmoqda. Qandaydir shartlarga b o ‘ysunuvchi graflarda Gamilton sikli mavjudligi haqida bir necha tasdiqlar mavjud. Qator hollarda bu tasdiqlaming isbotlari konstruktiv bo‘lganligidan, Gamilton siklini tuzishga doir samarali algoritmlar ham yaratilgan. Savollar: 1. Gamilton zanjiri deb nimaga aytiladi? 2. Qanday grafga Gamilton grafi deb aytiladi? 3. Eyler va Gamilton graflarining o‘xshashligi va farqi bormi? 2.3. Dirak teoremasi. 1952-yilda G. E. Dirak1 quyidagi teoremani isbotladi. (Dirak (Dirac Gabriel Andrew, 1925—1984) — Daniya matematigi. Dirak teoremasining bu isboti D.J. Nyuman tomonidan keltirilgan.) 1-teorema (Dirak). Uchlari soni uchtadan kam b o ‘lmagan grafdagi istalgan uchning darajasi uchlar sonining yarmidan kam b o ‘lmasa, bu graf Gamilton grafi b o ‘ladi. I s b o ti 2. Uchlari soni m > 3 b o ‘lgan graf berilgan b o ‘lsin. Bu grafning istalgan v uchi uchun p(v ) > — shart bajarilsa-da, u Gamilton grafi b o ‘lmasin, deb faraz qilamiz. Tabiiyki, istalgan grafga yetarlicha sondagi yangi uchlarni q o ‘shib olib, bu uchlarning har birini grafdagi har bir uch bilan qirra orqali tutashtirsak, berilgan grafdan Gamilton grafini hosil qilish mumkin. Bu usul bilan berilgan grafdan Gamilton grafini hosil qilish uchun q o ‘shilayotgan zarur uchlarning minimal sonini к > 0 bilan belgilaymiz. Yuqorida bayon qilingan usulni qo'llash natijasida hosil b o ‘lgan grafdagi uchlardan tashkil topgan (v1,w,v2,...,v1) ketma-ketlikbiron Gamilton sikli b o ‘lsin, bunda v1 v2 — berilgan grafning uchlari, w esa q o ‘shib olingan uchlardan biri. Tushunarliki, v2 uch vl uchga q o ‘shni emas, aks holda siklni tuzishda w uchni ishlatmasligimiz mumkin b o ‘lar edi. Bu esa к sonining minimalligiga ziddir. Agar grafdagi v’1, uch v1, uch bilan q o ‘shni, v’2 uch esa v2 uch bilan q o ‘shni b o ‘lsa, v2 uch siklda v, uchdan bevosita keying uch b o ‘la olmaydi, chunki bu holda (v1,w ,v2,..., v’1, v’2,.- - , v1) siklni (v1,v’1 ,...,v 2,v’ 2, v1) siklga almashtirish mumkin. Natijada hosil b o ‘lgan grafning v2 uchga q o ‘shni b o ‘lmagan uchlari soni v, uchga q o ‘shni uchlari sonidan kichik emasligi (ya’ni bu son kamida (ga teng ekanligi) ravshan. Boshqa tomondan esa hosil b o ‘lgan grafning v, uchga qo‘shni uchlari soni kamida (m/2+k) gatengligi ko‘rinib turibdi. Hosil b o ‘lgan grafning har bir uchi bir vaqtning o ‘zida v2 uchga q o ‘shni ham, q o ‘shnimas ham bo'lishi mumkin emasligidan hosil bo‘lgan graf uchlarining umumiy soni m ( m + k ) ushbu 2(m/2+k)=m+2k sondan kichik emas, y a ’ni m+k > m + 2 к . Oxirgi tengsizlik faqat k = 0 bo‘lgandagina to ‘g ‘ridir. Bu esa k>0 shartiga ziddir. Dirak teo rem a si shartlari berilgangrafning Gamilton grafi bo‘lishi uchunyetarli, lekin ular zaruriy emas. Bu tasdiqto ‘g ‘ri ekanligini 9- rasmda tasvirlangangraf misolida ko‘ramiz. Bu grafda sakkizta uch b o iib (m=8 >3), har bir v ( v = l,8 )uchning darajasi 3 ga teng: p (v)=3. Dirak teo rem a sidagi p ( v ) >(m/2) — shart grafdagi hech qaysi uch uchun bajarilmasa ham , bu grafda ( 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8,1) ko‘rinishdagi Gamilton sikli bor b o lg a n i uchun u Gamilton grafidir. 9-rasm. Savollar: 1. Berilgan graf Gamilton grafi bo‘lishining yetarli shartlari haqidagi Dirak teoremasi qanday ifodalanadi? 2.4. Ore teoremasi. Ore (Oysten, 1899—1968) — Norvegiya matematigi. 1960-yilda O. Ore1 quyidagi teoremani isbotladi. 3-teorema (Ore). Agar uchlari soni m ga (m>2) teng bo'lgan grafdagi q o ‘shni b o ‘lmagan ixtiyoriy uchlar darajalari y ig ‘ndisi m dan kam bo ‘Imasa, и holda bu graf Gamilton grafi bo ‘ladi. I s b o ti o ‘quvchiga topshiriq sifatida beriladi. 2-misol. 10-rasmda tasvirlangan graflar Gamilton graflariga misol b o ‘la oladilar. Bir qarashdayoq sezish mumkinki, bu graflaming har birida bir nechtadan G am ilton sikllari mavjud. Mumkin b o ‘lgan ba’zi Gamilton sikllari shaklda qalin chiziqlar bilan ifodalangan. 10-rasm. 3-misol. Shaxmat o ‘yinidagi otning yurishi haqidagi Eyler masalasi deb ataluvchi quyidagi masalani qaraymiz. Shaxmat taxtasidagi istalgan katakda turgan shaxmat oti uchun yurishlarning shunday ketma-ketligini tuzingki, u barcha kataklardan faqat bir martadan o ‘tsin va yurish boshlangan katakka qaytib kelsin. Bu masalani hal qilish maqsadida tuzilgan graf (shaxmat taxtasidagi kataklarga grafning uchlari, otning yurishlariga esa uning qirralari mos qo ‘yilishi nazarda tutilmoqda) ham Gamilton grafiga m isol b o ‘la oladi. Bu masalaning yechimlaridan biri 11-rasmda keltirilgan. 11-rasm. 4-misol 12-rasmda tasvirla n g a n g rafd a G a m ilt o n zanjiri mavjud emas. Berilgan grafda Gamilton zanjirining mavjudligi shartlarni o ‘rganish b o ‘yicha izlanishlar davom etayotganligi va bu s o h a d a g i ish la r b u g u n g i kunda ham d o lza rb lig in iy o 'q o tm a g a n lig i yuqorida qayd etilgan edi. 12-rasm. Grafdagi uchlar soni mning qiymatiga nisbatan ko‘phad bilan chegaralangan sondagi qadam ishlatib istalgan grafda Gamilton zanjiri mavjudligini tekshiradigan algoritm hozirgacha topilmagan. Shuning uchun ham G amilton zanjirini topish masalasi graflar nazariyasida markaziy masalalardan biri bo ‘lib qolmoqda, Albatta, grafdagi m ta uchlarning m\ta turli ketma-ketliklarini (aniqrog‘i, takrorlanmaydigan o ‘rin almashtirishlarini) tuzib grafda Gamilton zanjirimavjudligi masalasini hal qilish mumkin. Shunday b o ‘lishiga qaramasdan, barcha m\ta o ‘rin almashtirishlarini bajarmasdan qadamlar sonini jiddiy qisqartiradigan umumiy algoritm bor. Grafda G amilton zanjirini topishmasalasi quyidagi kommivoyajer(Kommiovoyajer-sayohatchi reklamachi, gumashta.) masalasideb ataluvchi masalada oshkora namoyon bo‘ladi. Bir-birlari bilan yo‘llar (graf qirralari) vositasida bog‘langan shaharlar (graf uchlari) tarmog‘i berilgan bo‘lib, shaharlaming har bir (a,/?) jufti uchun masofa (uni fi(a,b) bilan belgilaymiz) mos qo‘yilgan hamda o‘zaro bog‘lanmagan shaharlar orasidagi masofa cheksiz katta deb hisoblaymiz. Kommivoyajer uchun shunday Gamilton sikli topish kerakki, ifodaning qiymati minimal bo‘lsin, bu yerda a. — tarmoqdagi i = shahar ( i=0, n ). Boshqacha aytganda, kommivoyajeming biron shahardan chiqib va qolgan barcha shaharlardan faqat bir martadan o‘tib, yana dastlabki shaharga qaytishi imkonini beruvchi eng kichik umumiy uzunlikka ega bolgan yo‘lni topish kerak. Savollar: 1. Ore teoremasida berilgan graf Gamilton grafi boMishining qanday yetarli shartlari keltirilgan? 2. Eyler va Gamilton graflari qo‘llanilib hal qilinadigan qanday amaliy masalalarga misol keltira olasiz? XULOSA Graflarni biz qayerlarda 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 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. Graflarning har bir uchidan faqat bir marta o’tadigan zanjir Gamilton zanjiri hisoblanadi.Eler va Gamelton graflari bir-biriga o’xshash ta’riflansada grafning Gamilton grafi ekanligini tasdiqlaydigan alomat (mezon) toppish masalasi ancha murakkab hisoblanadi.Hozirgi vaqtgacha grafningGamilton grafi ekanligini tasdiqlovchi shartlarni o’rganish bo’yicha izlanishlar davom etib busohadagi ishlar hanuzgacha dolzarbligini yo’qotmasdan kelmoqda. Qandaydir shartlarga bo’ysinuvchi graflarda Gamilton sikli mavjudligi haqida bir nechta tasdiqlar mavjudQator hollarda butasdiqlar strukturaviy bo’lganligidan,Gamilton siklini tuzishga doir samarali algoretmlar ham yaratilgan. Bularga:Dirak va Ore teoremalari. (Dirak teoremasi) - Uchlari soni uchtadan kam bo‘lmagan grafdagi istalgan uchning darajasi uchlar sonining yarmidan kam bo‘lmasa, bu graf Gamilton grafi bo‘ladi (Ore teoremasi) - Agar uchlari soni m ga (m>2) teng bo'lgan grafdagi q o ‘shni b o ‘lmagan ixtiyoriy uchlar darajalari y ig ‘ndisi m dan kam bo ‘Imasa, u holda bu graf Gamilton grafi bo ‘ladi. Lekin bu teoremalar faqatgina yetarli, zarur emas. Berilgan grafda Gamilton zanjirining mavjudligi shartlarni o ‘rganish bo‘yicha izlanishlar davom etayotganligi va bu sohadagi ishlar bugungi kunda ham dolzarbligini yo'qotmaganligi yuqorida qayd etilgan edi. Grafdagi uchlar soni m ning qiymatiga nisbatan ko‘phad bilan chegaralangan sondagi qadam ishlatib istalgan grafda Gamilton zanjiri mavjudligini tekshiradigan algoritm hozirgacha topilmagan. Shuning uchun ham Gamilton zanjirini topish masalasi graflar nazariyasida markaziy masalalardan biri bo‘lib qolmoqda. Bunday algoretm topilsa ya’ni grafda Gamilton zanjirini topish masalasi kommivoyajer(Kommiovoyajer – sayohatchi reklamachi,gumashta) masalasi va boshqa tegishli masalalar yechimini toppish mumkin. Bu ma’lumotlar haqida ijtimoiy tarmoqlar va bir nechta adabiyotlardan oldim. Olingan natijalar va xulasalardan ishlab chiqgan taklif va mulohazalarim quyidagicha: Istalgan berilgan grafda Gamilton sikli mavjudligini tekshirish bo’yicha Dirak va Ore teoremalaridan mulohazalarim asosida grafdagi gamelton sikli mavjudligini topish algoretmining o’zimning shaxsiy shartlarimni tuzdim va u quyidagicha teorema yaratdim: Teorema: Uch(V)lari soni 3 dan kam bo’lmagan (V>=3) grafda qirra(U)lari soni uch(V)lari sonidan kam bo’magan (U>=V) va istalgan uchining daraja(D)si 2 dan katta yoki teng bo’lgan (D>=2) graf Gamilton grafi bo’la oladi. Izoh:Bu teorema asosida grafda Gamilton sikli mavjudligi bu istalgan uchdan boshlaganda barcha uchlarga borishi uchun shu uchlar sonicha qirra mavjud bo’lishi kerak ya’ni har bir uchga o’tish uchun bitta yo’l, undan tashqari istalgan uchga kirish qirra bo’lsa chiqish qirrasi ham bo’lishi kerak ya’ni istalgan uchning darajasi 2 dan katta yoki teng bo’ladi. ADABIYOTLAR RO’YXATI - Algoritm va MS o'quv qo'llanma (Yusupov, Eshonqulov) - H.TO‘RAYEV,I.AZIZOV,S.OTAQULOV KOMBINATORIKA VA GRAFLAR NAZARIYASI ILOVALAR ILOVA 1. Modul N1 boshlang’ich kodi. ILOVA 2. Modul N2 boshlang’ich kodi. ILOVA 3. Modul N3 boshlang’ich kodi.

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.

O'xshashlar

DIRAK VA ORE TEOREMALARI ASOSIDA GAMILTON SIKLINI TOPISH ALGORITMI
Niderlandiya bayrog’i masalasi asosida saralash
Al2O3 ASOSIDA MEZOG‘AVAK SORBENTLAR SINTEZI VA ULARNINIG TEKSTUR XARAKTERISTIKALARI
C++ da ko‘rsatkichlar asosida massiv yaratish
Qadimgi va o‘rta asrlarda Koreya san’ati. (arxeologik va yozma manbalar asosida) mavzusida