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