Question

max_flow

תהא N=(G,s,t,c)N = (G,s,t,c) רשת זרימה בה הקיבולים של כל הקשתות הם מספרים שלמים זוגיים, מלבד קשת אחת, ee, שלה קיבול שלם אי-זוגי. תהא ff זרימת מקסימום בשלמים ברשת ונניח שערכה אי-זוגי.

הוכיחו/הפריכו: ee רוויה.

1

Answers

הטענה נכונה. נשים לב ש-ee חוצה (כל) חתך-st מינימום (אחרת ערך זרימת המקסימום זוגי) ולכן בזרימת מקסימום היא רוויה.

1
Feedback