Bajaruvchi: Bekmatov e tekshiruvchi: Axmedov f samarqand-2022 5-mavzu. P, Np, np-to’liq masalalar

Mustaqil yechish uchun masalalar

Quyidagi grafdan foydalanib, 1-uchdan 6-uchgacha eng yaqin masofa va yo’nalishni aniqlash dasturini Prim, Xoffman va Kraskal algoritmlaridan foydalanib dastur tuzing va natijalarni taqqoslab tahlil qiling

Mavzu: Graf erkin uchlarini ajratish masalasi
Ishning maqsadi: Grafning erkin uchlarini ajratish masalaasiga namunalar ko’rish va graflarga doir masalalar yechish
Kerakli jihozlar: Kompyuter, proyektor, doska, C++ dasturlash tili
Grafikdagi cho'qqilar to'plami, agar bu to'plamning ikkita uchi bir chekka bilan bog'lanmagan bo'lsa, mustaqil deyiladi. Boshqacha qilib aytadigan bo'lsak, ushbu to'plam tomonidan induktsiya qilingan pastki grafik izolyatsiya qilingan tepalardan iborat. Shuningdek, ba'zida grafikning har bir chekkasi mustaqil to'plamning ko'pi bilan bitta cho'qqisiga to'g'ri keladi, deb ham aytiladi. Tanib olish masalasi (hal qilish masalasi) quyidagicha ko'rinadi: berilgan G grafigi k o'lchamdagi mustaqil to'plamga egami?
Unga mos keladigan optimallashtirish masalasi mustaqil to'plam masalasi deb ham ataladi, quyidagicha tuzilgan: berilgan G grafigida maksimal o'lchamdagi mustaqil to'plamni topish talab qilinadi. Bu o'lcham mustaqillik soni, ichki zichlik soni yoki bo'shlik deb ataladi va a (G) bilan belgilanadi.

1-rasm. 9 ta ko'k burchakning mustaqil to'plami
Bu masala ba'zan eng katta mustaqil to'plamni topish deb ataladi. Ushbu kontseptsiyani maksimal mustaqil to'plam yoki qo'shilish orqali maksimal mustaqil to'plam bilan aralashtirib yubormaslik kerak, bu shunday mustaqil cho'qqilar to'plami sifatida belgilanadiki, unga asl grafikning yana bitta (har qanday) cho'qqisi qo'shilsa, u to'xtaydi. mustaqil bo'ling (umuman aytganda, bunday to'plamlar bir nechta va turli o'lchamdagi bo'lishi mumkin). Inklyuziya-maksimal mustaqil to'plam har doim ham eng katta emas. Shu bilan birga, har bir eng katta mustaqil to'plam, ta'rifiga ko'ra, qo'shilish bo'yicha ham maksimaldir. Qo'shilish bo'yicha (ba'zi) maksimal mustaqil to'plamni topish uchun polinom vaqtida ishlaydigan ochko'z algoritmdan foydalanish mumkin, eng katta mustaqil to'plam masalasi esa NP-to'liq masalalar sinfiga tegishli.

Optimal quyistruktura masalasi

Daraxtning tuzilishi bu masalani hal qilishni taklif qiladi. Ya'ni, har qanday cho'qqini daraxtning ildizi sifatida belgilaymiz va uni r deb ataymiz. U(r) da ildiz otgan pastki daraxtning eng katta mustaqil choʻqqilar toʻplamining oʻlchamini bildirsin. U holda masalaning javobi I(r).
Ko’rinib turibdiki, agar u cho'qqini eng katta mustaqil to'plamga kiritsak, u holda uning asosiyligi 1 ga ortadi, lekin biz uning bolalarini ololmaymiz (chunki ular u cho'qqi bilan chekka bilan bog'langan); agar biz bu cho'qqini kiritmasak, u holda eng katta mustaqil to'plamning kardinalligi ushbu cho'qqining mustaqil to'plamlari o'lchamlari yig'indisiga teng bo'ladi. Masalani hal qilish uchun ushbu ikkita variantdan maksimalini tanlash qoladi:

bu yerda grandchild cho‘qqining istalgan “nabirasi”ni, child esa cho‘qqining har qanday avlodini bildiradi.
function get_independent_set(Node u)
{
Agar I(u) allaqachon hisoblangan, keyin I(r) ni qaytaring
// to'plamning aniqligi, agar u uchini olmasak, olinishi mumkin children_sum = 0
grandchildren_sum = 0
// barcha child uchun sikl
for i := 1 to child_num do
children_sum = children_sum + get_independent_set(children[i])
// barcha nabiralar uchun sikl
for i:= 1 to grandchildren_num
grandchildren_sum = grandchildren_sum + get_independent_set(grandchildren[i])
// qayta hisoblamaslik uchun eslab qoling
I(u) = max(1 + grandchildren_sum, children_sum)
возвратить I(u)
}