|
|
עמוד:326
6 . 1 הצגת הבעיה נתון גרף בלתי מכוון קשיר , 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' ( £ ) יהיה מינימלי . עץ פורש ( spanning tree ) של גרף G קשיר הוא עץ המכיל את כל קדקודי הגרף ס . ע . ץ פורש מינימלי ( minimum spanning tree ) הנו עץ פורש , ש 0 כום המשקלות הרשומים בצד הקשתות של העץ הוא מינימלי . . 6 עץ פורש מ > נ > מלי בפרק זה נתוודע אל בעיה ממשית בחקר הביצועים ונציג לה פתרונות אפשריים שונים . להלן הצגה של הבעיה ושל פתרונותיה ( האלגוריתמים ) השונים .
|
|