11-маъруза Йўналтирил маган графлар

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.

yo’naltirilgan graflarda ilmoqli yoy bo’lishi mumkin, yo’naltirilmagan graflarda esa bunday yoy bo’lmaydi.

yo’naltirilgan graflarda ilmoqli yoy bo’lishi mumkin, yo’naltirilmagan graflarda esa bunday yoy bo’lmaydi.

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

Grafni ko’rikdan o’tkazish (Graph traversal) – bu berilgan tugundan boshlab barcha tugunlarni ko’rib chiqish prosedurasidir.

Ikkita usuli mavjud:

• Tubiga qarab(Depth-First Search – DFS)
• Eniga qarab(Breadth-First Search – BFS)