Mavzu: Graf tushunchasi va uning ko’rinishlari. Graflarni tasvirlash usullari. Eng qisqa yolni to’pish algoritmi. Graf

Graf turlari
Tarif:Ixtiyoriy tugundan boshqa bironta tugunga murojaat mavjud boʻlsa, u xolda bunday graf yoʻnaltirilmagan graf deyiladi (1-rasm).
Tarif: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.



Graflar nazariyasining ayrim bir belgilanishlari:
• bu erda – graf, – tugunlar, – qirralar;
• - tugunlarisoni;
• – graf oʻlchami (qirralar soni).
Tarif: Agar grafda boshi va ohiri bitta tugunda tutashadigan qirra mavjud bo’lsa,u qirraga ilmoqli (sirtmoq) qirra deyiladi.



(1.2rasm)
Izox: (1.2) rasmda ko;rsatigan raqamlar bular graf uchlari hisoblanadi.
1-uch va 4-uch orasi qirra hisoblanadi…
4-uch va 6-uch o’zaro qo’shni…(1,4),(4,6) va hakoza.
(10,8),(8,3),(3,5) bular yo’l hisoblanadi.


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 tugunlari 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.

To’liq,yo’naltirilmagan grafda qirralar soni

D grafning toʻyinganligi (density):