שאלה 6 במסלול אלגוריתמים. מוגדר גרף לא מכוון "גרף־כמעט־עץ": גרף שקיימת בו קשת שהסרתה נותנת עץ (כלומר גרף קשיר עם קשת אחת בדיוק מעבר למספר קשתות של עץ). בסעיף א מסרטטים דוגמה; בסעיף ב בודקים אילו תכונות (מספר קשתות, מספר רכיבי קשירות) ניתן לדעת מתוך ההגדרה בלבד; בסעיף ג בונים אלגוריתם יעיל לזיהוי התכונה ומנתחים את סיבוכיותו.

סרטטו גרף שיש בו 6 קודקודים והוא "גרף־כמעט־עץ".

נתון "גרף־כמעט־עץ" ובו n קודקודים.

האם אפשר לדעת את מספר הקשתות בגרף זה? נמקו את תשובתכם. אם עניתם שאפשר, ציינו את מספר הקשתות.

האם אפשר לדעת את מספר רכיבי הקשירות בגרף זה? נמקו את תשובתכם. אם עניתם שאפשר, ציינו את מספר רכיבי הקשירות.

נתון גרף לא מכוון G ובו n קודקודים, המיוצג על ידי רשימת סמיכויות.

כתבו אלגוריתם יעיל המחזיר "אמת" אם הגרף הוא "גרף־כמעט־עץ" ואחרת הוא מחזיר "שקר".

מהי סיבוכיות זמן הריצה של האלגוריתם שכתבתם? נמקו את תשובתכם.