קוד פרופר

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
עץ ממוספר המתאים לקוד פרופר 4445

בתורת הגרפים, קוד פרווּפֵר (Prüfer Sequence) הוא התאמה בין קבוצת העצים הממוספרים בעלי n צמתים לבין אוסף הווקטורים באורך n-2 המורכבים ממספרים טבעיים בין 1 לבין n, באופן שמהווה מעין קידוד של המידע שדרוש כדי ליצור את הגרף. את הקידוד יצר המתמטיקאי הגרמני היינץ פרווּפֵר (1896-1934) ב-1918, וסיפק בכך את ההוכחה הקונסטרוקטיבית הראשונה למשפט של קיילי (1889) שלפיו מספר העצים הפורשים של הגרף השלם הוא .

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

תהליך הקידוד - מעבר מגרף לקוד[עריכת קוד מקור | עריכה]

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

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

בכל שלב:

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

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

תהליך החילוץ - מעבר מקוד לגרף[עריכת קוד מקור | עריכה]

מעבר מקוד פורפר "1344" לגרף עץ תואם

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

  1. נחפש את המספר המינימלי ברשימה (בפעם הראשונה - שאינו מופיע בוקטור הקוד), ונציב אותו כצומת בגרף.
  2. ניקח את הערך הראשון בוקטור ונציב כצומת בגרף
  3. נמתח קשת בין הצמתים שנוצרו בשני השלבים הקודמים
  4. נמחק את המספר מהווקטור ומהרשימה

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]