Laboratoriya ishi 25 Mavzu: np-to’liq masalalar. Ishdan maqsad

Amliy qism
Grafik - bu quyidagi ikki komponentdan iborat ma'lumotlar tuzilishi.
1. Tugunlar deb ham ataladigan cheklangan tepaliklar to'plami.
2. Shaklning tartiblangan juftligining cheklangan to'plami (u, v) chekka deb nomlanadi. Juftlik buyurtma qilingan, chunki (u, v) yo'naltirilgan grafik (di-grafik) holatida (v, u) bilan bir xil emas. Shaklning juftligi (u, v) u vertikaldan v tepaga qadar bir chekka borligini bildiradi, qirralarning vazni / qiymati / narxi bo'lishi mumkin.
Grafikalar hayotdagi ko'plab dasturlarni namoyish qilish uchun ishlatiladi: Grafikalar tarmoqlarni aks ettirish uchun ishlatiladi. Tarmoqlar shahar yoki telefon tarmog'idagi yoki elektron tarmoqdagi yo'llarni o'z ichiga olishi mumkin. Graflar, shuningdek, LinkIn, Facebook kabi ijtimoiy tarmoqlarda qo'llaniladi. Masalan, Facebook-da har bir odam vertex (yoki tugun) bilan ifodalanadi. Har bir tugun tuzilishga ega va shaxs identifikatori, ismi, jinsi va joyi kabi ma'lumotlarni o'z ichiga oladi. Grafikning ko'proq ilovalari uchun buni ko'ring.
Quyida 5 ta tepalikka ega bo'lgan yo'naltirilmagan grafikaga misol keltirilgan.

Quyidagi ikkitasi grafikaning eng ko'p ishlatiladigan tasvirlari.
1. Yaqinlik matritsasi
2. Yaqinlik ro'yxati
Shuningdek, boshqa hodisalar ham mavjud, "Intsident Matrix" va "Incident List". Grafik tasvirini tanlash vaziyatga xosdir. Bu butunlay bajariladigan operatsiyalar turiga va ulardan foydalanish qulayligiga bog'liq.
Yaqinlik ro'yxati:
Bir qator ro'yxatlar ishlatiladi. Massivning kattaligi tepalar soniga teng. Massiv bir qator bo'lsin []. Kirish massivi [i] ith vertexga qo'shni bo'lgan tepalar ro'yxatini aks ettiradi. Ushbu tasvir vaznli grafikani ko'rsatish uchun ham ishlatilishi mumkin. Qirralarning og'irliklari juftliklar ro'yxati sifatida ifodalanishi mumkin. Yuqorida keltirilgan grafikning qo'shni ro'yxati ko'rsatilgan.



Topshiriqlar.

1. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

2. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

3. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

4. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

5. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

6. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

7. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

8. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

9. 
   Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.
   

10. 
    Graflarning ro’yxat tuzilmasidan foydalanib yuqoridagi chizmani dasturiy kodi tuzilsin va ekranga chiqarilsin.