נקרא לגרף צנוע אם הדרגה המקסימלית שלו היא לכל היותר 1. 1. הוכיחו כי בעיית ההכרעה הבאה היא…

שאלה פתוחהq-742dce80700b

נוסח השאלה

נקרא לגרף צנוע אם הדרגה המקסימלית שלו היא לכל היותר $1$ .

הוכיחו כי בעיית ההכרעה הבאה היא $NP$ -שלמה:

קלט: גרף פשוט לא מכוון $G=(V,E)$ ומספר טבעי $k$ .
שאלה: האם ניתן להסיר לכל היותר $k$ קודקודים כך שהגרף הנותר יהיה צנוע?

רמז: בצעו רדוקציה מ- $VC$ והוסיפו עלה לכל קודקוד.
בגרסת המינימיזציה יש להסיר מספר מינימלי של קודקודים כדי לקבל גרף צנוע. תנו אלגוריתם פולינומי בעל יחס קירוב $3$ והוכיחו את יחס הקירוב.

נוסח מטלה שנבדק אנושית.

Exact provenance

Each card is a genuinely distinct file. Printed versions inside one PDF stay in that card and do not inflate the sitting count.

Assignment

2025_03_תרגיל_3.md

Question 5Page 1Human reviewed