BUXORO DAVLAT UNIVERSITETI
AXBOROT-TEXNOLOGIYALAR FAKULTETI
1-2 PM GURUH TALABASI
____________________________ning
_________________________________________
FANIDAN
TAYYORLAGAN MUSTAQIL ISHI
REJA:
1.Graflar nazariyasi
2.Graflar ustida amallar
3. Eyler va Gamilton graflari
Dastlab graflar haqida qisqacha tarixiy ma’lumotlar, grafning abstrakt matematik tushuncha sifatidagi ta’rifi va u bilan boshlang’ich tushunchalar, grafning geometrik ravishda, maxsus turdagi ko’phad yordamida, qo’shnilik va insidentlik matritsalari vositasida berilishi yoritiladi. So’ngra grafning elementlari ustida sodda amallar, graflarni birlashtirish, biriktirish va ko’paytirish amallari, marshurtlar va zanjirlar, grafning bog’lamliligi tushunchasi, Eyler va Gamilton graflari, graflarda masofa tushunchasi, minimal masofali yo’l haqidagi masala, daraxt va unga ekvivalent tushunchalar, grafning siklomatik soni bayon qilinadi. Tarmoq tushunchasi, tarmoqdagi oqimlar, maksimal oqim haqidagi va bu masalalarni hal qilish uchun Ford algoritmidek tushunchalar ham bor.
GRAFLAR NAZARIYASINING BOSHLANG’ICH MA’LUMOTLARI
Graf, uch, qirra, yoy, yo’nalish, orgraf, qo’shni uchlar, yakkalangan uch, karrali qirralar, multigraf, psevdograf nolgraf, to’la belgilanganva izomorf graflar, grafning geometrik ifidalanishi, uchlar, qirralar va yoylar insidentligi.
Graflar nazariyasi haqida umumiy ma’lumotlar.
yilda L.Eyler tomonidan o’sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko’priklari haqidagi masalaning qo’yilishi va yechilishi graflar nazariyasining paydo bo’lishiga sabab bo’ldi. Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yetti ko’prikning joylashuvi 1-shakldagi qadimiy xaritada tasvirlngan.
Graflar nazariyasi bo’yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo’llaniladi. Ulardan ba’zilari quyidagilardir: boshqotirmalarni yechish, qiziqarli o’yinlar; yo’llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; avtomatlar, blok sxemalar va kompyuter uchun programmalarni tadqiq qilish va hokazo.
Grafning abstrakt ta’rifi va u bilan bog’liq tushunchalar. Avvalo , grafning abstrakt matematik tushuncha sifatidagi ta’rifini va boshqa ba’zi sodda tushunchalarni keltiramiz.
*Qandaydir bo’sh to’plam berilgn bo’lsin G= ko’rinishidagi juftlik bo’lib, bu yerda v-grafning uchlari to’plami, u rsa qirralar to’plami hisoblanadi.
*Yo’nalishga ega bo’lgan grafga oryentrlangan graf deyiladi.*Agar 2 ta uch biror qirra bilan tutashtirilsa, ular qo’shni uch deyiladi/
*2 ta qirra umumiy uchga ega bo’lsa, qo’shni qirralar bo’ladi.
*qo’shni uchlar, shu uchlarni tutashtiruvchi qirraga insident’ o’z navbtida bu qirra shu uchga insident deyiladi.
*Agar qirradagi uchlar bir xil bo’lsa, bu sirtmoqni tashkil qiladi.
*Sirtmoq bo’lgan graf psedograf deyiladi.
*Grafda bir xil qirralar mavjud bo’lsa, bunga karrali qirralar deyiladi. Bunday graf multigraf deyiladi.
*Agar grafning ixtiyoriy ikkita uchini tutashtiruvchi qirra mavjud bo’lsa, unda sirtmoq va karrali qirralar mavjud bo’lmasa to’l graf deyiladi.
m(m-1)/2
*Oryenntrlangan graf uchun bu formula, qirralar soni m(m-1) bo’ladi.
*Uchdan chiquvchi qirralar soni shu uchning lokal darajasini belgilaydi.
*Insidentlik matrisasi. Uchlar soni satrlarni, qirralar soni esa ustunlarni bildiradi.
1
2
3
4
5
Oryentrlangan graf uchun insidentlik matrisasi
aij=
Berilgan grafga mos bo’lgan to’plamni
1 2
F(G)==(x2 -x1)(x3-x2)…(xn-xn-1)
F(G)=(x3-x1)(x2-x1)(x3-x2)(x4-x3)
i lar karrali qirralar soni, xi lar uchlar soni, i lar sirtmoqlar soni.
Mashurtlar va zanjirlar
Bizga G graf berilgan bo’lsin, v={v1 , v2 , …vn}
G=
U={u1 , u2, …u n}
*Mashurt uchlar va qirralar ketma-ketligidan iborat to’plam, ya’ni {1, u1, 2, u2, 3, u3}.
*Zanjir bu mashurt bo’lib, bir uch ikki marta keladi, yurgan qirrasi orqali yana yurmaydi.
*Sirtmoq va karrali qirralarning o’zi zanjior bo’la oladi.
Graflar ustida amallar. Graflar ustida turli amallar bajarish mumkin, masalan, graflarni birlashtirish, biriktirish, ko’paytirish, grafniqismlarga ajratish va hokazo. Eng sodda amallardan biri sifatida grafdan uchni olib tashlashamalini keltirsa bo’ladi. Bu amalni qo’llash berilgan grafning uchlari to’plamidan birorta element yo’qotishni (olib tashlashni) anglatadi. Natijada uchlari soni bittaga kamaygan yangi graf hosil bo’ladi. Albatta, bu amalni uchlari soni ikkitadan kam bo’lgan graflar uchun qo’llash mumkin bo’lib, uni bajarish jarayonida olib tashlanayotgan uch bilan birgalikda shu uchga insident bo’lgan barcha qirralar (yoylar) ham olib tashlanadi. Eng sodda amallar qatoriga grafdan qirrani (yoyni) olib tashlash amalini ham kiritish mumkin. Bu amalga ko’ra berilgan grafning qirralari (yoylari) to’plamidan birorta element yo’qotiladi (olib tashlanadi). Berilgan grafdan qirrani
(yoyni) olib tashlayotganda shu qirraga (yoyga) insident uchlarni grafda qoldirish ham yo’qotish ham mumkin. Bu yerda vaziyatga qarab ish yuritiladi.
Eyler va Gamilton graflari
EYler graflari .
Graflar nazariyasining shakllanishi Kyoning-sberg ko’priklari haqidagi masala bilan bog’liq ekanligi yaxshi ma’lum. L. Eyler 1736-yilda bu masalaning yechimga ega emas ekanligini 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 sikliga) ega graf Eyler grafi deb ataladi. Agar grafda yopiq bo’lmagan Eyler zanjiri topilsa, u holda bunday graf yarim Eyler graf deyiladi.
1-teorema. Bog’lamli graf Eyler grafi bo’lishi uchun undagi barcha uchlarning darajalari juft bo’lishi zarur va yetarlidir.
Isboti. Zarurligi. G Eyler grafida C- Eyler sikli bo’lsin. U holda C 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 C sikldagi har bir qirraning bir marta uchrashi mumkinligidan kelib chiqadi.
Yetarliligi. Endi G grafning har bir uchi darajasi juft bo’lsin deb faraz qilamiz. G graf bog’lamli bo’lgani uchun undagi har bir uchning darajasi ikkidan kichik bo’lmasa, u holda bunday graftarkibida sikl mavjud.
Demak, G grafning qirralaridan tashkil topgan qandaydir C2 sikl bor. Bu siklni uning ixtiyoriy v uchidan boshlab quramiz. Dastlab v 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’tishlar jarayonida faqat qirraning yangisini tanlashga harakat qilinadi , uchlar esa istalgancha takrorlanishi mumkin.
Har bir uchga insident qirralar sonijuft bo’lgani uchun Cx siklni qurish jarayonida faqat vx uchga borgandagina tugaydi. Bu yerda ikki hol bo’lishi mumkin:
Cx sikl G grafning barcha qirralaridan o’tadi yoki
Cx siklgrafninf barcha qirralaridan o’tmaydi.
Birinchi holda teorema isbotlandi deyish mumkin. Ikkinchi holda G grafdan Cx siklga tegishli barcha qirralarni olib tashlaymiz va natijada hosil bo’lgan grafni Cx 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 Gx grafni hosil qilishimiz ham mumkin. Grafdan qirralarni bunday olib tashlash amali orqali tabiiyki, grafning qirralari soni kamayadi., lekin grafdagi uchlarning darajalari juftligi xossasini o’zgartirmaydi.
G grafning bog’lamliligiga ko’ra, Cx sikl va Cx graf hech bo’lsa, bittass umumiy uchga ega bo’lishlari kerak. Shu sababli Cx siklda Cx grafning qirralariga ham insident bo’lgan insident bo’lgan qandaydir v2 uch bor. Bu v uchdan boshlab faqat Gx grafning qirralaridan tashkil topgan yangi C siklni qurish mumkin. C siklni qurish jarayoni faqat v2 uchga kelib tugashi mumkin.
|
