מה ההבדל בין יער ליער פורש בתורת הגרפים?


תשובה 1:

"יער" הוא כל אוסף עצים.

"יער פורש" הוא אוסף עצים הכולל ("טווח" או "כיסוי") כל קודקוד בתרשים. ישנם שני פרשנויות מתחרות:

  • "יער פורש מלא" או "יער פורש מרבי": כל רכיב מחובר בגרף מכוסה על ידי עץ פורש. כלומר ישנם עצים רבים ככל שישנם רכיבים מחוברים, ולא יותר. או כל אוסף עצים המכסה את הקודקודים, גם אם אוסף עצים קטן יותר היה עושה זאת. יתכנו יותר עצים מאשר ישנם רכיבים מחוברים.

לדוגמה, שקול גרף זה:

להלן יער בתרשים (צמתים ושוליים ירוקים), המורכב משני עצים אך משמיט חלק מקודקודיהם.

להלן יער פורש (כל הקודקודים) שיש בו עץ אחד לכל רכיב מחובר, "יער פורש מלא".

הנה יער פורש שונה שמשתמש במקום בשלושה עצים בכדי לכסות את כל הקודקודים: