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

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

עריכות