עץ פורש מינימלי – הבדלי גרסאות

ב[[תורת הגרפים]], '''[[עץ פורש]] מינימלי''' (אנגלית: Minimum spanning tree) או '''העץ הפורש המזערי''' הוא [[גרף עץ|עץ]] המורכב מתת-קבוצה של קשתות בגרף נתון, אשר מקיים את שתי התכונות הבאות:

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