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

נוספו 2 בתים ,  לפני 13 שנים
מ
אין תקציר עריכה
מ (תיקון קישור)
מ
ב[[תורת הגרפים]], '''עץ פורש''' של [[תורת הגרפים|גרף]] [[קשירות (תורת הגרפים)|קשיר]] G הוא [[תת גרף]] [[קשירות (תורת הגרפים)|קשיר]] של G, המכיל את כל צמתיצומתי G, ואין לו מעגלים. תת-גרף כזה הוא [[עץ (תורת הגרפים)|עץ]].
 
אפשר לקבל עץ פורש על-ידי הסרת קשתות מן הגרף, בזו אחר זו, בלי לפגוע בקשירות: אם הגרף כולל מעגל (כלומר, סדרה של קודקודים <math>\ v_0,v_1,\dots,v_n</math> שבה כל זוג קודקודים סמוכים, וכן הזוג <math>\ v_0,v_n</math>, מחוברים בקשת), אפשר להסיר את אחת הקשתות של המעגל. על תהליך זה אפשר לחזור עד שבגרף אין מעגלים, והתוצאה היא עץ פורש. מכיוון שמספר הקשתות בעץ תלוי רק במספר הקודקודים שלו, לכל העצים הפורשים של אותו גרף יש אותו מספר קשתות.