עץ פורש מינימלי
מתוך ויקיפדיה, האנציקלופדיה החופשית
בתורת הגרפים, עץ פורש מינימלי או העץ הפורש המזערי הוא עץ המורכב מתת-קבוצה של קשתות בגרף נתון, אשר מקיים את שתי התכונות הבאות:
- הוא פורש את הגרף - כלומר כולל את כל הצמתים בגרף.
- הוא מינימלי או מזערי - כלומר סך משקל כל הקשתות שלו הוא הנמוך ביותר האפשרי.
בהגדרה גרפית:
שבו
הוא המשקל הנמוך ביותר ו-
היא הקשת בין
ובין
.
לדוגמה חברת טלוויזיה בכבלים מניחה תשתית כבלים בשכונה כלשהי. אם החברה מוגבלת בכך שעליה להניח את הכבלים אך ורק לאורך מסלולים מסוימים, אזי יהיה גרף אשר מייצג את הנקודות המחוברות במסלולים אלו. חלק מן הקווים יכולים להיות יקרים יותר, מכיוון שהמרחק גדול יותר, או שיש צורך לקבור את הכבל יותר עמוק באזור זה.
עץ פורש בשביל גרף זה, הוא קבוצה חלקית הכוללת רק את המסלולים שאינם סגורים במעגל, ועדיין כל בית יהיה מחובר. ייתכנו מספר עצים פורשים לגרף אחד. עץ פורש מזערי הוא עץ פורש, בעל המשקל הכולל הנמוך ביותר. אם יש אפשרויות שוות (תיקו), הרי שיכולים להיות כמה עצים פורשים מזעריים.
האלגוריתם הראשון למציאת עץ פורש מזערי בגרף לא מכוון הומצא בידי המדען הצ'כי אוטקה בוהרובקה ב1926. מטרתו הייתה כיסוי חשמלי יעיל של חבל בוהמיה. כיום משתמשים בשני אלגוריתמים ידועים לגרף לא מכוון: האלגוריתם של פרים וכן האלגוריתם של קרוסקל. שניהם אלגוריתמים חמדניים. שניהם רצים בזמן פולינומיאלי, כך שמציאת פתרונות לבעיות כאלו, הם בתחום הסיבוכיות של P.
האלגוריתם המהיר ביותר עד היום, לעץ פורש מינימלי, פותח על ידי שאזל, ומבוסס על בורובקה. זמן הריצה שלו הוא:
כש
מסמן את מספר הקשתות,
מסמן את מספר הצמתים ו
הוא ההפכי המוכר של פעולת אקרמן. (ראו: פונקציית אקרמן)
מהו האלגוריתם המהיר ביותר לפתרון בעיה זו? זוהי אחת השאלות הפתוחות הישנות ביותר בתחום מדעי המחשב. אם משקלי הקשתות הינם מספרים שלמים המוגבלים במספר הביטים המייצגים אותם, אזי ידועים אלגוריתמים מוחלטים (דטרמיניסטיים - שאינם פועלים באקראיות) עם זמן ריצה לינארי
. עבור משקלים כלליים, ידועים אלגוריתמים אקראיים הרצים בזמן הצפוי להיות לינארי. אם קיים אלגוריתם מוחלט למשקלים כלליים, בעל זמן ריצה ביחס ישר (לינארי) עדיין נותר בגדר שאלה פתוחה.
[עריכה] קישורים חיצוניים
- Otakar Boruvka on Minimum Spanning Tree Problem (translation of the both 1926 papers, comments, history) (2000) Jaroslav Nesetril, Eva Milková, Helena Nesetrilová (section 7 gives his algorithm, which looks like a cross between Prim's and Kruskal's)
- A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, Bernard Chazelle, 1999


