מוגדר גרף לא מכוון "גרף־כמעט־עץ": גרף שקיימת בו קשת שהסרתה נותנת עץ (כלומר גרף קשיר עם קשת אחת בדיוק מעבר למספר קשתות של עץ).
סעיף א
סרטטו גרף שיש בו 6 קודקודים והוא "גרף־כמעט־עץ".
סעיף ב
נתון "גרף־כמעט־עץ" ובו n קודקודים.
סעיף ב(1)
האם אפשר לדעת את מספר הקשתות בגרף זה? נמקו את תשובתכם. אם עניתם שאפשר, ציינו את מספר הקשתות.
סעיף ב(2)
האם אפשר לדעת את מספר רכיבי הקשירות בגרף זה? נמקו את תשובתכם. אם עניתם שאפשר, ציינו את מספר רכיבי הקשירות.
סעיף ג
נתון גרף לא מכוון G ובו n קודקודים, המיוצג על ידי רשימת סמיכויות.
סעיף ג(1)
כתבו אלגוריתם יעיל המחזיר "אמת" אם הגרף הוא "גרף־כמעט־עץ" ואחרת הוא מחזיר "שקר".
סעיף ג(2)
מהי סיבוכיות זמן הריצה של האלגוריתם שכתבתם? נמקו את תשובתכם.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.