עץ פורש מינימלי או עץ פורש משקל מינימלי הוא תת-קבוצה של הקצוות של גרף לא מכוון מחובר, משוקל קצה, המחבר את כל הקודקודים יחדיו, ללא כל מחזוריות ועם משקל הקצוות המינימלי האפשרי. כלומר, זהו עץ פורש שסכום משקלי הקצוות שלו קטן ככל האפשר.
מהו מינימום עץ פורש עם דוגמה?
עץ פורש מינימום הוא סוג מיוחד של עץ שממזער את האורכים (או ה"משקלים") של קצוות העץ. דוגמה לכך היא חברת כבלים שרוצה לשים קו לשכונות מרובות; על ידי מזעור כמות הכבלים המונחת, חברת הכבלים תחסוך כסף. לעץ יש נתיב אחד מצטרף לכל שני קודקודים.
איך מוצאים את עץ המתח המינימלי?
מצא השכן הלא-צבעוני הקרוב ביותר לתת-הגרף האדום (כלומר, הקודקוד הקרוב ביותר לקודקוד אדום כלשהו). סמן אותו ואת הקצה המחבר את הקודקוד לתת-גרף האדום באדום. חזור על שלב 2 עד שכל הקודקודים מסומנים באדום. תת-הגרף האדום הוא עץ פורש מינימום.
למה אתה מתכוון בעץ פורש ועץ פורש מינימום?
עץ פורש של גרף הוא אוסף של קצוות מחוברים הכוללים כל קודקוד בגרף, אך אינם יוצרים מחזור. … העץ המינימלי הוא זה שלמשקלי הקצוות המצטברים שלו יש את הערך הקטן ביותר, עם זאת.
מה ההבדל בין עץ פורש לעץ פורש מינימלי?
אם הגרף הואבשקלול קצה, נוכל להגדיר את weight של עץ פורש כסכום המשקולות של כל הקצוות שלו. עץ פורש מינימלי הוא עץ פורש שמשקלו הוא הקטן ביותר מבין כל העצים המשתרעים האפשריים.
