[-] question 2
by arditi - Sunday, 24 June 2012 12:09:59
IS (G,k) belong to VC when k=3 and G is a graph that has only one edge and its 2 vertexes ?
thread
[-] Re: question 2
by taig - Sunday, 24 June 2012 13:14:15
Yes, but you may assume for simplicity that |V|>=k
thread
[-] Re: question 2
by roykey - Sunday, 24 June 2012 18:54:09
לשם הבהרה קטנה, בדוגמא הנגדית בשאלה 2ב, ניתן לתת כדוגמא גרף שה-קיי שלו איננו מינימלי ביחס לגרף או שיש דרישה למינימליות ?
thread
Re: question 2
by taig - Sunday, 24 June 2012 20:28:24
Yes. You may - if you mean that there's a VC of size 2 and the input is for example <G,3> - Yes, you may.
thread