48- rasm
1 Kyonigsberg (Konigsberg) – bu shahar 1255- yilda asoslangan bo‘lib, Sharqiy PrussiyadagiPregel 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 Modulning 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 asring 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, blok sxemalar va komp’yuter uchun programmalarni tadqiqqilish va hokazo.1
Graf – abstrakt tushuncha bo‘lib, obyektlar va ular orasidagi bog'liqliklarni tasvirlashda yoki ifodalashda ishlatiladi.
Obyektlari 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 u hamda v nomerli uchlari o‘zaro bog'liqligini bildiradi. Bunday juftliklarni grafning 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:
49-rasm 50-rasm
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. Shajara Ota-bola-nabira...
va h k.
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.
Ta’rif. Graf deb, shunday G1(X,E) ikki to‘plam juftligiga aytiladiki, bunda X-bo‘sh bo‘lmagan uchlar to‘plami {x1,,x2, … , xn} bo‘lib, E ning elementlari esa Xning ikki elementli to‘plam ostilaridir, ya’ni E={(x1,x2)}. Ushbu ikki elementli to‘plamostilar qirralari deb ataladi.
Masalan, G = ({х,, х2, х3, х4}, {(х,, х,), (х,, х2), (х,, х3), (х2, х3), (х3, х4)})
Murakkab bo‘lmagan graflarni grafik sxemalar orqali ifodalash maqsadga muvofiqdir, uyerdauchlarinuqtalardan, qirralari esa ularni birlashtiruvchi chiziqlardan iboratdir.
Shunday qilib graf erkin konstruksiyalardir.Bunda ikki uchlari orasidagi bog’lanishning bo‘lishi muhimdir, bir xilda ushbu bog’lanishni xarakteri muhimdir.
Agar x1 va x2lar qandaydir qirraga (xi , xj) ga tegishli bo‘lsa, u holda ushbu qirra xi vaxj “insindent” deyiladi, xi va xjlar 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‘lsa ular ikki va undan ko‘p uchlar bilan birlashtirilgan bo‘lsa bunday graf multi graf deyiladi. Ushbu uchga tegishli bo‘lgan qirralar soni uchning darajasini belgilaydi. 2.6rasmda ko‘rsatilgan x2 uch 6 darajaga ega, chunki unga α1, α2, α3, α4, α5, α6, α7 , qirralar “insindent”dir, x1uchning darajasi 3, x4ning darajasi esa 1.
51-rasm
Agar graf sirtmoqsiz yoki qirralari karrali bo‘lmasa, bunday graf oddiy graf deyiladi.Graf kvadrat jadval shaklida bo‘lishi mumkin.
|
