1

Mavzu: 1. Graflar Nazariyasi

Graflar nazariyasi bo'yicha

1. Graflar Nazariyasi ga javob

                     Graflar nazariyasidan tushunchalar   


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 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:


                    http://acm.tuit.uz/forum/img/m/3/t/p16v1f10l7pk1pai7qlne61o0l1.jpg                 http://acm.tuit.uz/forum/img/m/3/t/p16v1ftnkghvksui1rqpju4f241.jpg


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 <ui, vi> 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? Взвешанный граф)

1. Graflar Nazariyasi ga javob

daasturlashda grafdan foydalanish? C# tili misolda?