Nizomiy nomidagi tdpu fizika-matematika fakulteti mi-303 guruh talabasi mahmudova barnoning algoritmlash va dasturlash fanidan mustaqil ta’limi

Nizomiy nomidagi tdpu fizika-matematika fakulteti mi-303 guruh talabasi mahmudova barnoning algoritmlash va dasturlash fanidan mustaqil ta’limi

1. Graflar nazaryasi. Graflarning tipik qo’llanilishi, terminologiyasi.
2. Qism graf, orientrlangan va orientrlanmagan graflar tushunchasi.
3. Graflar izomorfizmi.
Mavzu: Graflar bilan ishlovchi sodda algoritmlar.

REJA:
Grafik tasvirlar - tasvirlarning boshqa usullarga bog'liq bo'lgan turli tushunchalar mazmunini tasvirlashning qulay usulidir (masalan, Venn diagrammasi va boshqa mantiqiy tasvirlarning grafik illyustratsiyalaridir).
Graf - bu intuitiv ravishda doiralar va ularni bog'laydigan chiziqlar to'plami sifatida ko'rish mumkin bo'lgan tizim (grafikni aniqlashning geometrik usuli 1-rasmga qarang).
Doiralar grafik cho'qqilari, o'qlari bor chiziqlar yoylar, o'qlari bo'lmagan chiziqlar esa qirralar deb ataladi.
Graf - bu murakkab chiziqsiz ko‘pbog‘lamli dinamik tuzilma bo‘lib, murakkab obyektlarning xususiyatlari va munosabatlarini aks ettiradi.
Matematik nazariyada va informatikada graf — bu tugunlar(uchlar)dan iborat bo‘lgan bo‘sh bo‘lmagan to‘plam va tugunlarni birlashtiruvchi yoylar majmuidir.
Obyektlar tugun yoki graf uzellari ko‘rinishida va munosabatlar yoy yoki yo‘naltirilgan qirralar kabi ifodalanadi.
yoy
Cho’qqi
qirra
1-rasm.
Graf turlari
Ixtiyoriy tugundan boshqa bironta tugunga murojaat mavjud bo‘lsa, u xolda bunday graf yo‘naltirilmagan graf deyiladi (1-rasm).
Agar graf tugunlari o‘zaro bog‘langan bo‘lsa-yu, lekin bu yoylar orqali munosabat faqat bir tomonlama bo‘lsa, u xolda bunday graflar yo‘naltirilgan graflar deyiladi.
Og‘irlikka ega bo‘lgan graf (weighted graph) – bu qirralari (yoylari) og‘irliklari bilan berilgan graf xisoblanadi. (i,j) qirraning og‘irligi wij kabi belgilanadi.
Graflarni ifodalash usullari
Graflar nazariyasining ayrim bir belgilanishlari:
•G=(V, E), bu yerda G – graf, V – tugunlar, E – qirralar;
• |V| – tugunlar soni;
•|E| – graf o‘lchami (qirralar soni).
Agar grafda boshi va oxiri bitta tugunda tutashadigan qirra mavjud bo‘lsa, unga ilmoqli qirra deyiladi.
Xalqa(cycle) – bu boshi va oxiri tutashuvchi tugundan iborat yo‘l xisoblanadi: (4, 6, 7, 8, 3, 4)
Tugun darajasi
(vertex degree) –
bu undan chiquvchi yoylar soni xisoblanadi.
deg(7) = 2, deg(1) = 3
Teorema: G(V, E) GRAFDA UNING BARChA TUGUNLARI DARAJALARI YIG‘INDISI – JUFT , GRAFNING QIRRALARI SONINING IKKILANGANIGA TENG.
TUGUNLAR JUFT(TOQ) DEYILADI, AGAR ULARNING DARAJALARI – JUFT(TOQ) QIYMATLI BO‘LSA.
Teorema: IXTIYoRIY GRAFDA TOQ TUGUNLAR SONI – JUFT BO‘LADI
Toq sonli toq tugunlardan iborat grafni chizib bo‘lmaydi.
To‘liq graf (complete graph) – bu istalgan tugunlari qo‘shni bo‘lgan graf xisoblanadi. (barcha tugunlar o‘zaro birlashtirilgan)
Grafni to‘ldiruvchisi bu aynan bir tugunlar va aynan bir qirralardan tashkil topgan va mavjud grafni to‘liq bo‘lishini ta’minlovchi grafga aytiladi.
A
B
C
D
A
B
C
D
A
B
C
D
To‘liq, yo‘naltirilmagan grafda qirralar soni:
D grafning to‘yinganligi (density):
To‘yingan graf (dense graph) – bu qirralar soni bo‘lishi mumkin bo‘lgan maksimalga teng bo‘lgan graf xisoblanadi. (D>0.5)
Siyrak raf (sparse graph) – bu qirralari soni tugunlar soniga yaqin bo‘lgan grafdir. (D<0.5)