3,867
עריכות
הבדלים בין גרסאות בדף "עץ פורש"
מ
תיקון קישור
Felagund-bot (שיחה | תרומות) (בוט - מחליף 'דוגמא' ב'דוגמה') |
מ (תיקון קישור) |
||
|
אפשר לקבל עץ פורש על-ידי הסרת קשתות מן הגרף, בזו אחר זו, בלי לפגוע בקשירות: אם הגרף כולל מעגל (כלומר, סדרה של קודקודים <math>\ v_0,v_1,\dots,v_n</math> שבה כל זוג קודקודים סמוכים, וכן הזוג <math>\ v_0,v_n</math>, מחוברים בקשת), אפשר להסיר את אחת הקשתות של המעגל. על תהליך זה אפשר לחזור עד שבגרף אין מעגלים, והתוצאה היא עץ פורש. מכיוון שמספר הקשתות בעץ תלוי רק במספר הקודקודים שלו, לכל העצים הפורשים של אותו גרף יש אותו מספר קשתות.
את מספר העצים הפורשים של גרף אפשר לקבל מ[[
במקרה המיוחד של הגרף השלם על n קודקודים (הגרף שכל שני קודקודים שלו מחוברים בקשת אחת), מספר העצים הפורשים הוא <math>\ n^{n-2}</math>. לתוצאה זו, הקרויה [[נוסחת קיילי]], ידועות הוכחות רבות.
| |||