נוסחת קיילי – הבדלי גרסאות

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