Graflar nazariyasining elementlari Reja

42-ma’ruza. Graflar nazariyasining elementlari

Reja:

1. 
   Graflar nazariyasi haqida umumiy ma’lumotlar
   
2. 
   Graflar haqida tushuncha va uning ta’rifi.
   
3. 
   Graflar va ularning turlari.
   

Graflar nazariyasi haqida umumiy ma’lumotlar. 1736- yilda L.Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg1 ko'priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi.

Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko'prikning joylashuvi 1- shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7 raqamlar bilan belgilangan. Pregel daryosi Kyonigsberg shahrini o‘sha davrda to‘rtta A , В , С va D qismlarga bo‘lgan. Shaharning ixtiyoriy qismida joylashgan uydan chiqib yettita ko‘prikdan faqat bir martadan o‘tib, yana o‘sha uyga qaytib kelish mumkinmi?

1. 
   shakl
   

1 Kyonigsberg (Konigsberg) - bu shahar 1255- yilda asoslangan bo'lib, Sharqiy Prussiyadagi

Pregel daryosi qirg‘oqlarida joylashgan. 1946- yildan boshlab Kaliningrad, hozir Rossiya Federatsiyasi tarkibida.
Kyonigsberg ko‘priklari haqidagi bu masalani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut Eyler sikli nomi

bilan yuritiladi, ushbu bobning 5- paragrafiga qarang) mavjudligi shartlari ham topildi. Bu natijalar e’lon qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan. L. Eyleming bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo‘yicha yagona ilmiy ish bo‘lib keldi. IX asming o‘rtalarida graflar nazariyasi bilan bog‘liq tadqiqotlar G. Kirxgof1 va A. Keli2 ishlarida paydo bo‘ldi.

