O‘zbekiston respublikasi axborot te

Аsosiy tushunchalar va graf turlari.
Graf - bu murakkab chiziqsiz koʼpbogʼlamli dinamik tuzilma boʼlib, murakkab obʼektlarning 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.
Obʼektlar tugun yoki graf uzellari koʼrinishida va munosabatlar yoy yoki yoʼnaltirilgan qirralar kabi ifodalanadi. «Graf» tushunchasini 1-marta 1936 yil vengriya matematigi Denni Kyonig kiritgan. Lekin graflar nazariyasi boʼyicha 1-ish Leonard Eylerga tegishli boʼlgan va u 1736 yilda bajarilgan edi.tugundan boshqa bironta tugunga murojaat mavjud



Ixtiyoriy tugundan boshqa bironta tugunga murojaat mavjud boʼlsa, u xolda bunday graf yoʼnaltirilmagan graf deyiladi (1-rasm).
Аgar 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 xisoblanaadi. (i,j) qirraning ogʼirligi wij kabi belgilanadi.

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). Аgar grafda boshi va oxiri bitta tugunda tutashadigan qirra mavjud boʼlsa, unga ilmoqli qirra deyiladi.
Graflarni ifodalash usullari


Tugun(vertex, node)