נתון גרף בלתי מכוון קשיר , G = ( V , E ) כאשר V מבטא קבוצת קדקודים , - £ -ו קבוצת קשתות . פונקציית המשקל w . E ^ -R קובעת משקל לכל קשת בגרף ס , וכל קשת ( u , v ) G E היא בעלת משקל . w ( u , v ) המשקל לכל קשת ( u , v ) יכול לייצג את המרחק בין שני הקדקודים , v-1 u או את ממוצע המכוניות העוברות בין שתי ערים המיוצגות באמצעות שני הקדקודים בגרף , או את העלות של סלילת כביש בין שתי ערים המיוצגות באמצעות שני קדקודי הגרף , וכדומה . הרשת הזאת יכולה לייצג מערכות קשר ותחבורה , כגון : רשתות כבישים , מערכת כבלי טלפון , מערכות כבלים לחיבור כל תחנות הטלוויזיה לרשת מסוימת או רשת תקשורת מחשבים . בעיית העץ הפורש המינימלי הבעיה : יש למצוא תת-גרף T = ( V , E ) ללא מעגלים של קשתות המחברות את כל T קדקודי הגרף הנתון ס , ואשר משקלו הכולל w ( E T ) = £ w ( u , v ) הוא מינימלי . ( u , v ) eE r גרף קשיר ללא מעגלים נקרא עץ , כיוון -V מחברת את כל קדקודי הגרף ואינה מכילה T מעגלים , התת-גרף T יוצר עץ . עץ כזה נקרא עץ פורש . במילים אחרות , מטרתנו היא למצוא עץ פורש , , T כזה , שסכום המשקלות המיוחסים לקשתות העץ , w' ( £ )...
אל הספר