עץ פורש מינימלי (Minimum spanning tree) של גרף ממושקל לא מכוון הוא עץ פורש שבו סכום משקלי הקשתות הוא הקטן ביותר מבין כל העצים הפורשים של אותו גרף. גרף הוא אוסף צמתים (נקודות) וקשתות (קווים) שמחברות ביניהם. עץ פורש הוא תת־גרף קשיר ונטול מעגלים שמכיל את כל הצמתים בגרף.
חברת כבלים שרוצה לחבר בתים לשכונה יכולה לראות את הבעיה כך: כל בית הוא צומת וכל מסלול אפשרי הוא קשת עם עלות. עץ פורש מבטיח שכל בית מחובר בלי מעגלים. עץ פורש מינימלי בוחר קשתות כך שסכום העלויות קטן ככל שניתן.
אם בגרף יש n צמתים, כל עץ פורש מכיל בדיוק n−1 קשתות. יכולות להיות מספר אפשרויות של עצים פורשים מינימליים באותו גרף. למשל, אם כל משקלי הקשתות שווים, כל עץ פורש הוא מינימלי.
כאשר קיימים כמה עצים מינימליים, לכל העצים האלה אותה קבוצה של משקלים, גם אם הקשתות עצמן שונות.
אם לכל קשת יש משקל שונה, הרי קיים רק עץ פורש מינימלי אחד. זה קורה לעתים במצבים אמיתיים, כי נדיר ששתי עלויות יהיו זהות בדיוק.
הרעיון להוכחת ייחודיות כשהמשקלים שונים מתבסס על ניגוד. בוחרים קשת קלה ביותר שמופיעה בעץ אחד אבל לא בשני. מוסיפים אותה לעץ השני ונוצרת מעגל. מחליפים קשת כבדה יותר מתוך המעגל בקלה יותר. החלפה כזו מקטינה את המשקל, וזה סותר את ההנחה שגם העץ השני מינימלי.
אם בקשת מסוימת במעגל משקלה גדול מכל שאר הקשתות במעגל, אז קשת זו לא יכולה להיכלל באף עץ פורש מינימלי. ניתן להסביר זאת על ידי החלפה שלה בקשת זולה אחרת מתוך המעגל ולהקטין את המשקל הכולל.
האלגוריתם הראשון למציאת עץ פורש מינימלי הומצא ב-1926 על ידי אוטקר בוהרובקה שעבד על בעיות חיווט. שני אלגוריתמים מרכזיים נוספים הם פרים וקרוסקל. שניהם משמשים כאלגוריתמים חמדניים, כלומר בוחרים בכל צעד את האפשרות הזולה ביותר באותו רגע.
אלגוריתמים אלה פועלים בזמן פולינומי, מה שאומר שניתן למצוא פתרונות ביעילות יחסית. קיימים גם אלגוריתמים מהירים יותר למקרים מיוחדים של משקלים שלמים. האלגוריתם המהיר ביותר הידוע כיום פותח על ידי ברנרד שאזל והוא מבוסס על רעיונות של בוהרובקה; זמן הריצה שלו קרוב לקווי ביחס למספר הקשתות, והוא משתמש בפונקציה מתמטית מיוחדת (פונקציית אקרמן ההפוכה). עדיין לא ידוע אם קיים אלגוריתם דטרמיניסטי בזמן ליניארי לכל סוגי המשקלים.
עץ פורש מינימלי הוא דרך לחבר את כל הנקודות בגרף עם פחות עלות. גרף הוא קווים וצמתים. צומת זה נקודה; קשת זה קו שמחבר בין נקודות. משקל של קשת זה עלות או אורך שלה.
חברת כבלים רוצה לחבר בתים. כל בית זה נקודה. כל כביש הוא קשת בעלות מסוימת. עץ פורש מקשר את כל הבתים בלי מעגלים. עץ פורש מינימלי מוצא את הקווים הכי זולים.
עץ פורש מחבר n נקודות עם בדיוק n−1 קווים. יכול להיות יותר מעץ פורש מינימלי אחד. אם כל הקווים שווים בעלות, כל עץ פורש הוא מינימלי.
אם לכל קו יש עלות שונה מאוד, אז העץ המינימלי יהיה אחד בלבד.
יש מאז הרבה אלגוריתמים למצוא עץ פורש מינימלי. שמות מוכרים הם בוהרובקה, פרים וקרוסקל. האלגוריתמים האלה עוזרים למצוא חיבורים זולים בין נקודות. יש גם אלגוריתמים מאוד מהירים, אבל הם יותר מתמטיים.
תגובות גולשים