Consider the flow x’ at the end of

Consider the flow x’ at the end of a ∆-scaling phase and let S be the set of nodes reachable
from node s in G(x’, ∆). That is, there exist flow augmenting paths from s to the nodes in S whereas there is no flow augmenting path from s to any node in S. From the definition of S, we know that the residual capacity of every arc in G(x’, ∆ ) must be less than ∆ . Thus, the residual capacity of the cut (S, S ) is at most m ∆ . In the next scaling phase, each augmentation carries at least ∆ /2 units of flow. As a result, there are at most 2m such augmentations. The labeling requires O(m) time to identify an augmenting path and push flow over the path. Therefore, the complexity is O( 2 m log U). Example: original network residual network

Results (Thai) 1:

พิจารณาการไหล x' จบเฟส∆ปรับให้ S เป็น ชุดของโหนดที่สามารถเข้าถึง จาก s โหนใน G (x', ∆) กล่าวคือ มีไหลอีกเส้นทางจาก s ไปยังโหนในขณะที่มีกระแสไม่อีกเส้นทางจาก s ไปยังโหนดใด ๆ ใน s ได้ จากคำนิยามของ S เรารู้ว่ากำลังการผลิตส่วนที่เหลือของทุกโค้งใน G (x', ∆) ต้องน้อยกว่า∆ ดังนั้น กำลังการผลิตเหลือตัด (S, S) ได้มากที่สุด m ∆ ในมาตราส่วนเฟสถัดไป เพิ่มเติมแต่ละดำเนินการน้อย∆ /2 หน่วยของกระแส ส่งผล มีมากที่สุด 2 เมตร augmentations ดังกล่าว การติดฉลากต้อง O(m) เวลาระบุลำดับเส้นทางและผลักดันการ augmenting ผ่านเส้นทาง ดังนั้น ความซับซ้อนเป็น O (2 m ล็อก U) ตัวอย่าง: เดิมเหลือข่ายเครือข่าย

Results (Thai) 2:

พิจารณาการไหล x 'ในตอนท้ายของเฟสΔ-ปรับและปล่อยให้ S
เป็นชุดของโหนดสามารถเข้าถึงได้จากs โหนดใน G (x' Δ) นั่นคือมีอยู่ไหลขยายเส้นทางจากที่จะโหนดใน S ในขณะที่ไม่มีการไหลขยายเส้นทางจาก s ไปยังโหนดใด ๆ ในเอสจากความหมายของ S ที่เรารู้ว่ากำลังการผลิตที่เหลือของส่วนโค้งทุกคนใน G (x ' , Δ) ต้องน้อยกว่าΔ ดังนั้นความจุที่เหลือของการตัด (S, S) เป็นอย่างมากมΔ ในขั้นตอนการปรับต่อไป, เสริมแต่ละดำเนินการอย่างน้อยΔ / 2 หน่วยของการไหล เป็นผลให้มีที่ดังกล่าวมากที่สุด 2m augmentations ติดฉลากต้องใช้ O (เมตร) เวลาในการระบุเส้นทาง augmenting และการไหลของการผลักดันในช่วงเส้นทาง ดังนั้นความซับซ้อนเป็น O (2 ม. ล็อก U) ตัวอย่าง: เครือข่ายเครือข่ายเดิมที่เหลือ

Results (Thai) 3:

พิจารณาการไหล x ' ในตอนท้ายของ∆ - ปรับระยะ และให้เป็นชุดของโหนดสามารถเข้าถึง
จากโหนดใน g ( x ' ∆ ) นั่นคือ มีการแต่งเติมโหนดในเส้นทางจาก s s ในขณะที่ไม่มีการแต่งเติมใด ๆเส้นทางจากโหนดใน S . จากนิยามของ S , เรารู้ว่าความจุคงเหลือของทุกโค้งใน g ( x ' ∆ ) ต้องน้อยกว่า∆ . ดังนั้นความจุที่เหลือของตัด ( s , s ) M ∆มากที่สุด . ในขั้นตอนการปรับต่อไป แต่ละเสริมประกอบอย่างน้อย∆ / 2 หน่วยของการไหล เป็นผลให้มี augmentations เช่น 2 มากที่สุด การติดฉลากต้องมี O ( M ) เวลาที่จะระบุวิถีแต่งเติมและดันไหลเหนือเส้นทาง ดังนั้นความซับซ้อนคือ O ( log 2 m U ) ตัวอย่าง : ต้นฉบับเครือข่ายตกค้าง