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

הוסרו 9 בתים ,  לפני שנתיים
←‏ספירת מספר העצים הפורשים: סופרים את העצים ולא את מספרם
מ (בוט החלפות: \1ליניארי)
(←‏ספירת מספר העצים הפורשים: סופרים את העצים ולא את מספרם)
אפשר לקבל עץ פורש על ידי הסרת קשתות מן הגרף, בזו אחר זו, כל עוד הקשירות לא נפגעת. אם הגרף כולל מעגל (כלומר, סדרה של קודקודים <math>\ v_0,v_1,\dots,v_n</math> שבה כל זוג קודקודים סמוכים, וכן הזוג <math>\ v_0,v_n</math>, מחוברים בקשת), נוכל להסיר את אחת מקשתות המעגל בלי לפגוע בקשירות. על תהליך זה אפשר לחזור עד שבגרף אין מעגלים, והתוצאה היא עץ פורש. מכיוון שמספר הקשתות בעץ תלוי רק במספר הקודקודים שלו, לכל העצים הפורשים של אותו גרף יש אותו מספר קשתות (<math> \displaystyle n-1 </math> כאשר מספר הקודקודים בגרף הוא <math> \displaystyle n </math>). דרכים יעילות יותר למציאת עץ פורש הם באמצעות [[אלגוריתם חיפוש לעומק]] או [[אלגוריתם חיפוש לרוחב]]. אלגוריתמים אלו ירוצו ב[[סיבוכיות זמן|זמן]] ליניארי במספר הקשתות בגרף.
 
==ספירת מספר העצים הפורשים==
את מספר העצים הפורשים של גרף אפשר לקבל מ[[משפט קירכהוף]]: אם A היא [[מטריצת שכנויות|מטריצת השכנויות]] של הגרף ו- D ה[[מטריצה אלכסונית|מטריצה האלכסונית]] שרכיבי האלכסון שלה הם ה[[דרגה (תורת הגרפים)|דרגות]] של הקודקודים, אז המטריצה <math>\ D-A</math> אינה [[מטריצה הפיכה|הפיכה]] (שכן שורותיה מסתכמות לאפס). עם זאת, מכפלת ה[[ערך עצמי|ערכים העצמיים]] השונים מאפס שווה למספר העצים הפורשים, כפול במספר הקודקודים (זהו מספר העצים הפורשים, כשסופרים עצים עם שורש).