Diskret tuzilmalari fanidan

MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI



diskret tuzilmalari fanidan
Mustaqil ish


Bajardi: Xayrullayev Jasur


Tekshirdi: Matyakubov Marks


Toshkent 2023


Mavzu: Yo’nalgan graflar matritsalari, yo’l tushunchasi

Reja:
1. Graflar nazariyasi.
2. Yo’nalgan graflar nazariyasi.
3. Yo’l tushunchai.
4. Xulosa

Graflar nazariyasi haqida umumiy ma’lumotlar.

1736- yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy
masalalardan biri hisoblangan Kyonigsberg1 ko'priklari haqidagi
masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo
bo‘lishiga asos bo‘ldi. Kyonigsberg shahridagi Pregel daryosi ustida
qurilgan yettita ko'prikning joylashuvi 1- shakldagi qadimiy xaritada
tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7 raqamlar bilan
belgilangan. Pregel daryosi Kyonigsberg shahrini o ‘sha davrda to‘rtta
A , В , С va D qismlarga bo‘lgan. Shaharning ixtiyoriy qismida
joylashgan uydan chiqib yettita ko‘prikdan prikdanfaqat bir martadan
o‘tib, yana o‘sha uyga qaytib kelish mumkinmi? Kyonigsberg
ko‘priklari haqidagi bu masalani hal qilish jarayonida graflarda
maxsus marshrut mavjudligi shartlari ham topildi. Bu natijalar e’lon
qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan.

Avvalo, grafning abstrakt matematik tushuucha. sifatidagi

ta’rifini va boshqa ba’zi sodda tushunchalami keltiramiz. V qandaydir
bo'shmas to‘plam bo‘lsin. Uning v1 e V va v2 e V elementlaridan
tuzilgan ko‘rinishdagi barcha juftliklar (kortejlar) to‘plamini
(V to‘plamning o‘z-o‘ziga Dekart ko‘paytmasini) V x V bilan
belgilaymiz.
Graf deb shunday juftlikka aytiladiki, bu yerda va
U - (v1 e V, v2 e V ) ko‘rinishdagi juftliklar korteji bo‘lib,
VxV to‘plamning elementlaridan tuzilgandir.
Bundan buyon grafni belgilashda yozuv o‘miga (V,U)
yozuvdan foydalanamiz. Grafning tashkil etuvchilarini ko‘rsatish muhim
bo‘lmasa, u holda uni lotin alifbosining bitta harfi, masalan, G bilan
belgilaymiz.
Grafning abstrakt ta ’rifl va u bilan bog‘liq boshlang‘ich
tushunchalar.

Yo’naltirilgan graflar nazariyasi

Oddiy yo'naltirilgan graf. Bu erda ikki boshli o'q har bir yo'nalish uchun
bittadan ikkita qirrani aks ettiradi.
Yilda matematika, va aniqrog'i graf nazariyasi, va yo'naltirilgan
graf (yoki digraf) va graf to'plamidan tashkil topgan tepaliklar bilan
bog'langan qirralar, bu erda qirralarning ular bilan bog'liq yo'nalishi bor.
Rasmiy ma'noda, yo'naltirilgan graf buyurtma qilingan juftlikdir G = (V,
A) qayerda. A to'plamidir buyurtma qilingan juftliklar deb nomlangan
tepaliklar o'qlar, yo'naltirilgan qirralar (ba'zan oddiygina qirralar tegishli
to'plam bilan nomlangan E o'rniga A), yo'naltirilgan yoylar, yoki yo'naltirilgan
chiziqlar.
Bu oddiy yoki yo'naltirilmagan graf, bunda ikkinchisi atamalar bilan
belgilanadi tartibsiz juftliklar odatda chaqiriladigan tepaliklarning qirralar,
yoylar, yoki chiziqlar.

Yuqorida aytib o'tilgan ta'rif yo'naltirilgan grafda bir xil manba va maqsad

