נוסחת קיילי

רשימה מלאה של העצים המסומנים על 3,2 ו-4 צמתים

נוסחת קיילי היא נוסחה בתורת הגרפים הקובעת שמספר העצים הפורשים של גרף שלם בעל n צמתים הוא $\ n^{n-2}$. בניסוח אחר ניתן לומר שמספר העצים המחברים n צמתים מסומנים הוא $\ n^{n-2}$. הנוסחה נקראת על שמו של המתמטיקאי הבריטי ארתור קיילי, וניתן לראות אותה כמקרה פרטי של משפט קירכהוף, המאפיין את מספר העצים הפורשים בגרף כלשהו.

הנוסחה הוכחה לראשונה על ידי המתמטיקאי הגרמני קרל בורכרט ב-1860, על ידי שימוש בדטרמיננטות. היא הוכללה על ידי קיילי ב-1889, ואף שהלה התייחס במפורש לבורכרט שמו נדבק לנוסחה.

מושגי יסוד

בתורת הגרפים גרף הוא אוסף של צמתים ושל קשתות המחברות בין הצמתים.

גרף שלם בעל 5 קודקודים

גרף שלם הוא גרף שבו צומת מחובר בקשת לכל אחת מהצמתים האחרים. באיור ניתן לראות גרף שלם בעל 5 צמתים.

עץ הוא גרף שבו קיים מסלול אחד בלבד המחבר כל שני צמתים.

עץ פורש הוא תת גרף שהוא עץ המכיל את כל הצמתים של הגרף המקורי.

דרגה של צומת - מספר הקשתות המחוברות לאותו צומת.

עלה הוא צומת בעץ המחובר לצומת אחד בלבד, כלומר צומת בעל דרגה 1.

הוכחת משפט קיילי

עץ ממוספר המתאים לקוד פרופר 4445

למשפט קיילי מספר הוכחות, נביא כאן שתיים מהן.

בניית פרופר

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

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

כעת נראה שיש גם התאמה מכל מילה באורך $n-2$ אותיות מעל אלפבית בגודל n לעץ פורש בעל n קדקודים.

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

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

ספירה כפולה

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

• עץ מושרש - עץ מכוון כך שאחד הקדקודים ("שורש") נבחר ולכל שאר הקשתות ניתן כיוון "החוצה" מהשורש (כך שניתן להגיע מהשורש לכל קדקוד).
• יער מושרש - איחוד זר של עצים מושרשים.

כעת נספור בשתי דרכים את התשובה לשאלה הבאה: בכמה דרכים ניתן להגיע מיער מושרש שבו עץ אחד ליער מושרש שבו n עצים (כל אחד מהם בין קדקוד אחד) על ידי הסרת קשתות, כאשר עוברים בדרך רק דרך יערות מושרשים?

• דרך ראשונה - מהסרת קשת מיער מושרש תמיד מקבלים יער מושרש, כי קיבלנו שני עצים חדשים: זה שהיה בו את השורש נשאר עץ, ובשני הקדקוד שחובר בקשת שהוסרה נעשה שורש. לכן מספר הדרכים להתחיל ביער מושרש שיש עץ אחד ולהגיע ל-n עצים בני קדקוד אחד הוא פשוט מספר הדרכים להתחיל בעץ כלשהו ולהוריד לו את כל הקשתות בסדר כלשהו, ומובטח לנו שנעבור בדרך רק ביערות מושרשים. נחשב: יש לנו בהתחלה C_n עצים שונים, וכיוון שלכל אחד מהם אפשר לבחור כל אחד מ-n הקודקודים להיות שורש, יש C_nn עצים מושרשים שונים. כעת נחשב את מספר הדרכים להסיר את הקשתות: יש n-1 קשתות, וצריך לבחור את הסדר שבו מסירים אותן; יש סך הכול !(n-1) דרכים כאלה. סך הכול מקבלים !(C_nn(n − 1 או !C_nn דרכים.
• דרך שנייה - הפעם נלך בכיוון ההפוך: נתחיל מיער עם n עצים ובכל שלב נוסיף קשת עד שנגיע ליער עם עץ אחד. לצורך כך נשים לב שהוספת קשת ליער מושרש הופכת ליער מושרש רק אם אנחנו מחברים קדקוד אל שורש של עץ אחר. נמספר את השלבים כך שהשלב בו יש n עצים הוא מספר 1 והאחרון מספר n. עכשיו נסתכל על שלב מספר k כלשהו: יש בו k עצים. כדי להוסיף קשת כך שיישאר עץ מושרש עלינו לבחור קדקוד כלשהו - יש n דרכים לעשות זאת, ואז לבחור עץ אחר - יש k-1 דרכים לעשות זאת. סך הכול יש (n(k-1 דרכים לעבור משלב k לשלב k+1. עלינו לעבור ככה על כל השלבים, ולכן יש להכפיל את כל הביטויים הללו לכל k עד שתיים (שזה השלב האחרון שעלינו לעבור ממנו לשלב הבא). מקבלים:

$\prod _{k=2}^{n}n(k-1)=n^{n-1}(n-1)!=n^{n-2}n!$

ציינו שתי דרכים לספור את אותו דבר, לכן אפשר להשוות ביניהן ולקבל:

$C_{n}n!=n^{n-2}n!$

$C_{n}=n^{n-2}$

מכאן שמספר העצים הפורשים הוא n^n-2.