|
|
עמוד:275
5 . 6 . 1 עץ פורש DFS בתום סריקת קדקודי הגרף , G = ( V , E ) נוצר התת-גרף , G = ( V , E ) כאשר E היא קבוצת הקשתות שעברנו דרכן בכדי לסרוק את קדקודי הגרף בשיטת . DFS ניתן להגדיר את E כדלקמן ן E = {( P ( v ) , v )| v £ V and P ( v ) * 0 הערה : תת-הגרף G = ( V , E ) עטר הגרף הלא ממון G מגדיר עץ ז אשר ייקרא העץ הפורש של שיטת הסריקה לעומק ( ובקיצור : עץ פורש . ( DFS העץ הפורש של שיטת הסריקה לעומק של הגרף שראינו בהרחבה בדוגמה הוא ו בסמוך לכל צומת מופיע מספרו של הקדקוד , ובכל קדקוד רשום מספר המציין את סדר התיוג של הקדקודים בשיטת . DFS
|
|