2-kurs tt 14-21- guruh (sirtqi) talabasi Temirov Qodirning Ma’lumotlar tuzilmasi va algoritmlari fanidan 5-mustaqil ishi

Qo'shnilik(qo'shni tugunlar) ro'yxati – bu A[n] massiv bo'lib, A[i] xar bir elementi i tugun bilan qo'shni tugunlar ro'yxatini o'zida saqlaydi.
Qo'shnilik(qo'shni tugunlar) ro'yxati qulaylik tomonlari quyidagilarda:
Joriy (berilgan) tugunga qo’shni tugunni izlash;
Tugun yoki qirra(yoy)larni qushish;
Siyrak graflar bilan ishlash.
Qo'shnilik(qo'shni tugunlar) ro'yxati noqulayliklari esa quyidagicha:
Qirra(yoy)ning mavjudligini tekshirish;
Tugun yoki qirra(yoy)larni o’chirish.
Qirralar ro'yxati – qirralarning qo'shni tugunlar juftliklaridan iborat chiziqli ro'yxatdir.

Graflarda ko'rik o'tkazish

Grafni ko'rikdan o'tkazish (Graph traversal) – bu berilgan tugundan boshlab barcha tugunlarni bir martadan ko'rib chiqish amalidir.
Ko’rikdan o’tkazish ikkita usuli mavjud:
Chuqurligiga (tubiga) qarab qidirish (Depth-First Search – DFS)
Kengligiga (eniga) qarab qidirish (Breadth-First Search – BFS)
Bu usullar berilgan X tugundan boshlab bironta konteynerni qo'llagan holda barcha tugunlarni ko'rib chiqadi.
Chuqurlikka qarab ko'rishda stek tuzilmasi qo'llaniladi.
Kenglikka qarab ko'rishda esa navbat tuzilmasidan foydalaniladi.
Tubiga qarab ko’rikni o’tqazish psevdokodi quyidagicha amalga oshiriladi




A tugundan boshlab tubiga qarab ko’rib chiqish misoli

graflar berilganV2 ,U2   va G2 V1,U1 Graflarni birlashtirish. G1
U2 kabiU1 V2 va qirralari korteji U V1 bo’lsin. Uchlari to’plami V
graf G1 va G2 graflarning birlashmasi deb ataladi vaU ,V  aniqlangan G
G2 ko’rinishda belgilanadi. 2.5–rasmda uchlari to’plami kesishmaydigan G1 G
K2 va K3 graflarning birlashmasi amali tasvirlangan.
graflar berilgan V2 ,U2   va G2 V1,U1 
Graflarni ko’paytirish.
G1 grafning qirralariV ,U  V2 bo’lgan G V1 bo’lsin. Uchlari to’plami V
kortejini quyidagicha aniqlaymiz: agar v
 v2 va (v1 2 v U2 yoki v v2 )2 2 va1 v (vU11)bo’lsa,uholda
U,vvbo’ladi,bu yerda V1,1V v2 ,v 22 ,Vv1,v2  v
1,vv va v V . Shunday usul2 graf G1 va G2 graflarning ko’paytmasi deb ataladi vaV ,U  bilan qurilgan G G2 kabi belgilanadi. G1 G

Agar ixtiyoriy G grafda a uch b uch bilan, b uch esa c uch bilan

bog’langan bo’lsa, u holda ko’rinib turibdiki, a uch c uch bilan bog’langan
bo’ladi. grafningV ,U  G uchlar to’plami Vi (3.4) yig’indi mavjud. Bunda har bir Vikesishmaydigan quyidagicha V I qism to’plamdagi uchlar o’zaro bog’langan, turli Vi qism to’plamdagi uchlar Vi o’zaro bog’lanmagan bo’ladi. Mos ravishda (3.4) yig’indidan G grafning G (3.5) to’g’ri yig’indisiVi Gqism graflari kesishmaydigan quyidagicha G tuziladi. Bu qism graflar grafning bog’lamlilik komponentalari deyiladi. Yuqorida keltirilgan tasdiqlardan quyidagicha teoremani isbotsiz keltiramiz.
Teorema 3.2. Har bir yo’naltirilmagan graf o’zining bog’lamlilik
komponentalarining (3.5) to’g’ri yig’indisiga ajraladi va bu ajralish yagona
bo’ladi.
Teorema 3.3.
Agar chekli G grafda darajaga ega bo’lsa, u holoda ular bog’langan bo’ladi.
Masofa. G yo’naltirilmagan bog’lamli graf bo’lsin. Ixtiyoriy a va b
bo’lgana,b uchlari bog’langan bo’lsa, u holda oxirlari a va b bo’lgan S
oddiy zanjir mavjud bo’ladi. Ushbu oddiy zanjirlarning uzunliklari manfiy
bo’lmagan butun sonlardan iborat bo’ladi. Mos ravishda a va b uchlar orasida
eng qisqa uzunlikka ega zanjir majud bo’ladi. Ushbu eng qisqa uzunlik a va b
kabi belgilanadi. Ta’rif bo’yicha bu masofalara,borasidagi masofa deyiladi va d
0 tenglik bajariladi. Oson ko’rish mumkinki, bu aniqlangana, auchun d
masofa funktsiyasi metrika aksirmalarini qanoatlantiradi: 0a, a1 d

Xulosa
Graflar nazariyasi bo’yicha tadqiqotlar natijalari inson faoliyatining turli

sohalarida qo’llaniladi. Ulardan ba’zilari quyidagilar: boshqotirmalarni hal
qilish; qiziqarli o’yinlar; yo’llar, elektr zanjirlari, integral sxemalari va
boshqarish sistemalarini loyihalashtirishva hakazo.


Foydalanilgan adabiyotlar:
Mengliyev.Sh- ,,Ma’lumotlar tuzilmasi va algoritmlari haqida tushunchalar” Toshkent 2015.
Ziyonet.uz portal:
Terabayt.uz portal: