13-amaliy mashg’ulot. Graflarni analitik usulda berilishiga ko’ra chizish. Oddiy graf. Multigraf, psevdograf. Graf uchlarining darajalari va kirralari sonini topish. Graflar ustida amallar. Graflarning qo’shnilik va insidentlik matrisalari

₁₃-AMALIY MASHG’ULOT. Graflarni analitik usulda berilishiga ko’ra chizish. Oddiy graf. Multigraf, psevdograf. Graf uchlarining darajalari va kirralari sonini topish. Graflar ustida amallar. Graflarning qo’shnilik va insidentlik matrisalari. Qo’shnilik va insidentlik matrisalariga kura grafni yasash


Reja:

1. 
   Graflar nazariyasiga oid asosiy tushunchalar.
   
2. 
   Mustaqil bajarish uchun masala va topshiriqlar
   
   1. 
      Graflar ustida amallar
      

1. 
   Graflar nazariyasiga oid asosiy tushunchalar
   

Graflar nazariyasi fani – chiziqlar va nuqtalardan tuzilgan bazi bir geometrik konfiguratsiyalar to‘g‘risidagi masalalarni Echishda ishlatiladi. Bunday masalalarni yechishda, geometrik konfiguratsiyalarda nuqtalar bir –biri bilan to‘g‘ri chiziq yoki yoy bilan birlashtirilganmi, bularning uzunligi qancha kabi faktorlar e’tiborga olinmaydi. Eng muximi shundaki, har bir chiziq qandaydir berilgan ikkita nuqtani birlashtirayapti. Shunday qilib, grafning ta’rifini quyidagicha berishi mumkin.
13.1-Ta’rif. To‘plam V={a₁,a₂,…,a_n} va V to‘plamdan olingan juftliklar E={(a_i1, a_j1),…,(a_ik, a_jk)} naboriga Graf deyiladi.
V to‘plamdagi a₁,…,a_n lar qandaydir ob’ektlar bo‘lib G grafning uchlari deyiladi. E to‘plamdagi har bir (a_i1, a_j1),…,(a_ik, a_jk) juftlik Grafning qirralari deyiladi.
Agar (a_i, a_j) qirra berilgan bo‘lsa, u holda a_i, va a_j uchlar birlashtirilgan deyiladi.
13.1-Misol. Agar V={a₁, a₂, a₃, a₄, a₅, a₆, a₇,}va E={(a₁,a₂)(a₂,a₂)(a₂,a₃)(a₃,a₄)(a₄,a₅)(a₅,a₆)(a₆,a₅)} bo‘lsin, u holda V va E to‘plam G grafni hosil qiladi.
13.2-Ta’rif. Grafning uchlarini tugunlar, 2 ta uchini birlashtiruvchi chiziqni qirralar deb ataymiz.