נתאר את בעיית האופטימיזציה הבאה: קלט: גרף פשוט מכוון G=(V,E). פלט: קבוצת קשתות E' E גדולה ככל האפשר, כך שהגרף…

נתאר את בעיית האופטימיזציה הבאה:

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

1. נתבונן בקבוצות הקשתות $$E_1=\{(i,j)\mid i<j\}, \qquad E_2=\{(i,j)\mid i>j\}.$$ הוכיחו כי הגרפים $G_1=(V,E_1)$ ו-$G_2=(V,E_2)$ חסרי מעגלים.
2. תארו אלגוריתם קירוב לבעיית האופטימיזציה שלעיל בעל יחס קירוב $1/2$, והוכיחו שהוא מקיים את כל הדרישות.
3. הוכיחו כי יחס הקירוב הדוק: הראו גרף שעליו האלגוריתם שכתבתם יחזיר קבוצת קשתות שגודלה בדיוק מחצית מגודלה של הקבוצה המקסימלית.