Toxirov javohirning diskret tuzulmalar fanidan mustaqil ishi

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYA UNIVERSITETI URGANCH FILIALI KOMPYUTER INJINIRINGI FAKULTETI

AXBOROT XAVFSIZLIGI (sohalar bo’yicha )
951-21 –GURUH TALABASI
TOXIROV JAVOHIRNING DISKRET TUZULMALAR FANIDAN MUSTAQIL ISHI

REJA
I-bob. Graflar nazariyasi elementlari.

1. 
   Graflar nazariyasi haqida umumiy ma’lumotlar
   
2. 
   Graflarning berilish usullari
   

1-bob
Mavzu : Graflar nazariyasi elementlari.
1.1 Graflar nazariyasi haqida umumiy ma’lumotlar.
1736-yilda Eyler tomonidan o’sha davrda qiziqarli bo’lgan amaliy masalalardan biri hisoblanganKuonidsberd ko’priklari haqidagi masalaning qo’yilishi va yechimlari graflar nazariyasining paydo bo’lishiga asosbo’lgan. XIXasrning o’rtalarida graflar nazariyasi bilan bog’liq tadqiqotlar G. Kichxdof va A. Kaliishlarida paydo bo’lgan.
“ Graf ” iborasi D.Kuopid tomonidan 1936- yilda graflar nazariyasiga bag’ishlangan dastlabki darslikda uchraydi. Graflar nazariyasibo’yicha tadqiqotlar natijalari inson faoliyatining turli soxalarida qo’llaniladi. Ulardan ba’zilari quyidagilar: boshqotirmalarni hal qilish, qiziqarli o’yinlar, yo’llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyixalashtirish, avtomatlar, blok – sxemalar kompyuter uchun programmalar tadqiq qilish va xokazo.
Avval grafning abstrakt ta’rifi va u bilan bog’liq boshlang’ich tushunchalarni keltiramiz . Grafning abstraktmatematik tushuncha sifatidagi ta’rifini va boshqa sodda tushunchalarni bayon qilamiz. V qandaydir bo’shbo’lmagan to’plam bo’lsin . Uning ʋ₁ϵV va ʋ₁ϵV elementlaridan tuzilgan < ʋ_1,ʋ₂ > ko’rinishdagi barcha juftliklar to’plamini VxV bilan belgilaymiz.
Graf deb shunday juftlikka aytiladiki, bu yerda V≠Ø va U-<ʋ_1,ʋ₂ >, ʋ₁ϵV,ʋ₂ϵV ko’rinishdagi juftliklar korteji bo’lib VxV to’plamning elementlaridan tuzilgandir.
Bundan keyin belgilash o’rniga VxU dan foydalanamiz. Grafning tashkil etuvchilarini ko’rsatish mumkin bo’lmasa, uholda uni lotin alifbosining bitta harfi bilanbelgilaymiz.G=(V,U) Graf berilgan bo’lsin. Vto’plamning o’zigaesa graf uchlari to’plami uchlari deyiladi.
Graflar nazariyasida“uch” o’rniga ba’zida tugun yoki nuqta iborasi ham ishlatiladi.
 G=(V,U) grafning ta’rifiga ko’ra,U bo’shkortej bo’lishi ham mumkin. Agar U bo’sh bo’lmasa u holda bu kortej (a,b) (a,b ϵV) ko’rinishdagi juftliklardan tashkil topadi, bunda a=b bo’lishi hamda ixtiyoriy (a,b) juftlik U kortejda istalgancha marta qatnashishi mumkin.
