|
עוד שאלה ממבחן, לגבי Max-3-Cut..
DrgnsMstr
(אוניברסיטת ת"א)
|
|
29.06.2006 13:21
|
|
תגידו, למה Max-3-Cut ב- NPC? ברור למה זה ב-NP אבל קשה לנו למצוא משהו לעשות ממנו רדוקציה לבעיה הזו - אז אני משער שאתם תדעו (MC לא יודע כי הוא אפס).
בכל מקרה - אם שכחתם, אז Max-3-Cut זו הבעיה הבאה - מקבלים מולטי גרף (גרף שאפשר בו קשתות מקבילות) ומספר k ושואלים האם קיימת חלוקה של הצמתים ל-3 קבוצות כך שמספר הקשתות בין הקבוצות הוא לפחות k?
תודה רבה =) אני יודע שעשינו את זה אתמול בכיתה אבל.. אנחנו אווזים :)
|
|
|
