Guruh Talabasi Qo`chqorov Azizbekning Diskret tuzilmalardan bajargan 1- mustaqil ish

---

 
 
 
 
 
 
O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA 
KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI 
 
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT 
TEXNOLOGIYALARI UNIVERSITETI 
 
TT-FAKULTETI 
MTH019
-guruh Talabasi Qo`chqorov Azizbekning 
Diskret tuzilmalardan 
bajargan 1-
mustaqil ish
. 
 
 
 
 
 
 
 
 

Bajardi: Qo`chqorov Azizbek 

 

Tekshirdi:
Aliqulov Yolqin
 

---

N%28 
Mavzu;
Graflar izomorfligi, misollar bilan. 
Asosiy tushunchalar. Graflar ustida amallar. Graflarning izomorfligi. 
Reia: 
Oddiy graflar Ta'rif va misollar 
Grafning uchlari va girralari. 
Insidentlik tushunchasi.Qism graf. 
To'Idiruvchi graf. Graflarning izomorfligi. 
1). Graf deb shunday  juftlikka aytiladiki, bu yerda Ko0 va U-
 (v,e V, ve V) ko'rinishdagi juftliklar korte]i'bo'lib, Vx V toplamning 
elementlaridan tuzilgandir. 
Bundan buyon grafni belgilashda yozuv o'riga (V, U) yozuvdan 
foydalanamiz.Grafning tashkil etuvchilar ini korsatish muhim bo'lm asa, 
u holda uni lotin alifbosining bitta harfi bilan belgilaymiz. 
Д'=(V, U) graf berilgan bolsin. Vtoplamning elementlariga G grafning 
uchlari, V to plamning oziga esa, graf uchlari to'plami deyiladi. 
Graflar nazariyasida «uch» iborasi o'miga, bazan, tugun yoki nuqta 
iborasi ham go'llaniladi. Umum an olganda, hanuzgacha graflar 
nazariyasining ba'zi iboralari bo'yicha umumiy kelishuv garor 
topmagan.Shuning uchun, bundan keyingi tariflarda, imkoniyat boricha, 
muqobil (alternativ) iboralarni ham keltirishga harakat qilaml2 XIV_ U7 
G=(V, U) grafning ta'rifiga ko'ra, U bo'sh korte] bo'lishi ham mumkin. 
Agar U bo'sh bo'lmasa, u holda bu korte (a,b) (ae V, be I° kotinishdagi 
juftliklardan? tashkil topadi, bunda 
a =b bolishi harnda ixtivoriy (a b) juftlik U kortejda I stal gancha marta 
catrashishi mumkin. (a ,b)t Cijuftlikni tashkil etuvchi a va b uchlaming 

---

joyla shish tartibidan bog liq hol da, ya 'hi yo'halishning borligi yoki 
yo'°qli giga garab, uni turicha atash mumkin. Agar (a,b) juftlik uchun uni 
Graflar nazariyasi xozirgi zamon matematika- sining asosiy qismlaridan 
biridir. Keyingi paytlarda turli xil ABT va diskret xususiyat- larga ega 
bo'lgan xisoblash qurilmalarini loyixalashda (yasashda) graflarning 
axamiyati vanada oshdi. Grafni ta'riflashdan avval uni misolda 
tushuntiramiz
. 
1, 2, 3, 4, 5 - grafning uchlari; a, b, c, d, e, f, g, h, i, j-grafning qirralari: a, 
b, e, f, g qirralilar yo' naltirilgan.b, c, d, k girralar sirtmoqlar deb ataladi. 
a, b, e, f, g qirralarni 1 uchga insident deb ataydilar, o' navatida bu uch 
shu qirralarning xar biriga insidentdir. 3 va 5 uchlar yakkalangan, 
deyiladi, ular ko'pi bilan sirtmoqlarga ega bo 'lishi mumkin. Kelgusida 
oddiy graflar muxim o' rin tutadi. 
Bu sinning graflari quyidagi xossalarga ega u chekli (girralari va uchlari 
soni chekli), barcha girralari yo' naltirilmagan, sirtmoqlari va karrali 
qirrali yo'q. Bunday graflarga quidagilar misol bola oladi: 

---

Ta'rif. Bo'sh bo 'Imagan X uchlar to guiami va qirralar to' plamidan 
tuzilgan tartiblangan 
G=(X, U) juftlik oddiy graf deb ataladi. 
• Petersen nomi bilan atalgan graf.
Bu sinfning graflari quyidagi xossalarga ega u chekli (qirralari va uchlari 
soni chekli), barcha qirralari yo‘naltirilmagan, sirtmoqlari va karrali 
qirrali yo‘q. Bunday graflarga quyidagilar misol bo‘la oladi: 
Agar uchlar uchun bo'lsa, uchlar qo'shni, bo'lsa, bu uchlar go' shnimas 
deyiladi. Oddiy graflarning ikki xolini 
ko' ramiz: 
E,-n uchli bo'sh graf, U(En) =0 
Fm-n uchli to'liq graf, U(Fn) = XI21 
SHaklda E5 va F5 graflar keltirilgan 

---

Ta'rif. Uchlari G-(X,U) grafning uchlaridan, qirralari esa UcX° IU to 
plamdan iborat bo'lgan graf © = (X,¿ ) berilgan grafning to ' diruvchisi 
degiladi. & = G xossa o'rinli bo 'lishi ravshan. YUqoridagi rasmdagi E, va 
F, graflar bir birini to 'Idiruvchidir. Ularga yana misol keltiramiz
: 
Ta' rif. Agar G=(X,U) va G=(X],U) graflar uchun bo'lsa, u xolda Gl graf G 
grafning bo ' lagi deyiladi. Mas alan 5 shakldagi graflar 4 shakldagi 
birinchi grafning bo' lagidir 
birinchi grafning bo' lagidir. 
'Ta' rif. Agar G=(X,U) grafning bo'lagi G=(X,U) uchun bo'lsa, u xolda u 
sugraf deb ataladi. 
Sugraflarni xosil qilish uchun faqat girralarni murojat qilamiz. Quyidagi 
graflar uning sugraflaridira.