הצגת המקור של הדף "עץ פורש"

{{מקורות|רמה=מחפש|נושא=מדעי הטבע}}
[[קובץ:4x4 grid spanning tree.svg|ממוזער|עץ פורש (הקשתות הכחולות) של גרף הגריד]]
[[קובץ:Натурализация_гамильтоновых_циклов.jpg|שמאל|ממוזער|שלוש דוגמאות בגרף רשת 8 על 8]]
ב[[תורת הגרפים]], '''עץ פורשׂ''' של [[תורת הגרפים|גרף]] [[גרף קשיר|קשיר]] G הוא [[תת גרף]] קשיר של G, המכיל את כל צומתי G, ואין לו מעגלים. תת-גרף כזה הוא [[עץ (תורת הגרפים)|עץ]]. 

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

==ספירת העצים הפורשים==
את מספר העצים הפורשים של גרף אפשר לקבל מ[[משפט קירכהוף]]: אם A היא [[מטריצת שכנויות|מטריצת השכנויות]] של הגרף ו- D ה[[מטריצה אלכסונית|מטריצה האלכסונית]] שרכיבי האלכסון שלה הם ה[[דרגה (תורת הגרפים)|דרגות]] של הקודקודים, אז המטריצה <math>\ D-A</math> אינה [[מטריצה הפיכה|הפיכה]] (שכן שורותיה מסתכמות לאפס). עם זאת, מכפלת ה[[ערך עצמי|ערכים העצמיים]] השונים מאפס שווה למספר העצים הפורשים, כפול במספר הקודקודים (זהו מספר העצים הפורשים, כשסופרים עצים עם שורש). 

במקרה המיוחד של הגרף השלם על n קודקודים (הגרף שכל שני קודקודים שלו מחוברים בקשת אחת), מספר העצים הפורשים הוא <math>\ n^{n-2}</math>. לתוצאה זו, הקרויה [[נוסחת קיילי]], ידועות מספר הוכחות, בהן זו של פרופר המבוססת על [[התאמה חד חד ערכית]] בין העצים הפורשים של [[גרף שלם]] לבין המילים באורך n-2 מעל אלפבית של <math>n</math> אותיות אפשריות.

==עץ פורש מינימלי==
{{ערך מורחב|עץ פורש מינימלי}}
[[קובץ:Minimum spanning tree.svg|שמאל|ממוזער|250px|עץ פורש מינימלי]]
כאשר בגרף הנתון יש "משקל" לכל קשת (כלומר, זהו [[גרף ממושקל]]), טבעי לחפש עץ פורש שלו משקל כולל מינימלי. עץ כזה נקרא [[עץ פורש מינימלי]]. לבעיה של מציאת עץ כזה יש השלכות מעשיות רבות. לדוגמה, כאשר רוצים לסלול רשת כבישים בין ערים כך שבין כל שתי ערים יהיה מסלול ולעשות זאת במחיר מינימלי, מחפשים את העץ הפורש המינימלי של הגרף שצמתיו הם הערים וקשתותיו הכבישים הפוטנציאליים ביניהן (המשקל הוא אורך הכבישים שיהיה צורך לסלול).

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{MathWorld}}
{{תורת הגרפים}}
{{בקרת זהויות}}
[[קטגוריה:תורת הגרפים]]
[[קטגוריה:עצים (גרפים)|פורש]]