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