Graflar ustida amallar - Педагогика - Дипломные работы

Информация о документе

Цена	12000UZS
Размер	468.6KB
Покупки	0
Дата загрузки	06 Ноябрь 2026
Расширение	docx
Раздел	Дипломные работы
Предмет	Педагогика

Graflar ustida amallar

Купить

REJA:
KIRISH
ASOSIY QISM.
1 Graf va uning asosiy xossalari . Asosiy tushunchalar
2 Graflar ustida amallar
3 Graflarni ko’paytirish.
4 Bog’lamlilik
XULOSA
FOYDALANILGAN ADABIYOTLAR
2

KIRISh
Graflar nazariyasini va uning sonli xarakteristkalarini o’rganish dinamik
sistemalarni optimal boshqaruv masalasini hal etishga olib keladi. Bunda
qidirish va qochish masalalari ustida ish olib boriladi. Ushbu masalani o’yinlar
nazariyasi deb ataladi. O’yinlar nazariyasi bugungi kunda matematikaning eng
qiziqarli, dolzarb yo’nalishlaridan biri deyish mumkin. Umuman o’yin
tushunchasiga kelsak, u chekli o’yin, diskret o’yin va dinamik o’yin kabi
turlarga bo’linadi. Dinamik o’yinlar o’z navbatida graflar ustida yoki Evklid
fazosida qaralishi mumkin. Bunda esa masalaning holatiga qarab, zarur bo’lgan
sonni (qiymatni) topish zarurati tug’iladi. Topilgan qiymat amaliy jihatdan fan
va texnikaning ko’plab sohalariga tadbiq etiladi. Shu hisobdan dinamik
o’yinlarning juda ko’plab masalalarini hal etishda graflar va uning sonli
xarakteristkalaridan salmoqli darajada foydalanilib kelinmoqda.
Shu nuqtai nazardan graflar nazariyasi va uning sonli xarakteristkalrini
o’rganish masalasi fanning dolzarb masalalridan biri bo’lib qolmoqda.
Hozirgi kunda hayotimizga kompyuter texnologiyalari shu qadar jadal bilan
kirib kelmoqda–ki taraqqiyotning hech bir sohasini kompyuter texnologiyasiz
tasavvur etish qiyin bo’lib qoldi. Bu esa albatta, yangi dasturlar va unga zarur
bo’lgan matematik algoritmlarga bo’lgan ehtiyojni keskin oshirib yubormoqda.
Aynan optimal boshqaruv masalalari, ushbu talabga bo’lgan ehtiyojni qondirish
uchun zarur. Buning uchun esa graflar ustida amallar bajarib, zarur bo’lgan
qiymatlarni hisoblab, uning matematik modelini tuzish masalasini hal etish
zarurdir. Shu sababli, ushbu bitiruv malakaviy ishi graflar nazariyasi va uning
sonli xarakteristkalarni o’rganishni o’z oldigi maqsad qilib qo’ygan.
3

ASOSIY QISM.
1. Graf va uning asosiy xossalari . Asosiy tushunchalar .
Graflar nazariyasining asosiy masalasi berilgan nuqtalar va ularni
tutashtiruvchi chiziqlarning xossalaridan tashkil topadi. Bunday talqinda
chiziqlarnig to’g’ri chiziq yoki kesma, yoylardan yoki egri chiziqlardan iborat
bo’lishi hamda bu chiziqlar qaerda joylashishi, uzun yoki qisqa bo’lishi muhim
emas. Shunisi muhimki bu chiziqlar berilgan ikki nuqtani tutashtiradi.
1736 – yilda L.Eyler tomonidan o’sha davrda qiziqarli amaliy masalalardan
biri hisoblangan Kyonisberg ko’priklari haqidagi masalaning qo’yilishi va
echilishi graflar nazariyasining paydo bo’lishiga asos bo’ldi.
Kyonisberg shaxridagi Pregel daryosi ustiga qurilgan ettita ko’prik o’sha
vaqtda shaxarni to’rtta qismga ajratgan. Shaxarning ixtiyoriy qismida
joylashgan uydan chiqib ettita ko’rikdan faqat bir martadan o’tib, yana o’sha
uyga qaytib kelish mumkinmi? Kyonisberg ko’priklari haqidagi bu masalani hal
qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida
bu marshrut Eyler tsikli nomi bilan yuritiladi) mavjudligi shartlari ham topildi.
L.Eyler tomonidan e’lon qilingan tarixiy ilmiy ish yuz yildan kshproq vaqt
mobaynida graflar nazariyasi bo’yicha yagona ilmiy ish bo’lib keldi.
XIX asrning o’rtalarida graflar nazariyasi bilan bog’liq tadqiqotlar
G.Kirxgof (1924–1887, olmon fizigi) va A.Keli (1821–1895, ingliz matematigi)
ishlaarida paydo bo’ldi.
“Graf” iborasi D.Kyonig (1884–1944, venger matematigi) tomonidan 1936–
yilda graflar nazariyasiga bag’ishlangan dastlabki darsliklarda uchraydi.
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.
4

