Texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al xozazmiy nomidagi toshkent axborot

2C
m
2 
 = m(m-1) 
bo‘ladi.Agar grafning uchlariga qandaydir belgilar, masalan, 1,2,...,m 
sonlari mos qo‘yilgan bo‘lsa, u belgilangan graf deb ataladi. 

---

 Agar G 

(V,U) va G' 

(V' ,U') graflarning uchlari to‘plamlari, ya’ni V va 
V ' to‘plamlar orasida uchlarning qo‘shnilik munosabatini saqlaydigan 
o‘zaro bir qiymatli moslik o‘rnatish mumkin bo‘lsa, u holda G va G' graflar 
izomorf graflar deb ataladi. Bu ta’rifni quyidagicha ham ifodalash mumkin: 
agar 

x,y

V va ularga mos bo‘lgan x' , y'

V' ( x 

y , x'

y' ) uchun xy 

x' y' ( xy

U , x' y'

U ' ) bo‘lsa, u holda G va G' graflar izomorfdir. 
Agar izomorf graflardan biri oriyentirlangan bo‘lsa, u holda ikkinchisi 
ham, albatta, oriyentirlangan bo‘lishi va ulardagi mos yoylarning 
yo‘nalishlari ham bir-birlariga mos bo‘lishlari shart.
Graf uchiga insident qirralar soni shu uchning lokal darajasi, yoki, 
qisqacha, darajasi, yoki valentligi deb ataladi. Grafdagi a uchning 
darajasini 

(a) bilan belgilaymiz.
Sirtmoqqa insident bo‘lgan uchning darajasini aniqlashda shuni e’tiborga 
olish kerakki, qaralayotgan masalaga bog‘liq holda sirtmoqni bitta qirra 
deb ham, ikkita qirra deb ham hisoblash mumkin. Ravshanki, ajralgan 
uchning darajasi nolga teng. Darajasi birga teng uch chetki (yoki osilgan) 
uch deb ataladi. Chetki (osilgan) uchga insident qirra ham chetki (yoki 
osilgan) qirra deb ataladi. 
Agar grafning barcha uchlari bir xil r darajaga ega bo‘lsa, u holda bunday 
graf r darajali regulyar graf deb ataladi. Uch darajali regulyar graf kubik 
(yoki uch valentli) graf deb ataladi. O
m
graf nol darajali regulyar graf 
ekanligini, K m esa ( m

1 ) darajali regulyar graf ekanligini ta’kidlaymiz.
Ko‘rinib turibdiki, oriyentirlanmagan grafda barcha uchlar darajalarining 
yig‘indisi qirralar sonining ikki baravariga teng juft son bo‘ladi, chunki 
qirralarni sanaganda har bir qirra hisobda ikki marta qatnashadi. Shunday 
qilib, XVIII asrdayoq L. Eyler tomonidan isbotlangan quyidagi tasdiq 
o‘rinlidir. 
1 - l e m m a (“ko‘rishishlar” haqida).Ixtiyoriyoriyentirlanmagan grafda 
barcha uchlar darajalari yig‘indisi qirralar sonining ikki baravariga teng. 
Agar grafning uchlar to‘plamini o‘zaro kesishmaydigan shunday ikkita 
qism to‘plamlarga (bo‘laklarga) ajratish mumkin bo‘lsaki, grafning 
ixtiyoriy qirrasi bu to‘plamlarning biridan olingan qandaydir uchni ikkinchi 

---

to‘plamdan olingan biror uch bilan tutashtiradigan bo‘lsa, u holda bunday 
graf ikki bo‘lakli graf (bixromatik yoki Kyonig grafi) deb ataladi. Ta’rifdan 
ko‘rinib turibdiki, ikki bo‘lakli grafning har bir bo‘lagidagi ixtiyoriy ikkita 
uchlar qo‘shni bo‘la olmaydi. Biror bo‘lagida faqat bitta uch bo‘lgan to‘la 
ikki bo‘lakli graf yulduz deb ataladi. 
Agar ikki bo‘lakli grafning turli bo‘laklariga tegishli istalgan ikkita uchi 
qo‘shni bo‘lsa, u holda bu graf to‘la ikki bo‘lakli graf deb ataladi. To‘la 
ikki bo‘lakli grafni Km,n bilan belgilaymiz, bu yerda m va n bilan grafning 
bo‘laklaridagi uchlar sonlari belgilangan. ( , ) Km,n 

V U graf uchun |V |

m 

n va |U |

mn bo‘lishi ravshan, bu yerda |V | – Km,n grafning uchlari 
soni, |U | – uning qirralari soni.
Grafning ikki bo‘lakli graf bo‘lishi haqidagi ba’zi qo‘shimcha ma’lumotlar 
(Kyonig teoremasi) ushbu bobning 4- paragrafida keltirilgan. Ikkidan katta 
ixtiyoriy natural k son uchun k bo‘lakli graf tushunchasini ham kiritish 
mumkin.
m i s o l . O‘zbekiston Respublikasi hududidagi aeroportlar to‘plamini V 
bilan, bu shaharlar orasida belgilangan vaqt mobaynida amalga 
oshirilayotgan samolyotlarning uchib qo‘nish hodisalari kortejini U bilan 
belgilaymiz. U holda (V,U) juftlikni graf deb qarash mumkin. Bu yerda 
grafning uchlariga aeroportlar, yoylariga esa samolyotlarning uchib qo‘nish 
hodisalari mos keladi. Tabiiyki, (V,U) grafda karrali yoylar bo‘lishi 
mumkin, agar, qandaydir sababga ko‘ra, samolyot uchgan aeroportga 
qaytib qo‘nsa, u holda bu hodisaga qaralayotgan grafdagi sirtmoq mos 
keladi. 
Graflar ustida amallar graflarni qo`shish. 
Graflar ustida sodda amallar. Graflar ustida turli amallar bajarish mumkin, 
masalan, graflarni birlashtirish, biriktirish, ko‘paytirish,grafni qismlarga 
ajratish va hokazo.
Eng sodda amallardan biri sifatida grafdan uchni olib tashlash amalini 
keltirsa bo‘ladi. Bu amalni qo‘llash berilgan grafning uchlari to‘plamidan 

---

birorta element yo‘qotishni (olib tashlashni) anglatadi. Natijada uchlari 
soni bittaga kamaygan yangi graf hosil bo‘ladi. Albatta, bu amalni uchlari 
soni ikkitadan kam bo‘lmagan graflar uchun qo‘llash mumkin bo‘lib, uni 
bajarish jarayonida olib tashlanayotgan uch bilan birgalikda shu uchga 
insident bo‘lgan barcha qirralar (yoylar) ham olib tashlanadi. 
Eng sodda amallar qatoriga grafdan qirrani (yoyni) olib tashlash amalini 
ham kiritish mumkin. Bu amalga ko‘ra berilgan grafning qirralari (yoylari) 
to‘plamidan birorta element yo‘qotiladi (olib tashlanadi). Berilgan grafdan 
qirrani (yoyni) olib tashlayotganda shu qirraga (yoyga) insident uchlarni 
grafda qoldirish ham yo‘qotish ham mumkin. Bu yerda vaziyatga qarab ish 
yuritiladi. G 

(V,U) va G' 

(V' ,U') graflar berilgan bo‘lsin. Agar V 

V' 
va G grafning barcha qirralari (yoylari) G' grafning ham qirralari (yoylari), 
ya’ni U 

U' bo‘lsa, u holda G graf G' grafning qism grafi deb ataladi. 
m i s o l . 1- shaklda Petersen grafining (ushbu bobning 2- paragrafidagi 8- 
shaklga qarang) qism graflaridan biri 
tasvirlangan. 1- shakl Agar G graf karrali 
qirralarga ega bo‘lmasa, u holda uchlari G 
grafning barcha uchlaridan iborat bo‘lgan 
shunday yagona G graf mavjudki, G grafdagi 
barcha juft uchlar faqat va faqat G grafda 
qo‘shni bo‘lmagandagina qo‘shnidir. Bunday G 
graf berilgan G grafning to‘ldiruvchi grafi deb ataladi. 
Berilgan graf uchun to‘ldiruvchi grafni qurish jarayonini ham graflar ustida 
bajariladigan amallar qatoriga kiritish mumkin. G graf uchun to‘ldiruvchi 
grafni qurish amalini qo‘llash natijasida G graf hosil bo‘ladi. Isbotlash 
mumkinki, G 

G munosabat o‘rinlidir. 
m i s o 
l . 2- shaklda tasvirlangan graf 1- shaklda 
ifodalangan graf uchun to‘ldiruvchi grafdir. 
Graflar ustida shunday amallarni bajarish 
mumkinki, ular elementlari soni berilgan 
grafdagidan ko‘proq bo‘lgan boshqa 
graflarning hosil bo‘lishiga olib keladi. 
Bunday amallar qatoriga uchni qo‘shish 

---

amali yoki qirrani (yoyni) qo‘shish amalini kiritish mumkin. Grafga yangi 
uchni qo‘shish turlicha usul bilan amalga oshirilishi mumkin. Masalan, 
yangi v uchni berilgan grafga qo‘shish shu grafning v1 va v2 uchlariga 
insident bo‘lgan qandaydir u qirrasiga qo‘shish orqali quyidagicha ikki 
bosqichda bajarilishi mumkin: 1) u qirra berilgan grafdan olib tashlanadi; 
2) hosil bo‘lgan grafga ikkita yangi qirralar: v va v1 uchlarga insident u1 
qirra hamda v va v2 uchlarga insident u2 qirra qo‘shiladi.
Bu jarayon grafda qirraga darajasi 2 bo‘lgan yangi uchni qo‘shish (kiritish) 
yoki qirrani ikkiga bo‘lishamali deb ataladi.
Agar G graf G' grafdan qirrani ikkiga bo‘lish amalini chekli marta ketma-
ket qo‘llash vositasida hosil qilingan bo‘lsa, u holda G graf G' grafning 
bo‘linish grafi deb ataladi. 
Bo‘linish graflari izomorf bo‘lgan graflar gomeomorf graflar deb ataladi. 
shaklda tasvirlangan graflar izomorf emas, lekin ular gomeomorf, chunki 
bu graflarning har 
biri 4- shaklda tasvirlangan bo‘linish grafiga ega. 3.2. Graflarni 
birlashtirish. ( , ) G1 

V1 U1 va ( , ) G2 

V2 U2 graflar berilgan bo‘lsin. 
Uchlari to‘plami V 

V1 

V2 va qirralari (yoylari) korteji U 

U1 

U2 kabi 
aniqlangan2 G 

(V,U) graf G1 va G2 graflarning birlashmasi (uyushmasi) 
deb ataladi va G 

G1 

G2 ko‘rinishda belgilanadi.
5-misol shaklda uchlari to‘plamlari kesishmaydigan K2 va K3 graflarning 
birlashmasi amali tasvirlangan 
m i s o l . Uchlari to‘plamlari 
kesishadigan graflarning birlashmasi 
amali 6- shaklda tasvirlangan. Agar 
birlashtirilayotgan graflarning uchlari 

---

to‘plamlari kesishmasa, u holda bu graflarning birlashmasi diz’yunkt 
birlashma deb ataladi.
Masalan, 5- shaklda tasvirlangan 
birlashma diz’yunkt, 6- shakldagi birlashma esa – diz’yunkt emas. 
3.3. Graflarni biriktirish. ( , ) G1 

V1 U1 va ( , ) G2 

V2 U2 graflar 
berilgan bo‘lsin. G1 va G2 graflar birlashtirilishi hamda G1 grafning har 
bir uchi G2 grafning har bir uchi bilan qirra vositasida tutashtirilishi 
natijasida hosil bo‘lgan G 

(V,U) graf G1 va G2 graflarning birikmasi 
(tutashmasi) deb ataladi va G 

G1 

G2 ko‘rinishda belgilanadi. 
5- m i s o l . Uchta uy va uchta quduq haqidagi boshqotirma masalaga mos 
graf (ushbu bobning 2- paragrafidagi 9- shaklga qarang) uchlari to‘plamlari 
kesishmaydigan ikkita ( O3 ) nolgraflarning birikmasidir.
6- m i s o l . 7- shaklda uchlari to‘plamlari kesishmaydigan K2 va K3 
graflarning birikmasi amali tasvirlangan.
Agar uchlari to‘plamlari kesishmasi bo‘sh bo‘lmagan graflarni biriktirish 
zarur bo‘lsa, u holda hal qilinayotgan masala xossalarini e’tiborga olib ish 
ko‘rish kerakligini ta’kidlaymiz.
3.4. Graflarni ko‘paytirish. ( , ) G1 

V1 U1 va ( , ) G2 

V2 U2 graflar 
berilgan bo‘lsin. Uchlari to‘plami V 

V1 

V2 bo‘lgan G 

(V,U) grafning 
qirralari (yoylari) kortejini quyidagicha aniqlaymiz: agar ' '' 1 1 v 

v va 2 2 
2 (v ' ,v '')

U yoki ' '' v2 

v2 va 1 1 1 (v ' ,v '')

U bo‘lsa, u holda (v' 
,v'')

U bo‘ladi, bu yerda 1 1 1 v ' ,v ''

V , 2 2 2 v ' ,v ''

V , v' 

(v1 ' ,v2 
')

V va v'' 

(v1 '' ,v2 '')

V .
Bu yerda birlashma “ 

” amali V ning to‘plam, U ning esa kortej 
ekanligini e’tiborga olgan holda amalga oshiriladi. 

---

shakl 1 2 3 4 5 1 2 3 4 5 K2 K3 K2 

K3 6- shakl 1 2 3 4 5 1 2 3 4 5 4 3 
Shunday usul bilan hosol qurilgan G 

(V,U) graf G
1
va G
2
graflarning 
ko‘paytmasi deb ataladi va G 

G
1

G
2
kabi belgilanadi. 
Graflarning ko‘paytmasi ta’rifiga asosan berilgan ( , ) G1 

V1 U1 va ( , ) 
G2 

V2 U2 graflarning ko‘paytmasi hisoblangan G grafdagi:
– uchlar ( , ) v1 v2 yoki ( , ) v2 v1 ko‘rinishdagi juftliklardan iboratdir, bu 
yerda 1 V1 v 

, v2 

V2 ;
– v' 

(v1 ' ,v2 ')

V va v'' 

(v1 '' ,v2 '')

V uchlar faqat va faqat shu holda 
qo‘shni bo‘ladilarki, qachonki bu uchlarni (juftliklarni) tashkil qiluvchi 
elementlarning biri unga mos element bilan ustma-ust tushgan holda 
boshqa elementlar o‘z grafida qo‘shni bo‘lishsa, bu yerda 1 1 1 v ' ,v ''

V , 
2 2 2 v ' ,v ''

V ;
– 1 1 |V |

m , 2 2 |V |

m , 1 1 |U |

n va 2 2 |U |

n munosabatlardan 1 2 
|V |

mm va 1 2 2 1 |U |

m n 

m n bo‘lishi kelib chiqadi. 
7- m i s o l . 8- shaklda uchlari to‘plamlari kesishmaydigan K2 va K3 
graflarning ko‘paytmasi 

---

amali tasvirlangan. 
Dekart ko‘paytmalar bilan bog‘liq tuzilmalar ustida bajariladigan amallar 
boshqalaridan o‘ziga xosligi bilan ajralib turadi. Bu o‘ziga xoslik graflarni 
ko‘paytirish amalida namoyon bo‘ladi. Aniqrog‘i, graflar ko‘patmasida 
qatnashgan birorta grafning qirralari korteji bo‘sh bo‘lsada, ko‘paytirish 
amalini qo‘llash natijasida hosil bo‘lgan grafning qirralari korteji bo‘sh 
bo‘lmasligi ham mumkin. Haqiqatdan ham, yuqorida keltirilgan 
graflarning ko‘paytmasi ta’rifidan kelib chiqadiki, agar G 

(V,U) graf ( , ) 
G1 

V1 U1 va ( , ) G2 

V2 U2 graflarning ko‘paytmasi, ya’ni, G 

G1 

G2 bo‘lsa, u holda V 

V1 

V2 bo‘ladi va U kortej elementlari bilan ( ) ( ) 
V1

U2 

U1

V2 birlashma elementlari orasida o‘zaro bir qiymatli moslik 
mavjud. Shuning uchun, agar, masalan, U1 


, U2 


bo‘lsa, u holda 
(V1 

U2 )

(U1 

V2 ) 

V1 

U2 


bo‘ladi, chunki grafning tarifiga 
ko‘ra V1 


. Demak, U 


, ya’ni G1 bo‘sh graf bo‘lsada, G 

G
1

G
2
bo‘sh bo‘lmagan grafdir. 
Graflarni ko‘paytirish amalini takror qo‘llash usuli bilan graflar 
nazariyasining muhim sinfini tashkil etuvchi n o‘lchovli kublarni aniqlash 
mumkin. N o‘lchovli kub ( Q
n
) uchlari soni ikkiga teng bo‘lgan to‘la graf 
K2 yordamida quyidagi rekurrent formula bilan aniqlanadi:
Q
1

K
2
, Q
n

K
2

Q
n-1
.
Yuqorida graflar ustidagi ba’zi amallar haqida qisqacha ma’lumot berildi. 
Shuni ta’kidlash lozimki, graflar ustida bundan boshqa bir qator amallar 
ham bor. 
Xulosa. 
Yo'naltirilgan grafada chekka tartiblangan juftlik bo'lib, bu erda 
tartiblangan juftlik ikkita tepalikni bog'laydigan chekka yo'nalishini aks 
ettiradi. Boshqa tomondan, yo'naltirilmagan grafikada chekka tartibsiz 
juftlikdir, chunki chekka bilan bog'liq yo'nalish yo'q. Yo'naltirilmagan 
grafikalar yordamida ob'ektlar orasidagi nosimmetrik munosabatlarni aks 
ettirish mumkin. Yo'naltirilmagan grafadagi har bir tugunning darajasi va 
darajasi teng, ammo bu yo'naltirilgan grafik uchun to'g'ri emas. 

---

Yo'naltirilmagan grafikani ko'rsatish uchun matritsadan foydalanganda 
matritsa har doim nosimmetrik grafikaga aylanadi, lekin bu yo'naltirilgan 
grafikalar uchun to'g'ri kelmaydi. Yo'naltirilmagan grafani har bir chekkani 
qarama-qarshi yo'nalishda ketadigan ikkita yo'naltirilgan qirralar bilan 
almashtirish orqali yo'naltirilgan grafaga aylantirish mumkin. Biroq, 
yo'naltirilgan grafani yo'naltirilmagan grafaga aylantirish mumkin emas. 
Foydalanilgan adabiyotlar: 
1. Sadaddinova S.S., Abduraxmanova Yu.M., Raximova F.S. DISKRET 
MATEMATIKA 
2.www.tuit.uz. 
3. http://www.doc.ic.ac.uk/iccp/papers/discrete94.pdf 
4. Тўраев Х. Математик мантиқ ва дискрет математика. Т.: 
“Ўқитувчи”, 2003. 
5. Abduraxmanova Yu. M., RaximovaF.S. va boshqalar. Diskret 
matematika, o`quv qo`llanma, Toshkent, “ALOQACHI” nashriyoti, 2014y. 
6.Qalandarov O`.N., Abduvaitov X. A. Matematik mantiq masalalari 
tatbiqlari va ularni yechish uchun uslubiy ko`rsatmalar. Toshkent, 
“ALOQACHI” nashriyoti, 2012 y.