הבדלים בין גרסאות בדף "עץ פורש"

נוספו 98 בתים ,  לפני 9 שנים
אין תקציר עריכה
את מספר העצים הפורשים של גרף אפשר לקבל מ[[משפט קירכהוף]]: אם A היא [[מטריצת שכנויות|מטריצת השכנויות]] של הגרף ו- D ה[[מטריצה אלכסונית|מטריצה האלכסונית]] שרכיבי האלכסון שלה הם ה[[דרגה (תורת הגרפים)|דרגות]] של הקודקודים, אז המטריצה <math>\ D-A</math> אינה [[מטריצה הפיכה|הפיכה]] (שכן שורותיה מסתכמות לאפס). עם זאת, מכפלת ה[[ערך עצמי|ערכים העצמיים]] השונים מאפס שווה למספר העצים הפורשים, כפול במספר הקודקודים (זהו מספר העצים הפורשים, כשסופרים עצים עם שורש).
 
[[תמונה:Minimum spanning tree.svg|שמאל|ממוזער|250px|עץ פורש מינימלי]]
במקרה המיוחד של הגרף השלם על n קודקודים (הגרף שכל שני קודקודים שלו מחוברים בקשת אחת), מספר העצים הפורשים הוא <math>\ n^{n-2}</math>. לתוצאה זו, הקרויה [[נוסחת קיילי]], ידועות הוכחות רבות.
 
5,675

עריכות