נוסחת קיילי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
רשימה מלאה של העצים המסומנים על 3,2 ו-4 צמתים

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

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

מושגי יסוד[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

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

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

עץ ממוספר

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

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

הוכחה זו התגלתה על ידי היינץ פרופר בשנת 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}, ומכאן נובעת נוסחת קיילי.

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

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

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

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

  • דרך ראשונה - מהסרת קשת מיער מושרש תמיד מקבלים יער מושרש, כי קיבלנו שני עצים חדשים: זה שהיה בו את השורש נשאר עץ, ובשני הקודקוד שחובר בקשת שהוסרה נעשה שורש. לכן מספר הדרכים להתחיל ביער מושרש שיש עץ אחד ולהגיע ל-n עצים בני קודקוד אחד הוא פשוט מספר הדרכים להתחיל בעץ כלשהו ולהוריד לו את כל הקשתות בסדר כלשהו, ומובטח לנו שנעבור בדרך רק ביערות מושרשים. נחשב: יש לנו בהתחלה Cn עצים שונים, וכיוון שלכל אחד מהם אפשר לבחור כל אחד מ-n הקודקודים להיות שורש, יש Cnn עצים מושרשים שונים. כעת נחשב את מספר הדרכים להסיר את הקשתות: יש n-1 קשתות, וצריך לבחור את הסדר שבו מסירים אותן; יש סך הכול !(n-1) דרכים כאלה. סך הכול מקבלים !(Cnn(n − 1 או !Cnn דרכים.
  • דרך שנייה - הפעם נלך בכיוון ההפוך: נתחיל מיער עם 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}

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

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

  1. ^ A. Cayley (1889). "A theorem on trees". Quart. J. Math 23: 376–378.