קוד פרופר

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

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

פעולת הקוד[עריכת קוד מקור | עריכה]

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

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

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

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

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

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