נוסחת קיילי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט: החלפת תגית ref בתבנית הערה |
|||
שורה 9:
[[קובץ:The graph K5.jpeg|שמאל|ממוזער|250px|גרף שלם בעל 5 קודקודים]]
[[גרף שלם]] הינו גרף שבו צומת מחובר בקשת לכל אחת מהצמתים האחרים. באיור ניתן לראות גרף שלם בעל 5
[[עץ (תורת הגרפים)|עץ]] הינו גרף שבו קיים מסלול אחד בלבד המחבר כל שני צמתים.
שורה 28:
הוכחה זו התגלתה על ידי היינץ פרופר בשנת [[1918]]. ההוכחה מבוססת על [[קוד פרופר]]. קוד פרופר הוא מילה המציינת מבנה של עץ ובכך מראה [[התאמה חד חד ערכית]] בין העצים הפורשים של גרף שלם לבין המילים באורך n-2 מעל אלפבית של n אותיות אפשריות.
בהינתן עץ עם <math>n</math>
כעת נראה שיש גם התאמה מכל מילה באורך <math>n-2</math> אותיות מעל אלפבית בגודל n לעץ פורש בעל n
נשים לב שהדרגה של כל צומת בעץ שווה למספר הפעמים שהצומת מופיע בקוד פרופר ועוד אחד. מכאן על מנת לייצר עץ מתוך מילה נתונה, נתחיל בכך שנחשב באופן זה את הדרגה של כל צומת. עתה נבדוק מבין כל הצמתים בעלי דרגה 1, דהיינו אלה שכלל לא הופיעו במילה, מהו הצומת
מכאן שיש [[התאמה חד חד ערכית]] בין עצים בעלי n קודקודים למילים המכילות n-2 אותיות מתוך n אותיות אפשריות. מספר המילים הללו הוא <math>\ n^{n-2}</math>, ומכאן נובעת נוסחת קיילי.
שורה 40:
הוכחה זו משתמשת בטכניקה הנקראת "[[ספירה כפולה]]" בה סופרים גודל מסוים בשתי דרכים, ועל ידי השוואה ביניהן מקבלים את הגודל הדרוש. נסמן את מספר העצים הפורשים ב-C<sub>n</sub>. כעת נגדיר מספר מושגים:
* '''עץ מושרש''' - עץ [[גרף מכוון|מכוון]] כך שאחד
* '''יער מושרש''' - [[איחוד זר]] של עצים מושרשים.
כעת נספור בשתי דרכים את התשובה לשאלה הבאה: בכמה דרכים ניתן להגיע מיער מושרש שבו עץ אחד ליער מושרש שבו n עצים (כל אחד מהם בין
* '''דרך ראשונה''' - מהסרת קשת מיער מושרש תמיד מקבלים יער מושרש, כי קיבלנו שני עצים חדשים: זה שהיה בו את השורש נשאר עץ, ובשני
* '''דרך שנייה''' - הפעם נלך בכיוון ההפוך: נתחיל מיער עם n עצים ובכל שלב נוסיף קשת עד שנגיע ליער עם עץ אחד. לצורך כך נשים לב שהוספת קשת ליער מושרש הופכת ליער מושרש רק אם אנחנו מחברים
:<math>\prod_{k=2}^{n} n(k-1) = n^{n-1} (n-1)! = n^{n-2} n!</math>
ציינו שתי דרכים לספור את אותו דבר, לכן אפשר להשוות ביניהן ולקבל:
|