Avvalo grafning abstrakt matematik tushuncha sifatidagi ta’rifini keltiramiz.
Ixtiyoriy nuqtalarning qandaydir usulda bog’lanishidan tashkil topgan V
to’plamni qaraymiz. Ushbu
V to’plamni uchlar to’plami va uning v∈V−
elementlarini esa uchlar deb ataymiz.
V to’plamning v1∈V va v2∈V
elementlaridan tuzilgan
(v1,v2) ko’rinishidagi barcha juftliklar to’plamini ( V
to’plamning o’z-o’ziga Dekrat ko’paytmasini)
V× V deb belgilaymiz.
Graf deb shunday
(V ,U ) juftlikga aytiladiki, bu erda V ≠ O va
U − (v1,v2)
ko’rinishidagi juftliklar bo’lib, V× V to’plamning elementlaridan
tuzilgandir.
Grafni lotin alifbosining
G harfi bilan belgilaymiz.
Grafga ta’rif berishda boshqacha yondoshuvdan ham foydalanish mumkin.
G = G (V )
graf deb bir qancha V uchlar to’plamining birlashmasiga yoki
E=(a,b)(a,b∈V ) (1.1)
qaysi uchlar bog’langanligini ko’rsatuvchi juftliklarga
aytiladi.
Mos ravishda grafning geometrik tasvirida aniq har bir
(1.1) juftlik grafning
qirrasi deyiladi,
a va b uchlar esa E qirraning oxirlari deyiladi. Qirraning (1.1)
ta’rifida uning oxirgi ikki uchining joylashish tartibi e’toborga olinishi ham,
olinmasligi ham mumkin. Agar bunday tartib mavjud bo’lmasa, ya’ni
E = (a,b )= (b,a)
deyish mumkin bo’lsa, u holda E ni yo’naltirilmagan qirra
deb ataladi. Agar bunday tartib mavjud bo’lsa, u holda qirra yo’naltirilgan qirra
deyiladi. Yo’naltirilgan
E = (a,b ) qirrada a boshlang’ich uch, b oxirgi uch
deb hisoblanadi. Shuningdek
E qirrani a uchdan chiquvchi va b uchga
boruvchi qirra deyiladi. Qirra yo’naltirilgan bo’lgan holda ham,
yo’naltirilmagan holda ham
E= (a,b) qirra a va b uchlarga intsidient deb
ataladi.
5

Grafni yo’naltirilmagan deyiladi, agar uning barcha qirralari
yo’naltirilmagan bo’lsa (1.1.a–rasm), yo’naltirilgan deyiladi agar barcha
qirralari yo’naltiriligan bo’lsa (1.1.b– rasm).

1.1.a–rasm 1.1.b–rasm.
Ham yo’naltirilgan, ham yo’naltirilmagan qirralarga ega bo’lgan graf
aralash graf deyiladi. Misol sifatida, shaxarning xaritasini graf sifatida olsak, unda
ko’chalarni qirra deb, chorrahalarni esa uchlar sifatida olish mumkin. Bunda faqat
bir tomonlama harakat mavjud ko’chalarni yo’nalishga ega qirra deb olsak, u holda
ikki tomonlama harakat mavjud ko’chalarni hech qanday yo’nalish orqali belgilab
bo’lmaydi.
Hech bir qirraga intsidient bo’lmagan uch yakkalangan uch deyiladi. Agar
grafning ikkita uchini tutashtiruvchi qirra bor bo’lsa, u holda bunday uchlar
qo’shni uchlar deyiladi, aks holda esa qo’shni bo’lmagan uchlar deyiladi.
Faqat yakkalangan uchlardan tashkil topgan grafni nol graf deyiladi va 0
orqali belgilanadi.
Ikkita chetki ya’ni boshlang’ich va oxirgi qirralari ustma-ust tushga qirra
sirtmoq deyiladi va uni
L= (a,a) kabi yoziladi (1.2–rasm).
Agar grafning ikiita uchi o’zaro bir necha qirralar orqali tutashgan bo’lsa
bunday qirralarni parallel yoki karrali qirralar deyiladi (1.3–rasm).
Bunda agar graf yo’naltirilgan bo’lsa, hr bir qirra uchun yo’nalish
aniqlanadi. Misol sifatida, jamoaviy musobaqani olish mumkin. Bunda jamoalar
6

a a bmos ravishda grafning uchlari hisoblanadi. Ikkita
А va В jamoalar har safar bir-
biri bilan o’ynaganda ular qirra orqali tutashtiriladi. Agar
А jamoa В ni yutsa u
holda yo’nalish
А dan В tomon yoki, aksincha yo’naltiriladi. Durang natija esa
yo’naltirilmagan qirrani ifodalaydi.

7

1.2–rasm 1.3–rasm
Istalgan ikkita uchi qo’shni bo’lgan sirtmoqsiz va karrali qirralarsiz,
yo’naltirilmagan graf to’la graf deyiladi (1.4-rasm). Uchlari soni m ga teng to’la
graf
Km bilan belgilanadi. Ravshanki, Km grafning qirralar soni
N m= m (m − 1)
2
ta bo’ladi.
Grafni tekislikda tasvirlaganda qirralarning barcha kesishish nuqtalari
uchlardan iborat bo’lsa bunday graf tekis graf deyiladi (1.5–rasm).

