עץ פורש מינימלי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Minimum spanning tree.svg

בתורת הגרפים, עץ פורש מינימלי (אנגלית: Minimum spanning tree) הוא עץ המורכב מתת-קבוצה של קשתות בגרף נתון, אשר מקיים את שתי התכונות הבאות:

  • הוא פורש את הגרף - כלומר כולל את כל הצמתים בגרף.
  • הוא מינימלי (או: מזערי) בסכום משקלי הקשתות שלו, שהוא הקטן ביותר האפשרי מכל העצים הפורשים של הגרף. כלומר אם משקל הקשת \ (u,v) (הקשת המחברת בין \ u ובין \ v) הוא  w(u,v) ועבור עץ T יהי משקלו
w(T) = \sum_{(u,v)\in T} w(u,v),

אז אנו מעוניינים בעץ עם w\left(T\right) הקטן ביותר.

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

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

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

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

האלגוריתם המהיר ביותר עד היום, לעץ פורש מינימלי, פותח על ידי ברנרד שאזל, ומבוסס על האלגוריתם של בוהרובקה. זמן הריצה שלו הוא: \ O(m \alpha (m,n)) כש\ m מסמן את מספר הקשתות, \ n מסמן את מספר הצמתים ו- \alpha(m,n) = \min\{i \geq 1 : A(i,\lfloor m/n \rfloor) \geq \log_2 n\} היא פונקציית אקרמן ההפוכה. קיומו של אלגוריתם דטרמיניסטי למשקלים כלליים, בעל זמן ריצה לינארי עדיין נותר בגדר שאלה פתוחה.

קישורים חיצוניים[עריכת קוד מקור | עריכה]