tugunlari bilan bir nechta o'qlarga ega bo'lishiga yo'l qo'ymaydi.
Ammo ba'zi mualliflar yo'naltirilgan graflarda bunday bir nechta o'qlarga ega
bo'lishiga imkon beradigan kengroq ta'rifni ko'rib chiqadilar (ya'ni ular o'qlarni
o'rnatishga imkon beradi) multiset ). Aniqrog'i, ushbu sub'ektlar quyidagi
manzilga murojaat qilishadi yo'naltirilgan multigraflar (yoki multidigraflar).
Boshqa tomondan, yuqorida aytib o'tilgan ta'rif yo'naltirilgan graflarga ega
bo'lishiga imkon beradi ko'chadan (ya'ni tugunlarni o'zlari bilan to'g'ridan-to'g'ri
bog'laydigan strelkalar), ammo ba'zi mualliflar yo'naltirilgan grafikalarda
ilmoqlarga ruxsat bermaydigan torroq ta'rifni ko'rib chiqadilar. Aniqrog'i,
halqasiz yo'naltirilgan graflar quyidagi manzilga yo'naltirilgan oddiy
yo'naltirilgan graflar, halqalar bilan yo'naltirilgan graflar quyidagi manzilga
yo'naltirilgan loop-digraflar (bo'limga qarang Yo'naltirilgan graflar turlari ).

G = (V,U ) graf berilgan bo‘lsin. V to‘plamning elementlariga G grafning uchlari, V to‘plamning o‘ziga esa, graf uchlari to‘plami deyiladi. Graflar nazariyasida “uch” iborasi o‘miga, ba’zan, tugun yoki nuqta iborasi ham

qoilaniladi. G = {V,U) grafning ta’rifiga ko‘ra, U bo‘sh kortej bo’lishi ham mumkin. Agar U bo‘sh bo'lmasa, u holda bu kortej (a,b) ( a e V , b e V) ko‘rinishdagi juftliklardan tashkil
topadi, bunda a = b bo'lishi hamda ixtiyoriy (a, b) juftlik U kortejda istalgancha
marta qatnashishi mumkin.
(a,b) e U juftlikni tashkil etuvchi a va b uchlaming joylashish tartibiga bog‘liq
holda, ya’ni yo'nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash mumkin.
Agar (a,b ) juftlik uchun uni tashkil etuvchilaming joylashish tartibi ahamiyatsiz,
ya’ni (a,b) = (b,a) bo‘lsa, (a,b) juftlikka yo‘naltirilmagan (oriyentirlanmagan) qirra
(yoki, qisqacha, qirra) deyiladi. Agar bu tartib muhim, ya’ni (a,b) = (b,а) bo‘lsa, u
holda {a, b) juftlikka yoy yoki yo‘naltirilgan (oriyentirlangan) qirra deyiladi.
U kortejning tarkibiga qarab, uni yo grafning qirralari korteji, yo yoylari korteji, yoki
qirralari va yoylari korteji deb ataymiz. Grafning uchlari va qirralari (yoylari) 
uning elementlari deb ataladi.

Eyler graflari. Graflar nazariyasining shakllanishi Kyonigsberg

ko‘priklari haqidagi masala bilan bog‘liq ekanligi yaxshi ma’lurn. L.
Eyler 1736- yilda bu masalaning yechimga ega emasligini isbotladi. U
graflar nazariyasining ancha umumiy hisoblangan quyidagi savoliga
ham javob topdi: qanday shartlar bajarilganda bog‘lamli grafda barcha
qirralardan faqat bir marta o'tadigan sikl mavjud bo‘ladi?
Grafning har bir qirrasidan faqat bir marta o‘tadigan zanjir Eyler zanjiri
deb ataladi. Yopiq Eyler zanjiriga (ya’ni Eyler sikliga) ega graf Eyler
grafi deb ataladi. Agar grafda yopiq bo’lmagan Eyler zanjiri topilsa, u
holda bunday graf yarim Eyler grafi deb ataladi.
Oriyentirlangan graflarda oriyentirlangan Eyler yo'lini izlash bilan
shug‘ullanish mumkin. Har bir yoydan faqat bir marta o ‘tadigan yo‘l
oriyentirlangan Eyler yo‘li deb ataladi. Tarkibida oriyentirlangan Eyler
yo‘li bor bo‘lgan oriyentirlangan graf oriyentirlangan Eyler grafi deb
ataladi.
Endi qirralari soni n ga teng bo'lgan berilgan Eyler grafida zanjirini tuzishning Flyori algoritmini keltiramiz. Bu
algoritmga ko‘ra grafning qirralari Eyler siklida uchrashi
tartibi bo‘yicha ldan n gacha raqamlab chiqiladi.
Flyori algoritmiga ko‘ra ish yuritish Eyler grafi uchun
doimo chekli jarayon ekanligi va bu jarayon doimo grafdan
barcha qirralarning olib tashlanishi, ya’ni Eyler zanjirini
tuzish bilan tugashi isbotlangan. Shuni ham ta’kidlash
kerakki, Flyori algoritmini qo‘llash jarayonida qirralami
tanlash imkoniyatlari ko‘p bo'lgani uchun, bunday
vaziyatlarda, algoritmni qo'llash mavjud Eyler sikllaridan
birini topish bilan cheklanadi. Tushunarliki, Flyori
algoritmini takror qo'llab (bunda qirralami tanlash jaroyoni
algoritmini avvalgi qo'llashlardagidek aynan
takrorlanmasligi kerak) grafda mavjud bo‘lgan barcha Eyler
sikllarini topish mumkin.

