|
Mustaqil bajarish uchun masala va topshiriqlar
|
| bet | 2/4 | | Sana | 11.01.2024 | | Hajmi | 2,46 Mb. | | #134474 |
Bog'liq DISKRET2.Mustaqil bajarish uchun masala va topshiriqlar
2.1.Graflar ustida amallar
1) Grafni markazini toping.
2) Grafni diametrini toping.
3) Grafni radiusini toping.
4) Grafda Eyler sikli mavjudligini tekshiring.
5) Grafda Gamilton sikli mavjudligini tekshiring.
6) Grafni siklomatik sonini toping.
7) Grafni qirralar sonini tugunlarning lokal
darajalari va qo’shnilik matritsasi orqali aniqlang.
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.
|
| |
