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

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

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

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

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

(1) כתבו אלגוריתם יעיל המחזיר "אמת" אם הגרף הוא גרף־כמעט־עץגרף־כמעט־עץגרף לא מכוון נקרא "גרף־כמעט־עץ" אם קיימת בו קשת שכאשר מורידים אותה מקבלים עץ. ואחרת הוא מחזיר "שקר".

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