לשרטט את העץ המתוייג לפי סדרת פרופר (Prufer)

שלום לכולם,
אני קצת מסתבך עם שאלות לגבי קוד פרופר (נקרא גם סדרת פרופר).

ההגדרה: בתורת הגרפים, קוד פרופר (Prüfer Sequence) הוא התאמה בין קבוצת העצים הממוספרים בעלי n צמתים לבין אוסף הווקטורים באורך n-2 המורכבים ממספרים טבעיים בין 1 לבין n, באופן שמהווה מעין קידוד של המידע שדרוש כדי ליצור את הגרף.

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

א. מהי הסדרה ע"פ קוד פרופר שמתאימה לעץ המתויג הבא:

proper1

ב. שחזרו את העץ המתויג מהסדרה הבאה: (5,5,5,1,1).

תודה רבה על כל העזרה! :slight_smile:

כדי לפתור את שני הסעיפים נפעל לפי שני אגלוריתמים. הראשון הוא תהליך הקידוד - מעבר מגרף לקוד והשני הוא תהליך החילוץ - מעבר מקוד לגרף.

א. תהליך הקידוד - מעבר מגרף לקוד: בהינתן עץ T כלשהו וצומת v כלשהו בתוכו נסמן ב- T-v את העץ המתקבל על ידי הסרת הצומת v וכל הצלעות המחוברות אליו. סימון זה יאפשר להגדיר רקורסיבית את פעולת הקוד. בכל שלב:

  • נבחר את העלה (צומת בעץ המחובר לצומת אחד בלבד, כלומר צומת בעל דרגה 1) שמספרו הוא מינימלי.
  • נרשום, במקום הבא בוקטור הקוד, את מספרו של הצומת היחיד שמחובר אליו.
  • נמחק את העלה מהעץ.

לאחר המחיקה נוצר עץ חדש T-v עם מספר צמתים קטן באחד מהעץ המקורי, עליו נפעיל שוב את התהליך. התהליך יסתיים כאשר יישארו שני עלים המחוברים אחד לשני. היות שאורך הקוד שווה למספר צמתים שהוסרו - אורך הקוד הוא בעל n-2 איברים.

האלגוריתם קצת מסובך להבין בפעם הראשונה אבל לאחר מספר דוגמאות הוא יראה פשוט. נבנה את הסדרה ע"פ קוד פרופר שמתאימה לעץ המתויג הנתון בסעיף הראשון. נתאר את שלבי בניית הקוד, כשבכל פעם נסיר את העלה בעל הערך המינימלי ונוסיף את שכנו בעץ לסדרה. נשים לב כי יש 7 צמתים ולכן הסדרה באורך 7-2=5.

  • העלה בעל הערך המינימלי הוא 1, לכן נסיר אותו ונוסיף את שכנו לסדרה: (6,\_,\_,\_,\_)
  • העלה בעל הערך המינימלי הוא 3, לכן נסיר אותו ונוסיף את שכנו לסדרה: (6,2,\_,\_,\_)
  • העלה בעל הערך המינימלי הוא 4, לכן נסיר אותו ונוסיף את שכנו לסדרה: (6,2,2,\_,\_)
  • העלה בעל הערך המינימלי הוא 4, לכן נסיר אותו ונוסיף את שכנו לסדרה: (6,2,2,\_,\_)
  • העלה בעל הערך המינימלי הוא 5, לכן נסיר אותו ונוסיף את שכנו לסדרה: (6,2,2,2,\_)
  • העלה בעל הערך המינימלי הוא 2, לכן נסיר אותו ונוסיף את שכנו לסדרה: (6,2,2,2,6)

לכן הסדרה המתאימה לעץ המתויג היא (6,2,2,2,6).

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

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

כך נמשיך ברקורסיה, לאחר n-2 שלבים ישארו ברשימה שני מספרים והווקטור יהיה ריק. נחבר את שני הצמתים האלו בקשת.

שוב, האלגוריתם עלול להיראות מפחיד בפעם הראשונה אבל לאחר מספר ניסיונות זה יראה פחות קשה. נשחזר את העץ מהקוד הנתון (5,5,5,1,1). נגדיר קבוצה A להיות קבוצת הקודקודים שטרם טופלו וקבוצה B להיות סדרת הקודקודים שתייצג את הקוד. בכל שלב נוסיף צלע בין הקודקוד בעל הערך המינימלי מ-A שאינו מופיע ב-B והקדקוד הראשון ב-B, ונסיר את שני הקודקודים מ-A ו-B בהתאמה. לבסוף נוסיף צלע בין שני הקודקודים שנשארו ב-A.

  • שלב התחלתי מתקיים:
A=\{1,2,3,4,5,6,7\},\,B=(5,5,5,1,1)
  • נוסיף צלע בין הקודקוד בעל הערך המינימלי ב-A, שלא מופיע ב-B (שזה 2), לבין הקודקוד הראשון ב-B (שזה 5). כמו כן, נסיר את שני הקודקודים (2 מ-A ו-5 מ-B) כך שסה"כ נקבל:
A=\{1,3,4,5,6,7\},\,B=(5,5,1,1)
  • נוסיף צלע בין הקודקוד בעל הערך המינימלי ב-A, שלא מופיע ב-B (שזה 3), לבין הקודקוד הראשון ב-B (שזה 5). כמו כן, נסיר את שני הקודקודים (3 מ-A ו-5 מ-B) כך שסה"כ נקבל:
A=\{1,4,5,6,7\},\,B=(5,1,1)
  • נוסיף צלע בין הקודקוד בעל הערך המינימלי ב-A, שלא מופיע ב-B (שזה 4), לבין הקודקוד הראשון ב-B (שזה 5). כמו כן, נסיר את שני הקודקודים (4 מ-A ו-5 מ-B) כך שסה"כ נקבל:
A=\{1,5,6,7\},\,B=(1,1)
  • נוסיף צלע בין הקודקוד בעל הערך המינימלי ב-A, שלא מופיע ב-B (שזה 5), לבין הקודקוד הראשון ב-B (שזה 1). כמו כן, נסיר את שני הקודקודים (5 מ-A ו-1 מ-B) כך שסה"כ נקבל:
A=\{1,6,7\},\,B=(1)
  • נוסיף צלע בין הקודקוד בעל הערך המינימלי ב-A, שלא מופיע ב-B (שזה 6), לבין הקודקוד הראשון ב-B (שזה 1). כמו כן, נסיר את שני הקודקודים (6 מ-A ו-1 מ-B) כך שסה"כ נקבל:
A=\{1,7\},\,B=()
  • נוסיף צלע בין שני הקודקודים שנשארו ב-A=\{1,7\}.

סה"כ נקבל את העץ הבא:

מקווה שמובן, בהצלחה :slight_smile: