עץ פורש

עץ פורש של גרף קשיר G הוא תת‑גרף קשיר שמכיל את כל צמתי G ואין לו מעגלים. (גרף קשיר, כל צומת נגיש מכל צומת אחר דרך מסלול.) אפשר להשיג עץ פורש על־ידי הסרת קשתות (קשת = קישור בין שני צמתים) ממעגלים, כל עוד הקשירות נשמרת. תהליך זה חוזר עד שלא נשאר מעגל; התוצאה היא עץ פורש. לכל עץ פורש של גרף עם n צמתים יש בדיוק n−1 קשתות. להנחת עבודה מהירה משתמשים באלגוריתם חיפוש לעומק (DFS) או חיפוש לרוחב (BFS). שניהם רצים בזמן ליניארי ביחס למספר הקשתות בגרף.

מספר עצי הפורש של גרף מחושב במשפט קירכהוף. אם A היא מטריצת השכנויות של הגרף ו‑D היא מטריצת דרגות (אלכסונית, שבה הדרגות של הצמתים על האלכסון), אז המטריצה D−A אינה הפיכה. מכפלת הערכים העצמיים (eigenvalues, מספרים שמאפיינים מטריצה) השונים מאפס שווה למספר עצי הפורש כפול מספר הצמתים. במקרה של גרף שלם על n צמתים (כל שני צמתים מחוברים), מספר העצים הפורשים הוא n^{n-2}. תוצאה זו נקראת נוסחת קיילי. יש לה הוכחות שונות, למשל הוכחה של פרופר המבוססת על התאמה בין עצי פורש ומחרוזות באורך n−2 מעל אלפבית של n אותיות.

בגרף ממושקל יש לכל קשת משקל (עלות). עץ פורש מינימלי הוא עץ פורש שמשקלו הכולל מינימלי. בעיות מעשיות רבות נפתרות כך: למשל בניית רשת כבישים שמחברת ערים במחיר כולל מינימלי. במקרה כזה הצמתים הם הערים, הקשתות הן הכבישים הפוטנציאליים, והמשקל הוא אורך או עלות סלילת הדרך.

עץ פורש הוא גרף שמכיל את כל הצמתים אבל אין בו מעגלים. (גרף = נקודות וקווים בין הנקודות.)

אפשר לקבל עץ פורש על־ידי הסרת קווים ממעגלים עד שלא נשארים מעגלים. עץ פורש תמיד יש בו בדיוק N פחות 1 קווים, אם יש N נקודות.

יש דרך מתמטית לספור כמה עצי פורש יש לגרף. במקרה שבו כל שתי נקודות מחוברות זו לזו, יש נוסחה ידועה בשם קיילי שקובעת את מספר העצים.

אם לכל קו יש מחיר, מחפשים עץ פורש שהמחיר הכולל שלו הכי קטן. זה שימושי לבניית רשתות וכבישים במחיר נמוך.