במאמר זה, נדון בעץ הפורש ובעץ הפורש המינימלי. אבל לפני שנעבור ישירות לעבר העץ המתפרש, בואו נראה תחילה תיאור קצר של הגרף וסוגיו.
גרָף
ניתן להגדיר גרף כקבוצה של קודקודים וקצוות לחיבור קודקודים אלו. סוגי הגרפים ניתנים כדלקמן -
כעת, בואו נעבור לכיוון העץ המתפרש על הנושא.
מהו עץ פורש?
ניתן להגדיר עץ פורש כתת-גרף של גרף מחובר לא מכוון. הוא כולל את כל הקודקודים יחד עם מספר הקצוות המינימלי האפשרי. אם קודקוד כלשהו מתפספס, זה לא עץ פורש. עץ פורש הוא תת-קבוצה של הגרף שאין לה מחזורים, וגם לא ניתן לנתק אותה.
עץ פורש מורכב מקצוות (n-1), כאשר 'n' הוא מספר הקודקודים (או הצמתים). לקצוות של העץ המתפרש עשויות להיות מוקצות משקלים או לא. לכל העצים הפורשים האפשריים שנוצרו מהגרף G הנתון יהיה אותו מספר קודקודים, אבל מספר הקצוות בעץ הפורש יהיה שווה למספר הקודקודים בגרף הנתון מינוס 1.
גרף לא מכוון שלם יכול להיות נn-2 מספר עצים פורש איפה נ הוא מספר הקודקודים בגרף. נניח, אם n = 5 , מספר העצים המרביים האפשריים יהיה 55-2= 125.
יישומים של העץ המתפרש
בעיקרון, עץ פורש משמש כדי למצוא נתיב מינימלי לחיבור כל הצמתים של הגרף. כמה מהיישומים הנפוצים של העץ המתפרש רשומים כדלקמן -
- ניתוח אשכולות
- תכנון רשת אזרחית
- פרוטוקול ניתוב רשת מחשבים
כעת, בואו נבין את העץ המתפרש בעזרת דוגמה.
דוגמה לעץ משתרע
נניח שהגרף הוא -
כפי שנדון לעיל, עץ פורש מכיל את אותו מספר קודקודים כמו הגרף, מספר הקודקודים בגרף לעיל הוא 5; לכן, העץ המתפרש יכיל 5 קודקודים. הקצוות בעץ הפורש יהיו שווים למספר הקודקודים בגרף מינוס 1. לכן, יהיו 4 קצוות בעץ הפורש.
חלק מהעצים המשתרעים האפשריים שייווצרו מהגרף לעיל ניתנים כדלקמן -
מאפיינים של עץ פורש
חלק מהמאפיינים של העץ המתפרש ניתנים כדלקמן -
- יכול להיות יותר מעץ פורש אחד של גרף G מחובר.
- לעץ פורש אין מחזורים או לולאה.
- עץ פורש הוא מחובר מינימלית, אז הסרת קצה אחד מהעץ תגרום לניתוק הגרף.
- עץ פורש הוא מקסימום אציקלי, כך שהוספת קצה אחד לעץ תיצור לולאה.
- יכול להיות מקסימום נn-2 מספר העצים המשתרעים שניתן ליצור מגרף שלם.
- עץ פורש יש n-1 קצוות, כאשר 'n' הוא מספר הצמתים.
- אם הגרף הוא גרף שלם, אזי ניתן לבנות את העץ המתפרש על ידי הסרת קצוות מקסימליים (e-n+1), כאשר 'e' הוא מספר הקצוות ו-'n' הוא מספר הקודקודים.
אז, עץ פורש הוא תת-קבוצה של גרף G מחובר, ואין עץ פורש של גרף מנותק.
עץ טווח מינימלי
ניתן להגדיר עץ פורש מינימלי כעץ פורש שבו סכום משקלי הקצה הוא מינימום. משקל העץ הפורש הוא סכום המשקולות שניתנו לקצוות העץ הפורש. בעולם האמיתי, משקל זה יכול להיחשב כמרחק, עומס תנועה, עומס או כל ערך אקראי.
דוגמה לעץ פורש מינימום
בואו נבין את העץ המשתרע המינימלי בעזרת דוגמה.
סכום הקצוות של הגרף לעיל הוא 16. כעת, חלק מהעצים המתפרשים האפשריים שנוצרו מהגרף לעיל הם -
אז, עץ הפורש המינימלי שנבחר מהעצים המשתרעים לעיל עבור הגרף המשוקלל הנתון הוא -
יישומים של מינימום פורש עץ
היישומים של עץ המתח המינימלי ניתנים כדלקמן -
- ניתן להשתמש בעץ פורש מינימלי לתכנון רשתות אספקת מים, רשתות תקשורת ורשתות חשמל.
- ניתן להשתמש בו כדי למצוא נתיבים במפה.
אלגוריתמים לעץ מינימלי מתפרש
ניתן למצוא עץ פורש מינימלי מגרף משוקלל באמצעות האלגוריתמים המפורטים להלן -
- האלגוריתם של פריים
- האלגוריתם של קרוסקל
בוא נראה תיאור קצר של שני האלגוריתמים המפורטים למעלה.
האלגוריתם של פריים - זהו אלגוריתם חמדני שמתחיל בעץ פורש ריק. הוא משמש כדי למצוא את העץ המינימלי המתפרש מהגרף. אלגוריתם זה מוצא את תת-קבוצת הקצוות הכוללת כל קודקוד של הגרף כך שניתן למזער את סכום המשקולות של הקצוות.
es5 לעומת es6
כדי ללמוד עוד על האלגוריתם של הפרי, אתה יכול ללחוץ על הקישור למטה - https://www.javatpoint.com/prim-algorithm
האלגוריתם של קרוסקל - אלגוריתם זה משמש גם למציאת עץ המתח המינימלי עבור גרף משוקלל מחובר. האלגוריתם של קרוסקל עוקב גם אחר גישה חמדנית, שמוצאת פתרון אופטימלי בכל שלב במקום להתמקד באופטימום גלובלי.
כדי ללמוד עוד על האלגוריתם של הפרי, אתה יכול ללחוץ על הקישור למטה - https://www.javatpoint.com/kruskal-algorithm
אז, זה הכל לגבי המאמר. מקווה שהמאמר יהיה מועיל ואינפורמטיבי עבורך. כאן, דנו בעץ פורש ועץ פורש מינימלי יחד עם המאפיינים, הדוגמאות והיישומים שלהם.