נוסחת קיילי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט מוסיף: uk:Формула Келі (теорія графів) |
מאין תקציר עריכה |
||
שורה 28:
נשים לב שהדרגה של כל צומת בעץ שווה למספר הפעמים שהצומת מופיע בקוד פרופר ועוד אחד. מכאן על מנת לייצר עץ מתוך קוד נתון, נתחיל בכך שנחשב באופן זה את הדרגה של כל צומת. עתה נבדוק מבין כל הצמתים בעלי דרגה 1 מהו הצומת בעל המספר הקטן ביותר. האות הראשונה בקוד פרופר מציינת קשת בין צומת זה לבין המספר הראשון בקוד. באופן זה ממשיכים את התהליך עד אשר מייצרים את העץ המתאים לקוד.
מכאן שיש [[איזומורפיזם (מתמטיקה)|איזומורפיזם]] בין עצים בעלי n קודקודים למילים המכילות n-2 אותיות מתוך n אותיות אפשריות. מספר המילים הללו הוא <math>\ n^{n-2}</math>, ומכאן נובעת נוסחת קיילי.
[[קטגוריה: תורת הגרפים]]
| |||