Daraxt haqida tushuncha
Agar G grafda sikllar mavjud bo‘lmasa, u holda bunday graf - asiklik graf deyiladi. Asiklik grafda sikllar bo‘lmasligi, ya’ni sirtmoq, karrali qirralar bo‘lmasligi kerak.
Daraxt deb, bog‘langan asiklik G grafga aytiladi.
Sikllari mavjud bo‘lmagan bog‘lanmagan G graf, o‘rmon deyiladi.
O‘rmonning bog‘lovchi kompanentasi sifatida daraxt ishlatiladi. O‘rmonning yoki daraxtning ixtiyoriy šismi o‘rmon yoki daraxt bo‘lib, ular sikllarga ega emas. Bunday grafdagi ixtiyoriy zanjir oddiy zanjir bo‘ladi.
15.13-Teorema. Daraxtda ixtiyoriy ikkita ai va aj tugunlar bitta va faqat bita zanjir bilan bog‘langan.
15.10-Ta’rif. Agar G grafning ixtiyoriy ikkita tuguni faqat bitta zanjir bilan bog‘langan bo‘lsa, G graf daraxt deb ataladi.
Misollar. Yo‘naltirilmagan daraxt.
1) 2) 3)
4)
15.3-Misol. Yo‘naltirilgan daraxt.
1) 2)
3)
15.14-Teorema. G chekli daraxtda tugunlar soni r, qirralar soni q dan bitta ortiq, ya’ni p=q+1.
Aytaylik, a0 ildizli G daraxtning tuguni a berilgan bo‘lsin. V (a) - a tugundan o‘tuvchi va ildiz a0 bilan bog‘lovchi zanjirdagi tugunlar to‘plami bo‘lsin. Bu to‘plam G grafda G(a) graf ostini hosil qiladi.
Graf osti G(a) a0 ildizli daraxt G da a tugunning shaxobchasi deyiladi.
15.4-Misol.
Tugunlarning tipi. Aytaylik chekli G – daraxt berilgan bo‘lsin. Bu daraxtning chekka tugunlarini 1 tipli tugunlar deb ataymiz. Ta’kidlaymizki, agar daraxtning tugunlari soni 2 tadan ortiq bo‘lsa, u holda ular orasida chekka bo‘lmagan tugunlar mavjud bo‘ladi. Haqiqatdan ham, aytaylik a1 va a2 – G daraxtning chekka tugunlari bo‘lsin. U holda ular zanjir bilan bog‘langan bo‘lishi kerak. Agar bu zanjir faqat bitta qirradan iborat bo‘lsa, u holda a1 va a2 boshqa birorta ham tugun bilan bog‘lanmagan, bu esa daraxtning bog‘langanligiga ziddir. Agar bu zanjir 2 ta yoki ko‘proq širradan iborat bo‘lsa, u holda bu zanjir lokal darajasi 2 dan katta yoki teng bo‘lgan tugunlardan o‘tadi, ya’ni bu tugunlar chekka tugunlar emas .
G daraxtdan hamma 1 tipli tugunlarni va ularga qo‘shma bo‘lgan qirralarni tashlab yuboramiz. U holda sikllarsiz bog‘langan G| daraxt qoladi.
Haqiqatdan, ixtiyoriy a|, a|| G|| tugunlarni birlashtiruvchi zanjir L(a|,a||) G daraxtning chekka tugunlaridan o‘tmaydi, balkim to‘lig‘icha G| daraxtda yotadi. G| daraxt ham o‘z navbatida chekka tugunlarga ega bo‘ladi. Bu tugunlarni G daraxtdagi 2 tipli tugunlar deb ataymiz. Xuddi shu usul bilan 3, 4 va h.k tipli tugunlarni hosil qilamiz.
15.5-Misol.
a) G:
b)
v) g)
G| G|| G|||
Demak G daraxtning markazi 4 –tipli a1, a2 tugunlardan iborat
Ushbu daraxtning markazi 4-tipli a1, a2 tugunlardan iborat.
15.14-Teorema. G daraxtning markazi deb, eng katta K - tipga ega bo‘lgan tugunlarga aytiladi.
a| chetki bo‘lmasa, u holda undan yana bitta qirra chiqadi. Ushbu qirraning a|| tugunidan yana bitta qirra chiqadi va hokazo.
Daraxtda siklomatik son. Aytaylik G chekli yo‘naltirilmagan daraxt bo‘lsin. Uning siklomatik soni deb aytiladi. Bu yerda - grafning bog‘liqlik komponentalari soni; - grafning qirralar soni; - grafning tugunlari soni.
15.2-Tasdiq. G daraxtning siklomatik soni 0 (nol) ga teng.
15.3-Tasdiq. O‘rmonning siklomatik soni – bog‘langan daraxt komponentalarining yig‘indisi bo‘lib, u ham 0 (nol) ga teng.
15.4-Tasdiq. Qolgan chekli graflarning siklomatik soni musbatdir, ya’ni (G)>0.
15.7-Misol.
(G)=2+4-4=2>0;
15.8-Misol.
Ixtiyoriy ai va aj tugunlarni bog‘lovchi zanjir bitta.
Demak (G) = 1+6-7=7-7=0.
|
