Ommaviy pastki grafik asl grafikning barcha uchlarini oʻz ichiga olgan pastki grafik. Yopuvchi daraxt - bu ko'pincha qiziqish uyg'otadigan kengaytmali subgraf. Grafikdagi barcha cho'qqilarni o'z ichiga olgan sikl kengaytmali sikl deb ataladi.
Qancha kengaytmali subgraflar bor?
2n ta induktsiyalangan subgraflar (barcha choʻqqilar toʻplami) va 2m ni qamrab oluvchi subgraflar (qirralarning barcha kichik toʻplamlari).
Qanday qilib kengaytmali subgrafni topaman?
Va Grafikning Spanning subgrafi taʼrifiga koʻra G bu kichik grafigi faqat chetini oʻchirish orqali olingan. Agar biz bir chekka, ikkita chekka, uchta chekka va hokazolarni o'chirish orqali qirralarning pastki to'plamlarini qilsak. m chekka bo'lgani uchun 2 ^ m pastki to'plamlar mavjud. Demak, G ning 2^m boʻlgan pastki grafiklari bor.
Daraxt deganda nima tushuniladi?
Grafikning kengayuvchi daraxti (G) bu G ning kichik toʻplami boʻlib, uning barcha choʻqqilarini minimal chekka sonidan foydalangan holda qamrab oladi. Ushbu ta'rifdan yoyilgan daraxtning ba'zi xossalarini chiqarish mumkin: "Qo'yilgan daraxt barcha cho'qqilarni qamrab olgani uchun" uni uzib bo'lmaydi.
Ommaviy grafik nazariyasi nima?
Koʻlamli daraxt G grafikining kichik toʻplami boʻlib, uning barcha uchlari minimal mumkin boʻlgan qirralar soni bilan qoplangan. Demak, kengayuvchi daraxtda sikllar yo‘q va uni uzib bo‘lmaydi. Ushbu ta’rifdan kelib chiqib, har bir bog‘langan va yo‘n altirilmagan G grafikida kamida bitta kengayuvchi daraxt bor degan xulosaga kelishimiz mumkin.
