O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti

13-ma’ruza. Yo’naltirilmagan graflar.

Minimal narxli daraxtlar skeleti.

Yo’nalishi aniqlanmagan daraxtlarni ko’ruvdan o’tkazish.

Reja

1. 
   Yo’naltirilmagan graflar.
   
2. 
   Yo’nalishi aniqlanmagan daraxtlarni ko’ruvdan o’tkazish algoritmi.
   
3. 
   Minimal narxli daraxtlar skeleti.
   

Yo’naltirilmagan graflar

Yo’naltirilmagan graf G=(V, E) – bu tugunlar va ularni birlashtirib turuvchi yoylar dan tashkil topgan tuzilma xisoblanadi. Undagi ixtiyoriy yoy teskarisi bilan teng va u yo’naltirilmagan yoy deyiladi. Agar bo’lsa, u xolda  u va v tugunlar qo’shni deyiladi va e yoy esa insident deyiladi. Tugunlarning chiqish darajasi deb u bilan qo’shni tugunlar soniga aytiladi. Chiqish darajasi 0 ga teng bo’lgan tugunlar izolyasiyalangan tugun deyiladi.

E’tibor qilish kerakki, yo’naltirilgan graflarda ilmoqli yoy bo’lishi mumkin, yo’naltirilmagan graflarda esa bunday yoy bo’lmaydi. Masalan, quyidagi rasmda yo’naltirilgan G₁=(V₁, E₁) grafda V₁={ a,b,c,d}tugunlar va E₁={ (a,b), (a,c), (b,b), (b,d), (d,a)} yoylar berilgan bo’lsin. Unda G₂=(V₂, E₂)yoy ilmoq xisoblanadi va uning kirish darajasi 2 ga, chiqish darajasi xam 2 ga teng. G₂ Grafda esa e tugunning darajasi 0 ga teng va izolyasiyalangan.


1-rasm. Yo’naltirilgan G1 va yo’naltirilmagan G2 graflar.