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

שגיאה ביצירת תמונה ממוזערת:

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

בכתיב פורמלי: אם משקל הקשת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (u,v)} הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w(u,v)} ועבור עץ הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} יהי משקלו $w(T)=\sum _{(u,v)\in T}w(u,v)$, העץ הפורש המינימלי הוא זה בעל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w\left(T\right)} הקטן ביותר.

המחשה

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

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

התפתחות האלגוריתם

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

הניסיון למצוא את האלגוריתם המהיר ביותר לפתרון בעיה זו הוא מהוותיקים ביותר בתחום מדעי המחשב. אם משקלי הקשתות הם מספרים שלמים המוגבלים במספר הביטים המייצגים אותם, אזי ידועים אלגוריתמים מוחלטים (דטרמיניסטיים - שאינם פועלים באקראיות) עם זמן ריצה ליניארי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(m)} . עבור משקלים כלליים, ידועים אלגוריתמים אקראיים הרצים בזמן שתוחלתו ליניארית במספר הקשתות.

האלגוריתם המהיר ביותר עד היום, לעץ פורש מינימלי, פותח על ידי ברנרד שאזל, ומבוסס על האלגוריתם של בוהרובקה. זמן הריצה שלו הוא: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(m \alpha (m,n))} כש-$\ m$ מסמן את מספר הקשתות, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} מסמן את מספר הצמתים ו-$\alpha (m,n)=\min\{i\geq 1:A(i,\lfloor m/n\rfloor )\geq \log _{2}n\}$ היא פונקציית אקרמן ההפוכה. קיומו של אלגוריתם דטרמיניסטי למשקלים כלליים, בעל זמן ריצה ליניארי עדיין נותר בגדר שאלה פתוחה.

ראו גם

• תורת הגרפים

קישורים חיצוניים

• 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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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