Agar (a,b) juftlik uchun uni tashkil etuvchilarning joylashuv o’rni ahamiyatsiz bo’lsa, ya’ni (a,b)=(b,a) bo’lsa (a,b) juftlikka yo’naltirilmagan qirra yoki qisqacha qirra deyiladi. Agar butartib muhim bo’lsa , ya’ni (a,b) ≠(b,a) bo’lsa (a,b) juftlikga yoy yoki yo’naltirilgan qirra deyiladi.
Ukortejning tarkibiga qarab, uni yo grafning qirralari korteji yo yoylari korteji , yoki qirralari va yoyalari korteji deb ataymiz.
Grafning uchlari va qirralari uningelementlari deyiladi. G=(V,U) graf yechimlarining soni ga tengdir, bu yerda G grafning uchlari soni va bilan uning qirralari soni belgilangan.
Grafning qirrasi, odatda uni tashkil etuvchi uchlar yordamida ( a,b) yoki ab yoki (a,b) ko’rinishda belgilanadi. Boshqa belgilashlar ham ishlatiladi : masalan, yoy uchun  yoki qirra uchun  , yoy yoki qirra uchun u ko’rinishda.
( a,b) va (b,a) yozuvlar bir biridan farq qiluvchi yoylarni ifodalaydi. Agar yoy (a,b) ko’rinishda ifodalangan bo’lsa, u holda uning boshlang’ich uchi b esa uning oxirga uchi deyiladi. Bundan tashqari, yoy (a,b) ko’rinishda yozilsa, u holda a uchidan chiquvchi va b uchga kiruvchi yoy deb aytiladi.
Qirra uchun uning (a,b) yozuvdagi harflar joylashish tartibi muhim rol o’ynamaydi va a va b elementlar qirraning uchlari deyiladi.
Agar grafda yo (a,b) qirra, yo (a,b) yoy yoki (b,a) yoy topilsa, u holda
a va b uchlar tutashtirilgan deyiladi. Agar grafning ikki uchini tutashtiruvchi qirra yoki yoy bor bo’lsa, u holda ular qo’shni uchlar, aks holda qo’shni bo’lmagan uchlar deyiladi.
Grafning ikki uchi qo’shni bo’lsa, ular shu uchlarni tutashtiruvchiqirraga intsident, o’z navbatida, qirra yoki yoy bu uchlarga intsident deyiladi. Grafda qirraumumiy chetga ega bo’lsa, ular qo’shni qirralar deyiladi.
Ba’zan graf undagielementlar soniga qarab, ya’ni uchlar soni m va qirralar soni n ga qarab belgilanadi va bu holda grafni (m,n) ni graf deb ataladi.
Agar G=(V,U) grafga U kartej faqat qirralardan iborat bo’lsa, u holda yo’naltirilmagan va faqat yo’naltirilgan qirralardan tashkil topgan bo’lsa, u holda u yo’naltirilgan qirra deyiladi. Agar grafda orientirlanmagan qirralar ham, orientirlangan qirralari ham bo’lsa, bunga aralash graf deyiladi.
Agar G=(V,U) grafga U kartej tarkibida VxV to’plamdan olingan takrorlanuvchi elementlarbo’lsa, u holda karrali yoki parallel qirralar deyiladi. Karrali qirralari yoki yoylari bo’lgan grafga multigraf deyiladi.
Umumiy holda uchlar to’plami V va qirralar korteji U cheksiz ko’p elementli bo’lishi mumkin. Bundan keyin V to’plam va U korteji faqat chekli bo’lgan G=(V,U) graflarni qaraymiz. Bunday graflar chekli graflar deyiladi.
Hech qanday qirrabilan bog’lamagan uchga yakkalangan uch deyiladi.Faqat yakkalangan uchlardan iborat grafga nol graf yoki bo’sh graf deyiladi.Uchlar soni ga teng bo’sh graf O_m yoki N_m kabi belgilanadi.
Istalgan ikki uchi sirtmoqsiz va karrali qirralarsiz orientirlanmagan grafga to’la graf deyiladi.Uchlar son m ga teng bo’lgan to’la graf K_m grafning qirralar soni  ga tengbo’ladi.
Agar grafning uchlariga qandaydir belgilar , masalan, 1,2,……m sonlari mos qo’yilgan bo’lsa, unga belgilangan graf deyiladi.
Agar G=(V,U) va G`=(V`,U`) graflarning uchlari to’plamlari, ya’ni V va V` to’plamlar asosida uchlarning qo’shnilik munosabatini saqlaydigan o’zaro bir qiymatli moslik o’rnatish mumkin bo’lsa, u holda G va G` graflar izomorf graflar deyiladi. Bu ta’rifni quyidagicha ifodalash mumkin: agar ixtiyoriy x,yϵV uchun bo’lsa u holda G va G` graflarizomorfdir. Agar ixomorf graflardan biri orientirlangan bo’lsa, u holda ikkinchisi ham albatta orientirlangan bo’lishi va ulardagi mos yoylarning yo’nalishlari ham bir biriga mos bo’lishi shart.
Graf uchiga intsident qirralar soni shu uchning lokal darajasi yoki qisqacha darajasi deyiladi. Grafdagi  uchning darajaini ρ(a) bilan belgilaymiz.
Agar grafning barcha uchlari bir xil r darajaga ega bo’lsa, u holda bunday graf r darajali regulyar graf deyiladi. Uch darajali regulyar grafga kubik grafdeyiladi.O_m graf nolinchi darajali regulyar graf deyiladi.
K_m esa (m-1) darajali regulyar graf bo’ladi.