עץ פורש – הבדלי גרסאות

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