1.4–rasm
1.5–rasm
Ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar soni
m va qirralar
soni
n ga qarab belgilanadi va bu holda grafni (m ,n) graf deb ataymiz.
Agar
G va G' graflarning uchlari to’plamlari, V va V' to’plamlar
orasida uchlarning qo’shnilik munosabatini saqlaydigan o’zaro bir qiymatli moslik
o’rnatilgan bo’lsa, u holda
G va G' graflar izomorf graflar deb ataladi (1.4–
rasm). Barcha izomorf graflar bir xil hossalarga ega bo’ladi.
Bog’lamli yo’naltirilmagan tsiklga ega bo’lmagan graf daraxt deyiladi. Hususiy
holda daraxt sirtmoq va karrali qirralarga ega bo’lmaydi.
Teorema 1.1. Daraxtda ixtiyoriy ikki uch yagona zanjir bilan
bog’langan bo’ladi.
8

Lokal darajalar . Agar grafni uni tashkil etuvchi qirralari soni sanoqli bo’lsa,
chekli graf , aksincha bo’lsa, cheksiz graf deb ataymiz. G−
yo’naltirilmagan graf bo’lsin. Bitta a uchga intsidient bo’lgan qirralar
soni uning lokal darajasi deyiladi va uni
ρ(a) (1.2) kabi belgilaymiz. Biror
uchning lokal darajasi hisoblanish jarayonida shu uchga intsidient bo’lagan
sirtmoq uchun noaniqlik vujudga keladi. Ya’ni, sirtmoqni qanday hisobga qo’shish
kerak; bitta qirra sifatidami yoki ikkita. Ushbu holatda qaralayotgan masalaga
bog’liq ravishda qanday hisoblash qulaylik tug’dirsa, shunday hisoblagan
ma’quldir. Shunga ko’ra, har bir holatda sirtmoqni qanday tartibda hisoblanganligi
ko’rastilishi zarur.
Lokal daraja uchun bir necha sodda formulalar keltiramiz.
G grafdagi a va
b
uchlarni tutashtiruvchi qirralar sonini ρ(a,b)= ρ(b,a) kabi belgilaymiz. Agar
grafda karrali qirralar bo’lmasa, u holda quyidagicha hollar bo’lishi mumkin:
ρ(a,b)= 0
ρ(a,b)= 1
Ko’rinib turibdiki, har bir (1.1.2) lokal darajada
a uch uchun quyidagi yig’indi
mavjud:
ρ(a)= ∑
b∈V
ρ(a,b)
(1.3)
G
grafdagi qirralar sonini v deb belgilaymiz. Har bir qirra a va b uch
bo’yicha ikkita lokal darajada ishtirok etadi, bundan esa quyidagiga ega bo’lamiz:
2v= ∑
a∈V
ρ(a)
(1.4)
yoki (1.3) ga ko’ra esa
2v= ∑
a,b∈V
ρ(a,b)
(1.5)
9

(1.4) formuladan ko’rinib turibdiki, chap tomon har doim juft son bo’ladi.
Yuqoridagi formulalardan ko’rish mumkinki, yo’naltirilmagan grafda barcha
uchlar lokal darajalar yig’indisi qirralar sonining ikki baravariga teng juft son
bo’ladi, chunki qirralarni sanaganda har bir qirra o’zi intsidient bo’lgan uchlarda
ikki marta qatnashadi. Shunga ko’ra XVIII asrdayoq L.Eyler tomonidan
quyidagicha tasdiq isbotlangan.
Lemma–1. Ixtiyoriy yo’naltirilmagan grafda barcha uchlar darajalari
yig’indisi qirralar sonining ikki baravariga teng.
Teorema 1.2. Chekli grafda toq darajali uchlar soni juft sonda
bo’ladi.
Agar grafning barcha uchlari bir xil
n –darajaga ega bo’lsa, u holda bunday
graf
n− darajali regulyar graf deb ataladi: ρ(a)= n .
Regulyar graflarga misol sifatida beshta muntazam ko’pyoqlar: tetraedr,
kub, oktaedr, dodokaedr va ikosaedrlarni keltirish mumkin. Ma’lumki, regulyar
grafning har bir uchidan bir hil sondagi qirralar chiqadi, demak (1.4) formulaga
ko’ra
2v= ∑ ρ(a)= nu bo’ladi, bu erda u− uchlar soni.
v= nu
2
= 1
2
nu . Demak,
n−
darajali u ta uchga ega regulyar grafda
1
2
nu ta qirra bo’ladi. Bunda agar,
n
toq bo’lsa,
u juft sonda ishtirok etadi. Chunki, a va b uchlarni tutashtiruvchi bitta
qirra ham
a uchda ham b uchda hisoblanadi.
Masalan. Tetraedrni olaylik. Unda lokal darajasi 3(toq)ga teng, undagi uchlar soni
4 ga teng. U holda qirralar soni
v= nv
2
= 3⋅4
2
= 6 . Oktaedrda lokal darajasi 4 ga,
uchlar soni 6 ga teng. U holda qirralar soni
v= 4⋅6
2
= 12 ga teng bo’ladi.
10

