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

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

עריכות