Mavzu: Grafning metrik xarakteristikalari

Muammoli masala va topshiriqlar

1. 
   4- shaklda tasvirlangan grafning diametri, radiusi va markaz(lar)ini toping.
   
2. 
   Petersen grafining markazini toping.
   
3. 
   Kyonigsberg ko‘priklari haqidagi masalaga mos grafning diametri va markazini toping.
   
4. 
   Uchta uy va uchta quduq haqidagi masalaga mos grafning diametri va radiusini toping.
   
5. 
   Insidentlik matritsasi quyida berilgan grafning diametri, radiusi va markaz(lar)ini aniqlang:
   

.

6. 
   Uchlari to‘plamlari kesishmaydigan va graflarga birikma amalini qo‘llash natijasida hosil bo‘lgan grafning diametri va radiusini aniqlang.
   
7. 
   Qirralari qo‘shniligi matrisasi quyida berilgan graflarning radiuslarini aniqlang:
   

a) , b) .

8. 
   
   Deykstra algoritmini 5- shaklda tasvirlangan grafga qo‘llab, eng qisqa uzunlikka ega yo‘lni toping.
   
9. 
   Siz yashayotgan hududda har bir aholi punktidan boshqasiga bevosita borish mumkin bo’lgan yo’llarni va ular-ning uzunliklarini aniqlang. Bu ma’lumotlarga mos ke-luvchi graf tuzing va Deykstra algoritmini qo’llab, o’zingiz yashayotgan aholi punktidan boshqa aholi punktiga borish mumkin bo’lgan yo’llarning eng qisqa uzunlikka ega bo’lganlarini toping.
   

Mustaqil ishlash uchun savollar

1. 
   Graf uchlari orasidagi masofa deb nimaga aytiladi?
   
2. 
   Graf uchlari orasidagi masofa metrikaning qanday aksiomalarini qanoatlantiradi?
   
3. 
   Metrika aksiomalarining qaysi biri uchburchak tengsizligi aksiomasi deb ataladi?
   
4. 
   Graf uchining ekssentrisiteti deganda nimani tushunasiz?
   
5. 
   Grafning diametri deb nimaga aytiladi?
   
6. 
   Diametral zanjir nima?
   
7. 
   Grafning radiusi qanday aniqlanadi?
   
8. 
   Grafning markazi yagona uchdan iborat bo‘lmasligi mumkinmi?
   
9. 
   Grafning radial oddiy zanjiri qanday topiladi?
   
10. 
    Graf qirrasining (yoyining) uzunligi deganda nimani tushunasiz?
    
11. 
    Additivlik xossasini qanday tushunasiz?
    
12. 
    Grafdagi zanjirning (yo‘lning) uzunligi qanday aniqlanadi?
    
13. 
    Qanday masalaga minimal uzunlikka ega yo‘l haqidagi masala deb aytiladi?
    
14. 
    Agar grafda umumiy uzunligi manfiy bo‘lgan sikl bor bo‘lsa, u holda Deykstra algoritmini qo‘llab minimal uzunlikka ega yo‘lni topish mumkinmi?
    
15. 
    Deykstra algoritmining umumiy qadamida qanday ishlar amalga oshiriladi?
    

1^ Agar grafda umumiy uzunligi manfiy bo‘lgan sikl mavjud bo‘lsa, u holda grafning qandaydir uchidan shu siklning biror uchiga o‘tib, keyin esa, sikl bo‘ylab harakatlanib, uchga istalgancha marta qaytish mumkin bo‘lganligidan, istalgancha kichik uzunlikka ega yo‘l tuzish mumkin.

2 ^ Deykstra Edsger Vayb (Dijkstra Edsger Wybe, 1930-2002) – Gollandiya matematigi.

3 ^ Yozuvning ixchamligi nuqtai nazardan bu yerda va bundan keyin hosil bo‘lgan to‘plamlar uchun va belgilar qoldiriladi.