נוסחת קיילי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Luckas-bot (שיחה | תרומות) מ r2.5.2) (בוט מוסיף: es:Fórmula de Cayley |
מ קישורים פנימיים |
||
שורה 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> ואף שהלה התייחס במפורש לבורכרט שמו נדבק לנוסחה.
==מושגי יסוד==
שורה 22:
[[קובץ:Tree graph.svg|שמאל|ממוזער|250px|עץ ממוספר]]
למשפט קיילי מספר הוכחות, אחת היפות שבהן התגלתה על ידי היינץ פרופר בשנת [[1918]]. ההוכחה מבוססת על בנייה של מילה המציינת מבנה של עץ ובכך מראה [[התאמה חד חד ערכית]] בין העצים הפורשים של גרף שלם לבין המילים באורך n-2 מעל אלפבית של n אותיות אפשריות .
===בניית פרופר===
| |||