קיבול חתך מינימלי

[lionsh]

קיבול חתך מינימלי

הגעתי למסקנה שהפתרון לשאלה שנשאלתי (על רשתות זרימה) הוא מציאת קיבול חתך מינימלי והחזרת הקשתות/קודקודים שלו. השאלה שלי היא איך ובאיזו סיבוכיות מוצאים חתך מינימלי? ידוע שחתך מינימלי = זרימה מקסימלית. וזרימה אני יודע למצוא. השאלה ע"י איזה אלגוריתם קיים או חדש ניתן למצוא את החתך המינימלי. תודה מראש,

 

[gil levi]

איזה קטע.

אתמול עברתי על השאלה הזו. ובכן, תעניין בהוכחה של max-flow min cut theorem. שם השתמשו בחתך (S,T) כאשר S הם כל הקודקודים שנגישים מs (המקור) בGf, את אלו אתה יכול למצוא על ידי BFS בGf.

 

[lionsh]

תודה, חשדבתי על הפתרון הזה

אתה מתכוון לDFS. ובטח לומד באו"פ...

 

[ron369]

דווקא את"א

 

[gil levi]

למה חייבים DFS?

גם BFS מוצא את הקודקודים שלא נגישים מהמקור. שכחתי לכתוב: T=V-S. וכמו שרון כתב, אני לומד באת"א.

 

[vinney]

למה דווקא DFS?

 

[lionsh]

תכל'ס, לא ממש משנה

פשוט קראתי איפה שהוא על פתרון לבעייה והשתמשו בDFS דווקא.