eyler va gamilton grafiklari

DOCX 7 sahifa 296,0 KB Bepul yuklash

7 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 296,0 KB

Fayl turi DOCX

Sahifalar 7

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 7

mavzu: eyler va gamilton[footnoteref:1] graflari [1: gamilton (william rowan hamilton, 1805-1865) – irlandiya matematigi, fizigi va astronomi.] graf. uch. qirra. sikl. eyler zanjiri. eyler sikli. eyler grafi. yarim eyler grafi. oriyentirlangan eyler yo‘li. oriyentirlangan eyler grafi. flyori algoritmi. gamilton zanjiri. gamilton sikli. gamilton grafi. yarim gamilton grafi. kommivoyajer masalasi. 1. 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‘ladi? grafning har bir qirrasidan faqat bir marta o‘tadigan zanjir eyler zanjiri deb ataladi. yopiq eyler zanjiriga (ja’ni eyler sikliga) ega graf eyler grafi deb ataladi. agar grafda yopiq bo‘lmagan eyler zanjiri topilsa, u holda bunday graf yarim eyler grafi deb ataladi. 1- teorema. bog‘lamli graf eyler grafi bo‘lishi uchun undagi barcha …

2 / 7

lab quramiz. dastlab uchga insident bo‘lgan 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‘tislar jarayonida faqat qirraning yangisini tanlashga harakat qilinadi, uchlar esa istalgancha takrorlanishlari mumkin. har bir uchga insident qirralar soni juft bo‘lgani uchun siklni qurish jarayoni faqat uchga borgandagina tugaydi. bu yerda ikki hol bo‘lishi mumkin: 1) sikl grafning barcha qirralaridan o‘tadi, yoki 2) sikl grafning barcha qirralaridan o‘tmaydi. birinchi holda teorema isbotlandi deyish mumkin. ikkinchi holda grafdan siklga tegishli barcha qirralarni olib tashlaymiz va natijada hosil bo‘lgan grafni deb belgilaymiz. bu yerda yakkalanib qolgan uchlarni olib tashlash yoki olib tashlamaslik muhim emas. agar yakkalanib qolgan uchlar olib tashlanmasa, natijada bog‘lamli bo‘lmagan grafni hosil qi-lishimiz ham mumkin. grafdan qirralarni bunday olib tashlash amali, tabiiyki, grafning qirralari sonini kamaytiradi, lekin grafdagi uchlarning darajalari juftligi …

3 / 7

a yuqorida bayon etilgan jarayonni takrorlaymiz. berilgan grafdagi qirralar soni chekli bo‘lganligidan, bu jarayon chekli jarayondir. bu jarayonni yetarlicha takrorlagandan so‘ng, albatta, u eyler siklini qurish bilan yakunlanadi. ■ 1- natija. bog‘lamli graf yarim eyler grafi bo‘lishi uchun undagi ikkitadan ko‘p bo‘lmagan uchlarning 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 mavjud emas degan xulosaga kelamiz, ya’ni kyonigsberg shahrining ixtiyoriy qismida joylashgan uydan chiqib pregel daryosi ustiga qurilgan yettita ko‘priklardan 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 ga teng bo‘lgan berilgan eyler grafida eyler zanjirini …

4 / 7

ki, bu qirrani olib tashlash grafdagi bog‘lamlilikni buzmasin. tanlangan qirraga navbatdagi () 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. shuni ham ta’kidlash kerakki, flyori algoritmini qo‘llash jarayonida qirralarni tanlash imkoniyatlari ko‘p bo‘lgani uchun, bunday vaziyatlarda, algoritmni qo‘llash mavjud eyler sikllaridan birini topish bilan cheklanadi. tushunarliki, flyori algoritmini takror qo‘llab (bunda qirralarni tanlash jaroyoni algoritmini avvalgi qo‘llashlardagidek aynan takrorlanmasligi kerak) grafda mavjud bo‘lgan barcha eyler sikllarini topish mumkin. 1- misol. 1- shaklda tasvirlangan grafni qaraymiz. avvalo 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 uchlarning darajasi ikkiga, 2, 4, 6, 8 belgili uchlarning darajasi to‘rtga, 5 belgili uchning darajasi esa oltiga teng. xullas, bu grafdagi barcha uchlarning …

5 / 7

i qanoatlantiruvchi marshrutlarni topish masalasiga keltiriluvchi bir qator muammolarni hal etishda qo‘llanilishi mumkin. shunday muammolardan biri sifatida uilyam gamilton nomi bilan bog‘liq masalani keltiramiz. u. gamilton dodekaedrni tekshirib, uning har bir uchidan faqat bir marta o‘tadigan siklni izlab topgan va shu asosda 1859 yilda “olam bo‘ylab sayohat” nomli o‘yinni topgan. grafning har bir uchidan faqat bir marta o‘tadigan zanjir gamilton zanjiri deb ataladi. yopiq gamilton zanjiriga (ja’ni gamilton sikliga) ega graf gamilton grafi deb ataladi. agar grafda yopiq bo‘lmagan gamilton zanjiri topilsa, u holda bunday graf yarim gamilton grafi deb ataladi. oriyentirlangan graflarda ham grafning har bir uchidan faqat bir marta o‘tuvchi oriyentirlangan sikllarni qarash mumkin. uilyam gamilton eyler va gamilton graflari bir-birlariga o‘xshash ta’riflansada, grafning gamilton grafi ekanligini tasdiqlaydigan alomat (mezon) topish masalasi ancha murakkab muammo 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. …

Ko'proq o'qimoqchimisiz?

Barcha 7 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"eyler va gamilton grafiklari" haqida

mavzu: eyler va gamilton[footnoteref:1] graflari [1: gamilton (william rowan hamilton, 1805-1865) – irlandiya matematigi, fizigi va astronomi.] graf. uch. qirra. sikl. eyler zanjiri. eyler sikli. eyler grafi. yarim eyler grafi. oriyentirlangan eyler yo‘li. oriyentirlangan eyler grafi. flyori algoritmi. gamilton zanjiri. gamilton sikli. gamilton grafi. yarim gamilton grafi. kommivoyajer masalasi. 1. 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‘ladi? gr...

Bu fayl DOCX formatida 7 sahifadan iborat (296,0 KB). "eyler va gamilton grafiklari"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: eyler va gamilton grafiklari DOCX 7 sahifa Bepul yuklash Telegram