1
2
3
45
6 1
2
3
452. Graflar ustida amallar.
Graflar ustida turli amallar bajarish mumkin, masalan, graflarni birlashtirish,
biriktirish, ko’paytirish,
graflarni qismlarga
ajratish va
hakazo.
Eng
sodda amallardan biri siftida grafdan uchni olib tashlash amalini ko’rsatsa
bo’ladi. Bu amalni qo’llash berilgan grafning uchlar to’plamidan birorta elementni
lib tashlashni anglatadi. Natijada uchlari soni berilgan graf uchlari sonidan bittaga
kam yangi graf hosil bo’ladi. Albatta bu amalni uchlari soni ikkitadan kam
bo’lmagan graflar uchungina qo’llash mumkin bo’ladi. Shu bilan birga birorta
uchni olib tashlash bilan birga shu uchga intsidient bo’lgan qirralarni ham olib
tashlash nazarda tutiladi (2.1–rasm).
2.1–rasm.
Yuqoridagi misolda 6–uchni olib tashlash yordamida berilgan grafdan yangi graf
hosil qilindi.
Yana bir sodda misollardan biri bu grafdan qirrani olib tashlash amalini
ham kiritish mumkin. Bu amalga ko’ra berilgan grafning qirralari to’plamidan bitta
element olib tashlanadi. Berilgan grafdan qirrani olish tashlash jarayonida shu
12

1
2
3
45
6 1
2
3
45
6qirraga intsidient bo’lgan uchlarni olib tashlash ham, olib tashlamaslik ham
mumkin. Bunda masalaning mohiyatiga e’tibor qaratiladi (2.2–rasm).
2.2–rasm.
Yuqoridagi misolda (1,6) qirrani olib tashlash yordamida berilgan grafdan qirralar
soni bittaga kam bo’lgan yangi graf hosil qilindi.
Graflar ustida uchni olib tashlash va qirrani olib tashlash amallarini qo’llash
orqali quyidagicha natijaga erishiladi. G = (V ,U )
va   U V G    , graflar berilgan bo’lsin. Agar V '⊆ V va G
grafning barcha qirralari
G' grafning ham qirralari, ya’ni U '⊆ U bo’lsa, u holda
G'
graf G grafning qism grafi deyiladi.
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
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’rinli.
Graflar ustida yana 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 qo’shish
amalini kiritish mumkin.
13

Grafda yangi uchni qo’shish turlicha usul bilan amalga oshirilishi mumkin.
Masalan, yangi v uchni berilgan grafga qo’shish shu grafning v1 va v2 uchlariga
intsidient 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 intsidient u1 qirra
hamda
v va v2 uchlarga intsidient u2 qirra qo’shiladi.
Bu jarayon grafda qirraga darajasi 2 bo’lgan yangi uchni qo’shish yoki
qirrani ikkiga bo’lish amali deb ataladi.
Ta’rif: Agar
G graf G grafdan qirrani ikkiga bo’lish amalini chekli marta
qo’llash vositasida hosil qilingan bo’lsa, u holda
G graf G grafning bo’linish grafi
deyiladi.
Bo’linish graflari izomorf bo’lgan graflar gomeomorf graflar deb ataladi.
Quyida 2.3–rasmda tasvirlangan graflar izomorf emas, lekin ular gomeomorf,
chunki bu graflarning har biri 2.4–rasmda tasvirlangan bo’linish grafiga ega.
2.3–rasm.
14

1
2
2 K

3
4
5
3 K
1
2
3 2 K K 
3
4
5
1
2
3
4

3
5
4
3
4
5
1
22.4–rasm.
Graflar ustida mallar qatoriga graflarni birlashtirish, graflarni biriktirish,
graflarni ko’paytirish amallarini kiritsh mumkin.
Graflarni birlashtirish.
G1= (V 1,U 1) va G 2= (V 2,U 2) graflar berilgan
bo’lsin. Uchlari to’plami
V= V1 V2 va qirralari korteji U = U 1 U 2 kabi
aniqlangan
G = (U ,V ) graf G1 va G2 graflarning birlashmasi deb ataladi va
G = G 1 G 2
ko’rinishda belgilanadi. 2.5–rasmda uchlari to’plami
kesishmaydigan
K2 va K3 graflarning birlashmasi amali tasvirlangan.
2.5–rasm.
Ta’rif : Agar birlashtirilayotgan graflarning uchlari to’plami kesishmasa, u
holda bu graflarning birlashmasi dizyunkt birlashma birlashma deyiladi.
Uchlari to’plamlari kesishadigan graflarning birlashmasi amali 2.6–rasmda
tasvirlangan.
15

1
2
2 K

3
4
5
3 K
1
2
3 2 K K 
3
4
52.6–rasm.
2.5–rasmda tasvirlangan birlashma dizyunkt, 2.6–rasmda tasvirlangan
birlashma esa – dizyunkt emas.
Graflarni biriktirish.
G1= (V 1,U 1) va G 2= (V 2,U 2) graflar berilgan
bo’lsin.
G1 va G2 graflar birlashtirilshi hamda G1 grafning har bir uchi G2
grafning har bir uchi bilan qirra vositasida tutashtirilishi natijasida hosil bo’lgan
G = (U ,V )
graf G1 va G2 graflarning birikmasi deb ataladi va G = G 1+G 2
ko’rinishda belgilanadi.
2.7–rasmda 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
hossalarini e’tiborga olish kerak bo’ladi.
2.7–rasm.
3.Graflarni ko’paytirish.
16

