קוד פרופר

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

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

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

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

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

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

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

קישורים חיצוניים

 תהליך הקידוד - הסבר ודוגמאות


קטגוריה:קומבינטוריקה
קטגוריה:תורת הגרפים