“Algoritmlarni loyihalash”

---

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNALOGIYALARI VA 
KOMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI 
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT 
TEXNALOGIYALARI UNIVERSITETI 
030-20 guruh talabasi 
Miryunusov Miryusufning 
“Algoritmlarni loyihalash”
 
fanidan bajargan 
Mustaqil ishi 
 
 
 
 

---

 
Graflarni eniga va bo’yiga aylanishi. 
Graflarni tasvirlash usullari.
 
 
 
 
 
 

REJA :
 
 
1. Graflar nazariyasining asosiy tushunchalar 
2. Graflarni eniga va boyiga aylanishi 
3. Graflarda ko'rik o'tkazish 

---

1. Graflar nazariyasining asosiy tushunchasi 
Matematik nazariyada va informatikada graf — bu tugunlar(uchlar)dan 
iborat bo'lgan bo'sh bo'lmagan to'plam va tugunlarni birlashtiruvchi yoylar 
majmuidir. 
Graf - bu murakkab chiziqsiz ko'pbog'lamli dinamik tuzilma bo'lib, 
murakkab ob'ektlarning xususiyatlari va munosabatlarini aks ettiradi. 
Ob'ektlar tugun yoki graf uzellari ko'rinishida va munosabatlar yoy yoki 
yo'naltirilgan qirralar kabi ifodalanadi. 
«Graf» tushunchasini birinchi marotaba 1936 yil vengriya matematigi 
Denni Kyonig kiritgan. Lekin graflar nazariyasi bo'yicha 1-ish Leonard Eylerga 
tegishli bo'lgan va u 1736 yilda bajarilgan edi. 
XVIII asrda mashhur shvetsariyalik matematik, mexanik va fizik Leonard 
Eyler (1707-1783 yy) Kyonigsberg ko’prigi haqidagi masalani yechish uchun 
birinchi marta graf tushunchasidan foydalanadi.
1.-rasm. Eski Kyonigsberg shahri sxemasi 
Graflar nazariyasi diskret matematika fanining bir bo’limi bo’lib, unda 
masalalar yechimlari chizmalar shaklida izlanadi. Keyingi paytlarda turli xil 
diskret xususiyatlarga ega bo‘lgan xisoblash qurilmalarini loyihalashda 
graflarning ahamiyati yanada oshdi. 
(V, E) sonlar juftligiga graf deyiladi, bu yerda V – ixtiyoriy bo`sh 
bo`lmagan to`plam, E esa 
ning qism to`plami 
, bunda 
V 
to`plam elementlarining tartiblanmagan juftliklari to`plami.
V – to`plam elementlari grafning uchlari deyiladi.
E  – to`plam elementlari esa grafning qirralari deyiladi.
Agar V chekli bo`lsa, graf chekli deyiladi, aks holda cheksiz graf 
deyiladi. 
Yo'l (path) – bu bironta tugundan boshqa bir tugungacha bo'lgan yonma-
yon joylashgan tugunlar ketma-ketligidir.

---

2.-rasm. Grafning asosiy alomatlari 
Grafning uchlari va qirralari to`plamini mos ravishda
va 
kabi 
belgilanadi. 
ushbu to’plamda uchlar berilgan bo’ladi. 
to’plamida esa 
qirallarning qushni uchlar juftligi bilan aniqlanadi.
Masalan:
)}.
,
(
),
,
(
),
,
(
),
,
(
),
,
(
),
,
(
),
,
(
),
,
(
),
,
{(
)
(
}
,
,
,
,
,
,
{
)
(
f
d
e
c
e
b
g
b
c
b
f
a
d
a
c
a
b
a
G
E
g
f
e
d
c
b
a
G
V
=
=
Bu holda grafning grafik ko’rinishi quyidagicha bo’ladi (3.-rasm):
B 

---

3.-rasm. Grafga misol 
Qirra ikkita uch bilan aniqlanadi. Umumiy uchga ega bo`lgan ikkita qirra 
qo`shni hisoblanadi. Agar grafning ikkita uchi qirra bilan tutashtirilgan bo`lsa, 
bu uchlar qo`shni uchlar deyiladi. Grafning bir uchdan chiqqan ikki qirrasi