משתמש:Snirma19/טיוטה

בעיית מציאת מינימום מסלולים זרים בצמתים המכסים את כל צמתי הגרף

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

פתרון הבעיה

ניתן לפתור את הבעיה באופן הבא:

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

לאחר הבניה של רשת הזרימה ניתן להסתכל עליה באופן הבא:

• מסלול ברשת שנבנתה: עבור קשת e(u,v) המחוברת לקשת e_2(v,k) נוכל להסתכל עליה באופן הבא, המקור מחובר ל u, u מתחברת ל v ול v ישנו קודקוד מקביל בצד של s המחובר באמצועת קשת e_2 ל קודקוד k וכך הלאה עד שאין קודקוד מתאים בצד של המקור ברשת הזרימה, לאחר מכן מחברים את נק' זו לבור של הרשת.
• ממשיכים לבנות מסלולים באופן זה, צריך לשים לב כי אין מעגלים ולכן לא נחזור לאותו קודקוד פעמיים.

מכיוון שמדובר ברשת זרימה נשתמש בתכונות של רשת זרימה עם שינויים אלה ונמצא זרימה מקס', אופן המעבר על הרשת:

1. מתחילים מהקודקוד הראשון (לא באמת משנה) נשתמש ב e(u,v) המחוברת לקשת e_2(v,k) מתחילים מהמקור ל u ואז עוברים ל v ואת v מחברים למקור, לאחר מכן ממשיכים לקודקוד הבא שהוא v ומשם ל k המתחבר לבור וכך הלאה עד לעצירה.
2. נריץ את אלג' פורד פלקרסון עם העדכון שתיארנו לגילוי זרימה מקס' ברשת וכך נמצא את כלל המסלולים הזרים המקיימים את התנאים המתוארים.

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