Berilgan grafga flyori algoritmini qo‘llab mavjud Eyler sikllaridan birini

aniqlaymiz. Dastlabki uch sifatida grafdagi 1 belgili uch olingan bo‘lsin. Bu
uchdan ikki yo‘nalishda: (1;2) qirra bo‘ylab yoki (1;4) qirra bo‘ylab 1-shakl
harakatlanish mumkin. Masalan, (1;2) qirra bo‘ylab harakatlanib 2 belgili
uchga o‘tamiz. Endi harakatni 3 yo‘nalishda: yo (2;3) qirra bo‘ylab, yo (2;4)
qirra bo‘ylab, yoki (2;5) qirra bo‘ylab davom ettirish mumkin. Aytaylik, (2;3)
qirra bo‘ylab harakatlanib 3 belgili uchga o‘tgan bo‘laylik. Shu usulda
davom etib mumkin bo‘lgan Eyler sikllaridan birini, masalan, quyidagi
siklni hosil qilamiz:
((1,2), (2,3), (3,5), (5,4), (4,6), (6,9), (9,8), (8,6), (6,5), (5,8), (8,7), (7,5), (5,2),
(2 ,4 ), (4,1)).
1- misol. 1- shaklda tasvirlangan grafni qaraymiz. Avvalo
bu grafning Eyler grafi bo'lishi shartini, ya’ni 1- teorema
shartlarining bajarilishini tekshiramiz

Marshrutlar va zanjirlar haqida umumiy ma’lumotlar. Uchlari

to‘plami V = {v1;v2,...,vm} va qirralar korteji U — {u1,u2,...,un} bo’lgan
oriyentirlanmagan G = (V,U) graf berilgan bo‘lsin. Bu G grafdagi uchlar
va qirralaming har ikki qo‘shni qirralari umumiy chetki uchga ega
(…,vi,ui,vi2,ui2,vi3,..)
ko'rinishidagi chekli yoki cheksiz ketma-ketligi marshrut deb ataladi.
Marshrutni uning uchlari ketma-ketligi (...,vj1,vj2,...) yoki qirralari
ketma-ketligi (…,uj1,uj2,...) ko‘rinishida ham belgilash mumkin
Agar marshrutda qandaydir uchdan oldin uchlar bo‘lmasa, bu uchni
marshrutning boshlang‘ich uchi deb, shu uchdan keyin marshrutga
tegishli uchlar bo‘lmaganda esa, uni marshrutning oxirgi uchi deb
ataydilar
Agar marshrutning boshlang‘ich uchi vp va oxirgi uchi vq bo‘lsa, u
holda uni vp uchdan vq uchga yo‘nalgan marshrut yoki chetlari vp va
vq bo‘lgan marshrut deb ataladi.

