Algoritmlarni layihalash




Download 268,36 Kb.
Pdf ko'rish
bet5/6
Sana24.05.2024
Hajmi268,36 Kb.
#252335
1   2   3   4   5   6
Bog'liq
5.1-mustaqil ishi

To'yingan grafik
(zich grafik) - bu qirralarning soni maksimal mumkin 
bo'lgan 
raqamga 
teng 
bo'lgan 
grafik 
hisoblanadi. (D>0,5) 
siyrak grafik
(siyrak grafik) - chekkalari tugunlarning oxiriga yaqin joylashgan 
grafik. (D<0,5)
a) to`yingan grafik (D=0,9)
b) siyrak grafik (D=0,33) 
Quyida turli ko`rinishdagi grafiklar keltirilgan. nom oddiy grafik , c-to‘liq 
grafik, e-multigraf, f-psevdograf, g-digrafda zanjir , h-digrafda ommaviy. 
Statik struktura matritsasi yoki dinamik tuzilma ro'yxatlari kompyuter 
dasturlash tillari xotirasida yo'naltirilmagan, yo'naltirilgan va yo'naltirilgan 
grafiklarni tasvirlash , ya'ni ularni xotirada tartibga solish uchun ishlatilishi 
mumkin. Har bir usul har qanday masalada o'zining afzalliklari va kamchiliklariga 
ega. Har bir usul yo'naltirilmagan, yo'naltirilgan va yo'naltirilgan grafiklarni ifodalash 
uchun o'z qoidalariga asoslanib tuzilgan.
Grafikning 
qo‘shma 
matritsasi G bu o‘lchamdagi kvadrat A matritsasi bo‘lib, 
grafik uchun: 


Aij = 1, agar i va j tugunlari chekka bilan bog‘langan bo‘lsa, 
orfograf uchun
i va j tugunlari orasida chekka bo‘lmasa, Aij = 0 bo‘ladi : Aij = 1, agar i tugundan j 
tugungacha yoy bo'lsa Aij = 0, agar 
vaznli grafik uchun
i va j tugunlarida yoy 
tugallanmagan bo'lsa : Aij = Wij, agar i va j tugunlari chekka (yoy) lsa bilan 
bog'langan bo'lsa. Aij = ∞ Agar i va j tugunlari chekka (yoy) sifatida mavjud 
bo'lmasa , Qo'shma matritsa asosiy diagonalga nisbatan nosimmetrik bo'ladi, agar u 
yo'naltirilmagan grafikni ifodalasa va u orfograflarda assimetrik bo'ladi. Qo'shma 
matritsaning afzalliklari quyidagilardan iborat: 
Oson yoqish va o'chirish; 
Tugunlarning qo'shniligini tekshirish. 
Qo'shma matritsaning kamchiliklari quyidagilardan iborat: 

Download 268,36 Kb.
1   2   3   4   5   6




Download 268,36 Kb.
Pdf ko'rish