נוסחת קיילי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 2:
'''נוסחת קיילי''' היא [[נוסחה]] ב[[תורת הגרפים]] הקובעת שמספר ה[[עץ (תורת הגרפים)|עצים]] הפורשים של [[גרף שלם]] בעל n צמתים הוא <math>\ n^{n-2}</math>. בניסוח אחר ניתן לומר שמספר העצים המחברים n צמתים מסומנים הוא <math>\ n^{n-2}</math>. הנוסחה נקראת על שמו של המתמטיקאי הבריטי [[ארתור קיילי]], וניתן לראות אותה כמקרה פרטי של [[משפט קירכהוף]], המאפיין את מספר העצים הפורשים בגרף כלשהו.
הנוסחה הוכחה לראשונה על ידי המתמטיקאי הגרמני קרל בורכרט ב-1860, על ידי שימוש ב[[דטרמיננטה|דטרמיננטות]]. היא הוכללה על ידי קיילי ב-1889,<ref>{{cite journal |author=A. Cayley |url=http://books.google.com/books?id=M7c4AAAAIAAJ&pg=PA26 |title=A theorem on trees |journal=Quart. J. Math |volume=23 |year=1889 |pages=376–378}}</ref> ואף שהלה התייחס במפורש לבורכרט שמו נדבק לנוסחה.
==מושגי יסוד==
שורה 33:
מכאן שיש [[התאמה חד חד ערכית]] בין עצים בעלי n קודקודים למילים המכילות n-2 אותיות מתוך n אותיות אפשריות. מספר המילים הללו הוא <math>\ n^{n-2}</math>, ומכאן נובעת נוסחת קיילי.
==הערות שוליים==
{{הערות שוליים}}
[[קטגוריה: תורת הגרפים]]
| |||