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

קליק בגרף לא מכוון הוא קבוצת קודקודים שכל שני קודקודים שונים בה מחוברים בקשת. גרף הוא איחוד זר של קליקים אם ניתן לחלק את קודקודיו לקבוצות שכל אחת מהן קליק, ואין קשתות בין קודקודים מקבוצות שונות.

1. הוכיחו כי גרף הוא איחוד זר של קליקים אם ורק אם אין בו שלושה קודקודים $x,y,z$ כך ש-$y$ מחובר ל-$x$ ול-$z$, אך $x,z$ אינם מחוברים.
2. בבעיית המינימיזציה, בהינתן $G$, המטרה היא למצוא קבוצת קודקודים קטנה ככל האפשר שהסרתה תיתן איחוד זר של קליקים. הוכיחו שקיים אלגוריתם פולינומי בעל יחס קירוב $3$.
3. בבעיית ההכרעה, בהינתן $G$, יש לקבוע אם ניתן לחלק את קודקודיו לשלוש קבוצות שכל אחת מהן קליק. הוכיחו כי הבעיה $NP$-שלמה. שימו לב שאין דרישה לאיחוד זר של קליקים.