עץ פורש

בתורת הגרפים, עץ פורש של גרף קשיר G הוא תת גרף קשיר של G, המכיל את כל צומתי G, ואין לו מעגלים. תת-גרף כזה הוא עץ.

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

את מספר העצים הפורשים של גרף אפשר לקבל ממשפט קירכהוף: אם A היא מטריצת השכנויות של הגרף ו- D המטריצה האלכסונית שרכיבי האלכסון שלה הם הדרגות של הקודקודים, אז המטריצה $\ D-A$ אינה הפיכה (שכן שורותיה מסתכמות לאפס). עם זאת, מכפלת הערכים העצמיים השונים מאפס שווה למספר העצים הפורשים, כפול במספר הקודקודים (זהו מספר העצים הפורשים, כשסופרים עצים עם שורש).

במקרה המיוחד של הגרף השלם על n קודקודים (הגרף שכל שני קודקודים שלו מחוברים בקשת אחת), מספר העצים הפורשים הוא $\ n^{n-2}$. לתוצאה זו, הקרויה נוסחת קיילי, ידועות הוכחות רבות.

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