עץ פורש – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מאין תקציר עריכה |
מ בוט החלפות: על ידי; |
||
שורה 1:
ב[[תורת הגרפים]], '''עץ פורש''' של [[תורת הגרפים|גרף]] [[קשירות (תורת הגרפים)|קשיר]] G הוא [[תת גרף]] [[קשירות (תורת הגרפים)|קשיר]] של G, המכיל את כל צומתי G, ואין לו מעגלים. תת-גרף כזה הוא [[עץ (תורת הגרפים)|עץ]].
אפשר לקבל עץ פורש על
את מספר העצים הפורשים של גרף אפשר לקבל מ[[משפט קירכהוף]]: אם A היא [[מטריצת שכנויות|מטריצת השכנויות]] של הגרף ו- D ה[[מטריצה אלכסונית|מטריצה האלכסונית]] שרכיבי האלכסון שלה הם ה[[דרגה (תורת הגרפים)|דרגות]] של הקודקודים, אז המטריצה <math>\ D-A</math> אינה [[מטריצה הפיכה|הפיכה]] (שכן שורותיה מסתכמות לאפס). עם זאת, מכפלת ה[[ערך עצמי|ערכים העצמיים]] השונים מאפס שווה למספר העצים הפורשים, כפול במספר הקודקודים (זהו מספר העצים הפורשים, כשסופרים עצים עם שורש).
|