קוד פרופר

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

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

תהליך הקידוד - מעבר מגרף לקוד

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

בכל שלב:

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

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

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

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

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

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

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

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

קוד פרופר

תהליך הקידוד - מעבר מגרף לקוד

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

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

תפריט ניווט

חיפוש