1

1
1v
2v 3v
 1 ,1 v
 2 ,1 v
 3 ,1 v
 1 ,2 v  2 ,2 v
 3 ,2 vGraflarni ko’paytirish.
G1= (V 1,U 1) va G 2= (V 2,U 2) graflar berilgan
bo’lsin. Uchlari to’plami
V= V1× V2 bo’lgan G = (V ,U ) grafning qirralari
kortejini quyidagicha aniqlaymiz: agar
v1
'= v2
' va (v2
'= v2
'')∈U 2 yoki v2
'= v2
'' va
(v1
'= v1
'')∈U 1
bo’lsa, u holda (v',v'')∈U bo’ladi, bu erda
v1',v1'∈V 1, v2',v2''∈V 2, v'= (v1',v2')∈V
va v''= (v1'',v2'')∈V . Shunday usul
bilan qurilgan
G = (V ,U ) graf G1 va G2 graflarning ko’paytmasi deb ataladi va
G = G 1× G 2
kabi belgilanadi.
Graflarning ko’paytmasi ta’rifiga asosan berilgan
G1= (V 1,U 1) va
G 2= (V 2,U 2)
ko’paytmasi hisoblangan G grafdagi:
– uchlar
(v1,v2) yoki (v2,v1) ko’rinishidagi juftliklardan iboratdir, bu erda
v1∈V1,v2∈V 2;
–
v'= (v1',v2')∈V va v''= (v1'',v2'')∈V uchlar faqat va faqat shu holda qo’shni
bo’ladiki, bu uchlarni tashkil qiluvchi elementlarning har biri unga mos element
bilan ustma-ust tushgan holda boshqa elementlar o’z grafida qo’shni bo’lishsa, bu
erda
v1
',v1
''∈V1,v2
',v2
''∈V2;
–
|V 1|= m1, |V 2|= m 2, |U 1|= n1, |U 2|= n2 munosabatlardan |V|= m1m2 va
|U |= m 1n2+m 2n1
bo’lishi kelib chiqadi.
2.8–rasmda uchlari to’plami kesishmaydigan
K2 va K3 graflarning
ko’paytmasi amali tasvirlangan.
17

2.8–rasm.
Yuqorida ko’rib o’tildiki, Dekart ko’paytmalar bilan bog’liq tuzilmalar
ustida bajariladigan amallar boshqalardan o’ziga xosligi bilan ajralb turadi. Bu
o’ziga xoslik graflarni ko’paytirish amalida namoyon bo’ladi. Aniqrog’i, graflar
ko’paytmasida qatnashgan birorta grafning qirralar korteji bo’sh bo’lsada,
ko’paytirish amalini qo’llash natijasida hosil bo’lgan grafning qirralar korteji bo’sh
bo’lmasligi ham mumkin. Haqiqaan ham, yuqorida keltirilgan graflarnng
ko’paytmasi ta’rifidan kelib chiqadiki, agar G = (V ,U ) graf G1= (V 1,U 1) va
G 2= (V 2,U 2)
graflarning ko’paytmasi, ya’ni G = G 1× G 2 bo’lsa, u holda
V= V1× V2
bo’ladi va U kortej elementlari bilan (V 1× U 2) (U 1× V 2) birlashma
elementlari orasida o’zaro bir qiymatli moslik mavjud. Shuning uchun, agar,
masalan,
U 1= θ , U 2≠ θ bo’lsa, u holda (V 1× U 2) (U 1× V 2)= V 1× U 2≠ θ
bo’ladi, chunki grafning tarifiga ko’ra
V ≠ θ. 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 rekkurent formula bilan aniqlanadi:
Q 1= K 2⋅Q n= K 2× Q n−1.
4. Bog’lamlilik
Uchlar to’plami
V va qirralar to’plami U bo’lgan yo’naltirilmagan
G = (V ,U )
graf berilgan bo’lsin. Bu G grafdagi ikkita qo’shni Ei va Ei−1
qirralari umumiy uchga ega
18

5
1 3
9
8
7 4
6
2
S= (...,E0,E1,...,En,En+1,...), (3.1)
ko’rinishdagi chekli yoki cheksiz ketma-ketlikka marshrut deb ataladi. Ikkita
qo’shni qirraning umumiy uchga egaligidan uni quyiddagicha ham yozish
mumkin:

S=(...,E0=(a0,a1),E1=(a1,a2),...,En=(an,an+1)), (3.2)
Shuni ta’kidlash lozimki, marshrutda bitta
E qirra bir necha marta ishtirok etishi
mumkin (3.1–rasm).

3.1– rasm.
Agar (3.1) marshrutda
E0 qirradan oldin hech qanday qirra mavjud
bo’lmasa u holda,
a0 uch S marshrutning boshlang’ich uchi , agar En−1 qirradan
keyin hech bir qirra mavjud bo’lmasa u holda,
an uch oxirgi uchi deyiladi. Ikkita
qo’shni
Ei va Ei−1 qirralarga tegishli bo’lgan ixtiyoriy ai uch ichki uch deyiladi.
Ko’rinib turibdiki marshrutda qirralar va uchlar takrorlanishi mumkin, shu bilan
birga ichki uch ham boshlang’ich yoki oxirgi uch sifatida ishtirok etishi mumkin.
Tabiiiyki, marshrut:
– boshlang’ich uchga ega bo’lib, oxirgi uchga ega bo’lmasligi, yoki,
aksincha, oxirgi uchga ega bo’lib, boshlang’ich uchga ega bo’lmasligi mumkin.
Bunday marshrut bir tomonlama cheksiz marshrut deyiladi;
19

– boshlang’ich uchga ham, oxirgi uchga ham ega bo’lmasligi mumkin.
Bunday marshrut ikki tomonlama cheksiz marshrut deyiladi.
– Birorta ham qirraga ega bo’lmasligi mumkin. Bunday marshrut trivial
marshrut deyiladi.
– Faqatgina yagona qirradan iborat marshrut bo’lishi mumkin. Bunday
marshrut nol marshrut yoki notrivial marshrut deyiladi.
Agar S marshrut a0 boshlang’ich uchga va an oxirgi uchga ega bo’lsa, u
holda uni

S = S (a0,an) (3 .3)
kabi yoziladi. (3.3) kabi belgilangan marshrutning uzunligi
n deb a0 va an
uchlarni tutashtiruvchi qirralar soniga aytiladi. (3.1–rasm) keltirilgan marshrutning
uzunligi 7 ga teng. Marshrutning ikkita
ai va aj uchlaridan tuzilgan marshrut S
marshrutning qismi deyiladi. Marshrutning oxirgi va boshlang’ich uchlari ustma–
ust tushsa, ya’ni,
a0= an bunday marshrut tsiklik marshrut deyiladi.
Agar marshrutda qirralar faqat bir martadan ishtirok etsa, zanjir deyiladi.
Tsiklik marshrutda qirralar faqat bir martadan ishtirok etsa, tsikl deyiladi. Bu ikki
holda ham uchlar bir necha marta takror ishtirok etishi mumkin. Agar zanjirning
chetki uchlaridan boshqa barcha uchlari turlicha bo’lsa, ya’ni hech bir uch
takrorlanmasa, u holda uni yopiq zanjir deb ataladi. Marshrutning oxirgi va
boshlang’ich uchlari ustma–ust tushsa, ya’ni,
a0= an bo’lib, unda ishtirok etgan
qirralar va uchlar bir martadan ishtirok etsa u holda uni oddiy tsikl deb ataladi.
Berilgan
(a0,a1,...,as) zanjir uchun a0= as bo’lsa, u yopiq zanjir deb ataladi.
Sirtmoq yoki bir juft karrali qirralar tsikl tashkil etishi ravshan.
Yuqoridagi tushunchalarda graf
G yyo’naltirilmagan deb faraz qildik.
Yo’naltirilgan graflar uchun ham marshrut, zanjir va oddiy zanjir tushunchalarini
kiritsh mumkin. Bu holda (3.2) dagi barcha qirralar yo’naltirilgan qirralar bo’ladi,
20

1 1u 6u
4u
2u 3u
5u
2
3 4unda esa yo’nalishlari qirralarga mos holda yo’naltirilgan marshrut, zanjir va oddiy
zanjir tushunchalari kiritiladi.
Yo’naltirilgan marshrut uchun zanjir tushunchasiga o’xshash yo’l
tushunchasini ham kiritish mumkin. Boshlang’ich va oxirgi uchlari ustma–ust
tushadigan yo’naltirilgan zanjir kontur deb ataladi.
Ushbu 3.2–rasmda keltirilgan graf uchun
(3,u4,2,u1,1,u1,2,u6,2,u4,3,u5,4)
ketma–ketlik 3 belgili uchdan 4 belgili uchga
yo’nalgan marshrutdir, bunda 3–boshlang’ich, 4–esa oxirgi uch. Bu marshrutda 1,2
va 3 belgili uchlar oraliq uchlar hisoblanadi. Qaralayotgan marshrutning uzunligi 6
ga teng bo’lib, u zanjir bo’la olmaydi, chunki 1belgili uch ikki marta (birmarta
oraliq uch sifatida, ikkinchi marta oxirgi uch sifatida) ishtirok etmoqda.
(3, 2,1,3) zanjirning oxirgi qirrasi sifatida
u2 yoki u3 qirralardan qaysi biri
olinishiga bog’liqsiz ravishda u yopiq zanjir va tsikldir.

3.2–rasm.
Yuqorida keltirilgan tushunchalar uchun quyidigicha teoremani keltiramiz.
Teorema. Agar grafdagi har bir uchning lokal darajasi ikkidan
kichik bo’lmasa, u holda bu graf tsiklga ega.
Isboti. Agarda graf sirtmoqlar yoki karali qirralardan iborat bo’lsa,
teoremaning isboti ravshan. Shu sababli teorema isbotini graf karrali qirralar va
sirtmoqlar bo’lmagan holda keltiramiz.
21

Faraz qilaylik, v∈V berilgan G = (V ,U ) grafning ixtiyoriy uchi bo’lsin.
Qaralayotgan
v uchga qo’shni v1 uchni va bu uchga v dan farqli boshqa qo’shni
v2
uchni v2 uchga esa v1 dan farqli boshqa v3 uchni va hakozo, vi uchga vi−1 dan
farqli boshqa qo’shni
vi+1 uchni va hakazo, tanlab,
((v,v1),(v1,v2),(v2,v3),...,(vi−1,vi),(vi,vi+1),...)
qirralar ketma-ketligini tuzamiz. Teoremaning shartiga ko’ra yuqoridagi ketma-
ketlikni tuzish va talab etilgan hossaga ega
vi+1 uchni har doim topish mumkin.
Grafning uchlar to’plami
V chekli to’plam bo’lganligidan, yuqorida bayon
etilgan uchlar ketma–ketligini qurish jarayonida chekli qadamdan so’ng albatta
oldin uchragan uchlardan birini tanlashga majburmiz. Agar biror
vk uch ketma–
ketlkda ikki marta uchragan birinchi uch bo’lsa, ketma–ketlikka qirralar qo’shish
jarayonini to’xtatamiz., chunki tuzilgan qirralar ketma–ketligining
vk uch ikki
marta qatnashgan qismi biz izlayotgan tsikldir. Teorema isbot bo’ldi.
G
graf yo’naltirilmagan graf bo’lsin. Agar oxirlari a va b uchlardan iborat
(3.1) ko’rinishdagi marshrut marshrut mavjud bo’lsa, u holda ikkita
a va b uchlar
bog’langan deyiladi. Agar
S marshrut qandaydir ai uchdan bir martadan ko’p
o’tsa, u holda uning tsiklik qismini o’chirib tashlash orqali,
a va b uchlarni
bog’lovchi qirralardan iborat yangi
S' marshrut hosil qilinadi. Bundan kelib
chiqadiki, marshrut bilan bog’langan uchlar doimo oddiy zanjir bilan ham
bog’langan bo’ladi. Agar grafda uning ixtiyoriy ikki uchi bog’langan bo’lsa, bu
holda uni bog’lamli graf deb ataladi.
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.
G = (V ,U ) grafning uchlar to’plami uchun juft–jufti bilan
22

kesishmaydigan quyidagicha V = ¿
i
V i (3.4) yig’indi mavjud. Bunda har bir Vi
qism to’plamdagi uchlar o’zaro bog’langan, turli
Vi qism to’plamdagi uchlar
o’zaro bog’lanmagan bo’ladi. Mos ravishda (3.4) yig’indidan
G grafning G (Vi)
qism graflari kesishmaydigan quyidagicha
G = ¿
i
G (V i) (3.5) to’g’ri yig’indisi
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 ikkita uchlar toq lokal
darajaga ega bo’lsa, u holoda ular bog’langan bo’ladi.
Masofa.
G yo’naltirilmagan bog’lamli graf bo’lsin. Ixtiyoriy a va b
uchlari bog’langan bo’lsa, u holda oxirlari
a va b bo’lgan S= (a,b) bo’lgan
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
orasidagi masofa deyiladi va
d(a,b) kabi belgilanadi. Ta’rif bo’yicha bu masofalar
uchun
d(a,a)= 0 tenglik bajariladi. Oson ko’rish mumkinki, bu aniqlangan
masofa funktsiyasi metrika aksirmalarini qanoatlantiradi:
1.
d(a,a)≥ 0.
2.
d(a,b)= 0 tenglik shunda va faqat shunda bajariladiki, qachonki,

a= b .
23

3. d(a,b)= d(b,a) .
4. Uchburchak tengsizligini qanoatlantiradi:
d(a,b)d(b,c)≥ d(a,c) .
Chekli graflar uchun uning ikki uchi orasidagi eng uzun masofani
ifodalovchi chegaralangan diametr tushunchasini kiritish mumkin:

d (G )= maxa,b∈Vd (a ,b) (3.6)
Mos ravishda eng uzun masofaga ega ikki uchni bog’lovchi oddiy zanjirni
diametrial oddiy zanjir deb ataymiz.
Qandaydir fiksirlangan
с uchni olamiz va undan G ning uchigacha bo’lgan
eng uzun masofani

r(c)= maxx∈V d (c,x) (3.7)
kabi belgilaymiz. Agar (2.1.7) qiymat
с0 uchda

r0= r(c0)= minc∈V r(c) (3.8)
eng kichik qiymatga erishsa, u holda bu
с0 uchni G grafning markazi deb ataladi.
(3.8) qiymatni
G grafning radiusi deb, с0 uchdan eng uzun masofadagi qandaydir
uchgacha bo’lgan ixtiyoriy eng qisqa oddiy zanjirni radial oddiy zanjir deb
ataladi. Grafda markaz yagona bo’lmasligi mumkin. Faraz qilaylik,
G – chekli,
lokal darajasining yuqori chegarasi
ρ0≥ 2 bo’lgan graf bo’lsin. Ixtiyoriy a0
uchni olaylik va bu uch uchun
V = ¿
n
An uchlar yoyilmasi mavjud bo’lsin. a0
uchdan
A1 uchga ρ0 dan ko’p bo’lmagan qirralar chiqadi. Har bir a1∈ A1 uchdan
A2
uchga ρ0 dan ko’p bo’lmagan qirralar chiqadi va hakazo. Bundan quyidagi
tengsizlik kelib chiqadi:
24

n<1+ ρ0+ ρ02+ ρ03+ ...+ ρ0r≤ 1
ρ0− 1 (ρ0r+1− 1) (3.9)
Bundag esa, quyidagicha tasdiq kelib chiqadi: biror
x uch ikkita a va b uchlar
orasidagi eng qisqa uchga tegishli bo’ladi shunda va faqat shundaki, qachonki
d(a,x)+d(x,b)= d(a,b)
tenglik o’rinli bo’lsa.
25

Xulosa.
Ushbu bitiruv malakaviy ish graflar nazariyasi va uning sonli
xarakteristkalariga bag’ishlangan. Graflar nazariyasi fanga XIX asr oxirlarida kirib
kelgan Graflar nazariyasining fan sifatida shakllanishiga L. Eyler tomonidan
Kyonisberg ko’priklari g’aqidagi masala asoso bo’lib xizmat qildi. Muallif
tomonidan bu masalani echish uchun yozilgan maqolasi dastlabki ilmiy manba
hisoblanadi.
Bitiruv malakaviy ishda graf tushunchasi, uning abstrakt ta’rifi, turlari,
uning tashkil etuvchilari (qirralar va uchlar) ta’riflar yordamida bayon etilgan.
Graflar ustida sodda amallar (graflarni qo’shish, ko’paytirish, uchni yoki qirrani
qo’shish, olib tashlash) bajarilgan. Bajarilgan amallar aniq geometrik chizmalar
yordamida ko’rsatilgan.
Graf: daraxt o’rganilgan: G(m,n)-graf uchun daratlar xaqidagi asosiy
teorema va bu teoremadan kelib chiqadigan natijalar keltirilgan. Shu bilan birga
tarmoq va tarmoqda Ford tomonidan taklif etilgan maksimal oqimni topish
algoritmi bilan tanishalgan. Ford algoritmining jadvallar bilan ish ko'riladigan
jarayon dastlabki, umumiy (takrorlanuvchi) va yakuniy qadamlardan ibort bo'lib,
ular batafsil keltirilgan.
Ushbu bitiruv malakaviy ishda keltirilgan koeffitsientlar yordamida
graflarda qochish va qidirish masalalarini hal qilish usullarini topish nazariyasi
paydo bo’ladi.
Shu sababli, bitiruv malakaviy ishda keltirilgan natijalar graflar
nazariyasi hamda matematikaga qiziquvchilar uchun foydali deb hisoblaymiz.
26

Foydalanilgan adabiyotlar .
1. O’zbekiston Respublikasining “Ta’lim to’g’risida” gi Qonuni (1997
yil 29 avgustda qabul qilingan)/.Barkamol avlod – O’zbekiston
taraqqiyotining poydevori. –T.: O’zbekiston. 1997.
2. O’zbekiston Respublikasining “Kadrlar tayyorlash milliy dasturi”/.
Barkamol avlod –O’zbekiston taraqqiyotining poydevori. –
T .: O’zbekiston . 1997 .
3. C o o k. W.J., C u n n i n g h a m., W. H., P u l l e y b l a n k. W.R.,
S c h r I j v e r. A. Combinatorial optimization. New York, John Wiley &
Sons, Inc, 1998, 355 p.
4. О. О р е. Теория графов. М.: Наука, 1980, 336 с.
5. Ф. Харрари. Теория графов. Москва – 1973.
6. А.А.Азамов. Основания теории дискретн ых игр. Тошкент –2011.
7. Н.Кристофидес. Алгоритмический подход., Моква –1978.
8. А.И. Благодатских. Введение в оптимальное управления. Москва –
2001.
9. Б.Н.Пшеничный., В.В. Остапенко. Дифференциальные игры. Киев –
1992.
10. Б.Б. Рихсиев. Дифференциальные игры с простыми движенями.
Тошкент –1989.
11. Ж.С.Маматов., Х.Норжигитов. О длине полуэйлеровых циклов в
графах. ЎзР ФА маърузалари. №2. 2012.6-8сс.
12. Ж.С.Маматов. Об оценке длин ы полуэйлеров ы х циклов в графах.
Тезисы докладов республиканской научной конференции с участием
зарубежных ученых «Операторные алгебры и смежные проблемы».
Тошкент. 2012. 177с.
27

13. A.Azamov. J.S. Mamatov. Semieulerian Cycles in Graphs and their
Applications to Dynamical Searching Game.// Game theory and
management. The sixth International Conference Game Theory and
Management – GTM 2012/ pp 37-38.
14. Ж.С.Маматов. “Графларда яримэйлер циклларини баҳолаш”. Аниқ
фанларни ўқитишнинг долхзарб муаммолари. Илмий-амалий анжуман
материаллари. Гулистон –2013. 50бет.
15. Ҳ.Тўраев., И. Азизов. Математик мантиқ ва дискрет математика.
Тошкент, 2011.
16. www.edu.uz .
17. www.ziyonet.uz .
18. www.mathnet.ru
28

Graflar ustida amallar

Купить

Похожие документы
2001-yil sentabr voqealri va uning xalqaro munosabatlarga
1945-1990-yillarda Buyuk Britaniya
1918-1923 yillarda xalqaro munosabatlar, Versal Vashington siyetemasining tuzilishi
Ahmad al-farg‘oniy
Almashlab ekishni loyihalashtirish va joriy etish