Maksimal dəst#3411
Ömür boyu gözlədiyiniz gün gəlib çatdı: siz maksimal dəst məsələsini həll etmək üçün üsul icad etdiniz: istiqamətlənməmiş qraf verilib, qrafın təpə nöqtələrinin maksimum alt çoxluğunu tapmaq lazımdır ki, onlar cüt-cüt qoşulmuş və tam dəst təşkil etsin (və ya, başqa sözlərlə, ulduz təşkil edir). Bu məsələ NP-çətindir, amma sizdə sübut var ki, P = NP!
Təəssüf ki, elmi ictimaiyyət sizə eşitmək belə istəmir. Mövzu ilə bağlı təqdim etdiyiniz sənədlər "aydın şəkildə həll olunmayan problemin həlli yoxdur" səbəbi ilə rədd edilir. Tanıdığınız bütün kompüter elmi professorları artıq telefon nömrənizi siyahılarından çıxarıb. Sanki dünya sizə qarşıdır.
Beləliklə, maksimal dəst tapmaq üçün bir həll proqramı yaratmağa və onu internetə yerləşdirməyə qərar verdiniz ki, hər kəs sizin doğru olduğunuzu yoxlaya bilsin. Artıq proqramı yazmış və veb-saytı demək olar açmışdınız, amma sonra başa düşdünüz ki, bu, o qədər də yaxşı fikir deyil: çünki proqram əlçatan olsa, hər kəs NP sinfindən istənilən problemi maksimal dəst problemi kimi həll edə bilər. İnsanlar sadəcə səssizcə istifadə etsələr, şöhrət və hörmət əvəzinə sizə heç nə gətirməyə bilər.
Xoşbəxtlikdən, maksimal dəst probleminin NP-çətinliyinin sizə məlum olan yeganə sübutu, 3-SAT məsələsini ona kifayət qədər xüsusi şəkildə endirməklə əldə edilir. Buna görə siz qərara gəldiniz ki, daxil olan qraf bu reduksiyadan alınmış ola bilərmi, və əgər belədirsə, həmin problemi həll etməkdən imtina edəcəksiniz. Beləliklə, heç kim NP sinfindən bütün problemlərə tez həll tapmaz, amma başqaları sizin proqramınızı fərqli qraflarla asanlıqla yoxlaya bilər.
3-SAT probleminin şərti belədir: , burada hər termin t^i_j ya hansısa boolean dəyişəni, ya da onun inkarıdır (daha formal desək, x_k və ya \neg x_k). Soruşulur, elə true/false qiymətləri təyin etmək olarmı ki, ifadə doğru alınsın? Bir mötərizədəki bütün üç termin müxtəlif dəyişənlər olmalıdır.
Reduksiya belə işləyir: yuxarıdakı ifadədən təpədən ibarət bir qraf düzəldirik, hər biri hər mötərizədəki bir termə uyğun gəlir. t^i_j və t^r_s terminlərinə uyğun gələn iki təpə i \ne r olduqda (yəni fərqli mötərizədə) və aralarındakı terminlər ziddiyyət təşkil etmədikdə (ya eynidirlər, ya da fərqli dəyişənlərə malikdir) qoşulur.
Aşağıdakı şəkildə (x_1 x_2 x_3) (x_1 x_2 x_4) (x_1 x_2 x_4) üçün qraf göstərilmişdir:
Burada ölçüsü olan tam dəst, dəyişənlərə true/false qiymətlərini elə təyin etmək deməkdir ki, hər bir mötərizədə ən azı bir termin doğru olsun. Yuxarıdakı şəkildə seçilmiş kənarlar ölçülü tam dəst təşkil edir və x_1-ə false, x_2-yə true qiyməti verilməsi bütün mötərizələri ödəyir, x_3 və x_4-ün qiymətindən asılı olmayaraq.
Verilmiş qrafın yuxarıda təsvir edilən reduksiya ilə əldə olunan olub-olmadığını müəyyən edin. Təpə nömrələri istənilən sırayla verilə bilər.
Giriş faylının ilk sətrində qrafın təpələrinin (1 \leq v \leq 100) və kənarlarının və ədədləri verilir. Növbəti sətrin hər birində bir kənarı birləşdirən iki təpənin nömrəsi göstərilir. Hər bir cüt ən çox bir dəfə birləşdirilib, heç bir kənar özü ilə qovuşmur.
Əgər verilmiş qraf yuxarıda təsvir olunan reduksiya ilə əldə oluna bilərsə, "YES", əks halda isə "NO" çap edin.
Nümunə 1