כל מה שרצית לדעת על עץ פורש:
בתורת הגרפים, עץ פורש של גרף קשיר G הוא תת גרף קשיר של G, המכיל את כל צומתי G, ואין לו מעגלים.
תת-גרף כזה הוא עץ.
אפשר לקבל עץ פורש על ידי הסרת קשתות מן הגרף, בזו אחר זו, כל עוד הקשירות לא נפגעת.
אם הגרף כולל מעגל (כלומר, סדרה של קודקודים   v 0 , v 1 , … , v n {\displaystyle \ v_{0},v_{1},\dots ,v_{n}} שבה כל זוג קודקודים סמוכים, וכן הזוג   v 0 , v n {\displaystyle \ v_{0},v_{n}} , מחוברים בקשת), נוכל להסיר את אחת מקשתות המעגל בלי לפגוע בקשירות.
על תהליך זה אפשר לחזור עד שבגרף אין מעגלים, והתוצאה היא עץ פורש.
מכיוון שמספר הקשתות בעץ תלוי רק במספר הקודקודים שלו, לכל העצים הפורשים של אותו גרף יש אותו מספר קשתות ( n − 1 {\displaystyle \displaystyle n-1} כאשר מספר הקודקודים בגרף הוא n {\displaystyle \displaystyle n} ).
דרכים יעילות יותר למציאת עץ פורש הם באמצעות אלגוריתם חיפוש לעומק או אלגוריתם חיפוש לרוחב.
אלגוריתמים אלו ירוצו בזמן ליניארי במספר הקשתות בגרף.

נלקח מויקיפדיה

הגדרות נוספות הקשורות לעץ פורש:
•תורת הגרפים
•עצים (גרפים)