Daraxtlar va graflar

Graf — uchlar (tugunlar) va ularni bog‘lovchi qirralardan iborat tuzilma. Shaharlar va ular orasidagi yo‘llar, ijtimoiy tarmoqdagi do‘stlar, internetdagi sahifalar va havolalar graf bilan tasvirlanadi. Qirralar yo‘nalishli (bir tomonlama yo‘l) yoki yo‘nalishsiz bo‘lishi mumkin; qirraga son — masofa yoki narx — ham biriktirish mumkin. Uchning darajasi — unga tutashgan qirralar soni; har qanday yo‘nalishsiz grafda barcha darajalar yig‘indisi qirralar sonining ikkilanganiga teng.

Daraxt — sikl (yopiq yo‘l) bo‘lmagan bog‘lanishli graf. Unda bitta alohida uch — ildiz bor, qolgan har bir uchning bitta “ota”si bo‘ladi, farzandi yo‘q uchlar esa barg deyiladi. Daraxtga kompyuterdagi papkalar tuzilmasi, oilaviy shajara, mantiqiy tanlov sxemasi misol bo‘ladi. n ta uchli daraxtda doim aynan n − 1 ta qirra bo‘ladi.

Python’da grafni qo‘shni uchlar ro‘yxati bilan saqlash qulay: har bir uchga unga qo‘shni uchlar ro‘yxati mos qo‘yiladi. Masalan, lug‘at yaratib: g = dict(), so‘ng g["A"] = ["B", "C"], g["B"] = ["A", "D"], g["C"] = ["A"], g["D"] = ["B"]. Bunday yozuvda A uchining qo‘shnilari g["A"] da turibdi, uni topish juda oson va xotira kam sarflanadi.

Grafda eng ko‘p uchraydigan masala — uchlarni aylanib chiqish. Kenglik bo‘yicha qidirish boshlang‘ich uchdan boshlab avval uning barcha qo‘shnilarini, so‘ng ularning qo‘shnilarini ko‘radi (navbat yordamida); u qirralar soni eng kam bo‘lgan yo‘lni topadi. Chuqurlik bo‘yicha qidirish esa bir yo‘ldan imkon qadar uzoqqa boradi, keyin qaytadi (stek yoki rekursiya yordamida). Navigatsiya dasturlari, tavsiyalar tizimi va tarmoq yo‘nalishlari graf algoritmlariga asoslangan.

Asosiy xulosalar

Graf uchlar va qirralardan iborat; qirralar yo‘nalishli yoki yo‘nalishsiz bo‘lishi mumkin.
Daraxt — sikli yo‘q bog‘lanishli graf; n ta uchli daraxtda n − 1 ta qirra bo‘ladi.
Daraxtda ildiz, ota-farzand munosabati va barglar mavjud.
Grafni Python’da qo‘shni uchlar ro‘yxati bilan lug‘atda saqlash qulay.
Kenglik bo‘yicha qidirish eng qisqa (qirralar soni bo‘yicha) yo‘lni topadi.

Amaliy topshiriqlar

Ikki do‘stlik guruhi berilgan: A–B, A–C, B–C, D–E. Bu grafni chizing, har bir uchning darajasini toping va darajalar yig‘indisi qirralar sonining ikkilanganiga tengligini tekshiring.
Maktabingizning “direktor — o‘rinbosarlar — sinf rahbarlari” tuzilmasini daraxt sifatida chizing: ildizni, barglarni va daraxtdagi uchlar sonidan qirralar sonini toping.
Matndagi A, B, C, D uchli grafni Python’da lug‘at ko‘rinishida yozing va A uchining qo‘shnilarini chiqaruvchi qisqa dastur tuzing. Keyin A dan D gacha qirralari eng kam yo‘lni qo‘lda toping.

Mustahkamlash savollari

O‘zingizni sinab ko‘ring: avval o‘ylab ko‘ring, keyin javobni oching.

1Daraxt graflarning qanday xususiy holati?Javobni ko‘rish

Bog‘lanishli va sikli yo‘q graf; unda n ta uch uchun aynan n − 1 ta qirra bo‘ladi.

2Grafda eng kam qirrali yo‘lni qaysi qidirish usuli topadi?Javobni ko‘rish

Kenglik bo‘yicha qidirish: u uchlarni boshlang‘ich uchdan uzoqlik tartibida ko‘radi.

36 ta uchli daraxtda nechta qirra bor?Javobni ko‘rish

5 ta, chunki qirralar soni uchlar sonidan bitta kam.