“Graf’ iborasi D. Kyonig tomonidan 1936- yilda graflar nazariyasiga bag`ishlangan dastlabki darslikda uchraydi. 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, bloksxemalar va komp’yuter uchun programmalarni tadqiq qilish va hokazo.¹
Graf - bu abstrakt tushuncha bo'lib, obyektlar va ular orasidagi bog'liqliklarni tasvirlashda yoki ifodalashda ishlatiladi.

Obyektlarni ko'p hollarda nuqtalar bilan belgilab olinadi va ularga nomer beriladi. Bu grafning uchlari deb ham ataladi. Grafning uchlarini sonlar to'plami sifatida qaraymiz va uni V harfi bilan belgilaymiz. Grafning uchlarini 1 dan N gacha nomerlash mumkin (yoki 0 dan n - 1 gacha)

Graf uchlari orasidagi bog'liqliklarni sonlar jufti bilan belgilaymiz (ui ,  vi)  va bu grafning ui  hamda  vi  nomerli  uchlari o'zaro bog'liqligini bildiradi. Bunday juftliklarnigrafning qirralari deyiladi va ular E harfi bilan belgilanadi. E to'plam elementlari juftlik sonlardan iborat.

Demak, ixtiyoriy grafni uning uchlarini bildiruvchi to'plam V va qirralarini bildiruvchi to'plam E bilan berish mumkin. Grafni G harfi belgilasak, uni quyidagicha ifodalash mumkin: G(V, E). Bundan tashqari graflarni oddiygina qilib rasmli ko'rinishda tasvirlash mumkin. Bunda uchlari uchun nuqtalar qo'yib, keraklilarini chiziqlar bilan tutashtiramiz. Qizig'i shundaki, bu yoqda nuqtalarning o'rni ahamiyatga ega emas, faqat bog'liqliklar ko'rinsa bo'ldi. Graflarni bu usulda tasvirlash ularga oid misollarni qo'lda yechganda, yoki tahlil qilganda juda qo'l keladi.

Graflarga misol:

                                     

Graflarga juda ko'plab misollar keltirish mumkin:

1) Ixtiyoriy tarmoq - graf. Bunda tarmoq elementlari va ular orasidagi bog'lanishlar bor.

2) Shaharlar va ularni tutashtiruvchi yo'llar

3) Kishilar va ular orasidagi bog'liqliklar. Ota-bola-nabira...

va hk.
Graf qirralari yo'nalishiga qarab ikki xil bo'lishi mumkin:

1)Bir tomonlama yo'nalgan qirra

2) Ikki tomonlama yo'nalgan qirra

Bir tomonlama yo'nalgan qirra deb belgilanadi va bunda bog'liqlik faqat ui - uchdan vi - uchga yo'nalgan bo'ladi, aksi noto'g'ri. Masalan, ...  Bunday graflarga yo'naltirilgan graflar ham deyiladi.

Ikki tomonlama yo'naltirilgan qirralar oddiy (ui, vi) kabi belgilanadi va bunda bog'liqlik ikki tomonlama bo'ladi. Ya'ni vi dan ui ga ham bo'ladi. Bunday graflarga yo'naltirilmagan graflar ham deyiladi.

Qirralarning og'irliklariga qarab ular quyidagicha bo'ladi:

1) Og'irligi bor qirralar

2) Og'irligi yo'q qirralar (og'irligi 1 ga teng)

Og'irligi bor qirralarda  (ui, vi)  dan tashqari uning og'irligi -   ci  ham beriladi. Bu, masalan, yo'lni graf qirrasi deb oladigan bo'lsak, uning o'tkazuvchanlik darajasi yoki og'irlik limiti bo'lishi mumkin. Bunday graflarni .. graflar deyiladi. (o'zbekchasi qanaqa bo'ladi?

Ta’rif. Graf deb, shunday G₁(X,E) ikki to’plam juftligiga aytiladiki, bunda X-bo’sh bo’lmagan uchlar to’plami {x_1,,x₂, … , x_n} bo’lib, E ning elementlari esa X ning ikki elementli to’plam ostilaridir, ya’ni E={(x₁,x₂)}. Ushbu ikki elementli to’plam ostilar qirralari deb ataladi.

Masalan, G = ({х,, х₂, х₃, х₄}, {(х,, х,), (х,, х₂), (х,, х₃), (х₂, х₃), (х₃, х₄)})

Murakkab bo’lmagan graflarni grafik sxemalar orqali ifodalash maqsadga muvofiqdir, u yerda uchlari nuqtalardan, qirralari esa ularni birlashtiruvchi chiziqlardan iboratdir.²

Ushbu sxemalarda chiziqlar uzunligi, eni va shakli hech qanday ahamiyatga ega emas.

Graflarga misollar³

Shunday qilib graf erkin konstruksiyalardir. Bunda ikki uchlari orasidagi bog’lanishning bo’lishi muhimdir, bir xilda ushbu bog’lanishni xarakteri muhimdir.

Agar x₁ va x₂lar qandaydir qirraga (x_i , x_j) ga tegishli bo’lsa, u holda ushbu qirra x_i va x_j “insindent” deyiladi, x_i va x_j lar esa qo’shni nuqtalar deyiladi. Agar qirra bir nuqtaga “insindent” bo’lsa, u sirtmoq deyiladi.

Hech qanday qirraga “insindent” bo’lmagan uch ajratilgan uch deyiladi. Agar grafda shunday uchlar bo’lsaki ular ikki va undan ko’p uchlar bilan birlashtirilgan bo’lsa bunday graf multigraf deyiladi. Ushbu uchga tegishli bo’lgan qirralar soni uchning darajasini belgilaydi. 2.6rasmda ko’rsatilgan x₂ uch 6 darajaga ega, chunki unga α₁, α₂, α₃, α₄, α_5, α_6, α₇ , qirralar “insindent”dir, x₁ uchning darajasi 3, x₄ ning darajasi esa 1.

Agar graf sirtmoq siz yoki qirralari karrali bo’lmasa, bunda graf oddiy graf deyiladi. Graf kvadrat jadval shaklida bo’lishi mumkin.