![[-]](/~lab/course.wiki/images/button-minus.gif)
לגבי שאלה 2
by gonengut - Wednesday, 27 June 2012 03:02:36
האם ניתן להניח שהגרף קשיר?חשבתי שהבנתי את הרדוקציה שאליה אתם מכוונים, אבל היא לא עובדת לי על הגרף הבא:o-----o o(קודקוד בודד ושני קודקודים מחוברים)כאשר קיי הוא 1. יוצא לי שהיא לא ב-ורטקס קאבר, אבל אחרי הרדוקציה אני מקבל שהגרף החדש כן שייך לשולה המוקשים.מצד שני יכול להיות שאני פשוט לא בכיוון, אז אם אי אפשר להניח אני אמשיך לנסות...
Re: לגבי שאלה 2
by taig - Wednesday, 27 June 2012 11:10:59
The graph you gave has a vertex cover of size 1. Please read again the definition of vertex cover, it depends only in the edges.