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