“Algoritmlarni loyihalash”

qo`shni qirralar deyiladi. Agar grafda boshi va oxiri bitta tugunda tutashadigan 
qirra mavjud bo'lsa, unga ilmoqli qirra deyiladi. 
4.-rasm. Qirra tushunchasi 
Agar grafda takroriy (karrali) qirralar mavjud bo`lsa, bunday grafga 
multigraf deyiladi. Agar grafda karrali qirralar bilan birga uchni o`z-o`zi bilan 
tutashtiruvchi ilmoqlar ham mavjud bo`lsa, bunday grafga psevdograf deyiladi 
(5.-rasm). 
5.-rasm. A) multigraf; B) psevdograf 
Ixtiyoriy tugundan boshqa bironta tugunga murojaat mavjud va murojaat 
ikki tomonlama bo’lsa, bu holda bunday graf yo’naltirilmagan graf (graph) 
deyiladi (6.-rasm. A).
Agar graf tugunlari o'zaro bog'langan bo'lsa, lekin bu yoylar orqali 
munosabat faqat bir tomonlama bo'lsa, u xolda bunday graflar yo'naltirilgan 
graflar (oriented graph) deyiladi (6.-rasm. B).
a 
b 
c 
d 
e 
f 
g 
1 uch 
2 uch 
qirra 
A) 
B) 

---

6.-rasm. A) yo’naltirilmagan graf; B) yo’naltirilgan graf 
Og’irlikka (vaznga) ega bo’lgan graf (weighted graph) – bu qirralari 
(yo’ylari) og’irliklari bilan berilgan graf hisoblandi. (i,j) qirraning og’irligi w
ij 
kabi belgilanadi (7.-rasm). 
 
7.-rasm. Og’irlikka ega bo’lgan graf 
Agar V to`plamning quvvati n ga teng bo`lsa, n soni grafning tartibi 
deyiladi. Agar V to`plamning quvvati n ga teng bo`lsa, E to`plamning quvvati m 
ga teng bo`lsa, graf (n, m) graf deyiladi.
Tugun darajasi (vertex degree) – bu undan chiquvchi yoylar soni 
xisoblanadi. deg(7) = 2, deg(1) = 3 
Halqa (cycle) – bu boshi va oxiri tutashuvchi tugundan iborat yo'l 
hisoblanadi: (4, 6, 7, 8, 3, 4) (1.2.8.-rasm). 
G(V, E) grafda uning barcha tugunlari darajalari yig'indisi – juft, 
grafning qirralari sonining ikkilanganiga teng.

=
=
n
i
i
m
V
1
2
)
deg(
Tugunlar darajasiga nisbatan juft yoki toq deyiladi, agar ularning 
darajalari mos ravishda juft yoki toq qiymatga teng bo'lsa. 
4 
3 
1 
2 
4 
3 
1 
2 
A) 
B) 

---

8.-rasm. Grafning halqa va tugun darajasiga misol 
To'liq graf (complete graph) – bu istalgan tugunlari qo'shni bo'lgan graf 
xisoblanadi yani barcha tugunlar o'zaro birlashtirilgan. (9. a -rasm) 
Grafni to'ldiruvchisi bu aynan bir tugunlar va aynan bir qirralardan tashkil 
topgan va mavjud grafni to'liq bo'lishini ta'minlovchi grafga aytiladi. (9. b -
rasm) 
a) 
b) 
9.-rasm.a) to’liq graf b) graf va uning to’ldiruvchisi 
To'liq, yo'naltirilmagan grafda qirralar soni quyidagi formula (1) orqali 
aniqlanadi: 
A
B
C
D
A
B
C
D
A
B
C
D

---

(1) 
qaerda n – yoylar(tugunlar) soni. 
D grafning to'yinganligi (density) grafning qirralrining tugunlar nisbatiga 
to’liqlik munosabat koefitsientini belgilaydi va quyidagi formula (2) orqali 
aniqlanadi: 
(2) 
qaerda n – grafning tugunlar soni, m – grafning qirralar soni.
Grafning to'yinganligi koefitsientiga qarab ikki hil graf ko’rinishi aniqlash 
mumkin: to'yingan graf va siyrak graf (10.-rasm).