Marshrutdagi ikkita qoshni qirralarga tegishli uch ichki uch yoki oraliq uch

deb ataladi.
Marshrutda qirralar va uchlar takrorlanishi mumkin boMgani uchun
marshrutning ichki uchi, bir vaqtning o ‘zida, uning boshlang‘ich va (yoki)
oxirgi uchi bo‘lishi ham mumkin va teskarisi, marshrutning boshlang‘ich va
(yoki) oxirgi uchi uning ichki uchi bo‘lishi ham mumkin.
Tabiiyki, marshrut:
- boshlang‘ich uchga ham oxirgi uchga ham ega bo‘lmasligi mumkin (bunday
marshrut ikki tomonlama cheksiz marshrut deb ataladi);
boshlangich uchga ega bo‘lib, oxirgi uchga ega bo‘lmasligi mumkin yoki,
aksincha, oxirgi uchga ega bo'lib, boshlangich uchga ega bo‘lmasligi
mumkin (bir tomonlama cheksiz marshrut);
- yagona qirradan iborat bo‘lishi mumkin (notrivial marshrut);
birorta ham qirraga ega bo‘lmasligi mumkin (nol m arshrut yoki trivial
marshrut).
Marshrutning uzunligi deb undagi qirralar soniga aytiladi.
Turli qirralardan tashkil topgan marshrutga zanjir deb ataladi

Grafning bog‘lamliligi tushunchasi. Agar oriyentirlanmagan grafda

chetlari a va b uchlardan iborat marshrut topilsa, bu a va b uchlar
bog‘langan deb, marshrutning o‘zi esa a va b uchlarni bog‘lovchi
marshrut deb ataladi.
Tabiiyki, agar qandaydir uchlarni bog‘lovchi marshrut biror at
uchdan bir necha marta o‘tsa, u holda marshrutning siklik qismini
olib tashlab (bunda siklik qismning o‘rniga marshrutda faqat ai
uch qoldiriladi) yana o‘sha uchlarni bog‘lovchi oddiy zanjir
ko‘rinishdagi marshrutni hosil qilish mumkin. Shuning uchun,
marshrut bilan bog‘langan uchlar doimo oddiy zanjir bilan ham
bo'glangan bo‘ladi, degan xulosaga kelamiz.
Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari
bog‘langan graf bog‘lamli graf deb ataladi.

Xulosa
Ushbu mavzuda graflar haqida qisqa tarixiy ma’lumotlar,

grafning abstrakt matematik tushuncha sifatidagi ta’rifi va u bilan
bog‘liq boshlang‘ich tushunchalar, graflaming geometrik ravishda,
maxsus turdagi ko‘phad yordamida, qo'shnilik va insidentlik
matritsalari vositasida berilishi, graining elementlari ustida sodda
amallar, graflami birlashtirish, biriktirish va ko‘paytirish amallari,
marshrutlar va zanjirlar, grafning bog’lamliligi tushunchasi, Eyler
va Gamilton graflari, graflarda masofa tushunchasi, minimal
masofali yo‘l haqidagi masala, daraxt va unga ekvivalent
tushunchalar, grafning siklomatik soni, tarmoq tushunchasi,
tarmoqdagi oqimlar, maksimal oqim haqidagi masala va bu
masalalarni hal qilish uchun Ford algoritmi yoritiladi..

Foydalanilgan adabiyotlar

1. http://hozir.org
2. https://e-library.namdu.uz/22%20%D0%A4%D0%B8%D0%B7%D0%B8%D0%BA%D0%B0-%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0/Kombinatorika%20va%20graflar%20nazariyasi.To'rayev%20H.%20Azizov%20I.pdf
3. https://jdpu.uz/wp-content/uploads/2020/08/Kombinatorika-va-graflar-nazariyasi.-%D0%A2%D1%83%D1%80%D0%B0%D0%B5%D0%B2.pdf