|
|
| (ไม่แสดง 17 รุ่นระหว่างกลางโดยผู้ใช้ 10 คน) |
| แถว 1: |
แถว 1: |
| − | ==Network Flows==
| + | Smack-dab what I was loonkig for-ty! |
| − | ===Flows,Cuts,Augmenting paths===
| |
| − | | |
| − | หาการไหลของ flow ที่มีขนาดมากที่สุด จะเท่ากับขนาดของ flow
| |
| − | <br>
| |
| − | | |
| − | [[ภาพ:N01.PNG]]
| |
| − | | |
| − | <br>
| |
| − | ให้กราฟมีทิศทาง <math>G = (V,E)</math><br>
| |
| − | ฟังก์ชันความจุ cap :<math>VxV \to R^ +</math> และ s,t ∈ V<br>
| |
| − | ฟังก์ชัน f : <math>VxV \to R</math> จะเรียกว่าเป็น flow <br>
| |
| − | ถ้า<br>
| |
| − | i) สำหรับทุกๆคู่ u,v : <math>f(u,v) \le cap(u,v)</math> [Capacity Constraint]<br>
| |
| − | | |
| − | ii)สำหรับทุกๆ u,v : <math>f(u,v) = -f(u,v)</math> [Skew Symmetry]<br>
| |
| − | | |
| − | iii)สำหรับทุกๆ <math>{\rm u } \notin {\rm \{ s,t\} , }\sum\limits_{{\rm v} \in {\rm V}} {{\rm f(u,v) = 0}}
| |
| − | </math> [Flow conservation Constraint]<br>
| |
| − | | |
| − | <u>ขนาดของ flow f</u> ,|f|, คือ<br>
| |
| − | <br>
| |
| − | <math>\sum\limits_{v \in V} {f(s,v)}
| |
| − | </math><br>
| |
| − | <br>
| |
| − | มี Flow s-t
| |
| − | <br>
| |
| − | [[ภาพ:N02.PNG]]
| |
| − | <br>
| |
| − | จะเรียก <math>(x,\bar x)</math> ว่าเป็น s-t cut ถ้า <math>s \in x,t \in \bar x
| |
| − | </math> และ <math>\bar x = v - x</math><br>
| |
| − | | |
| − | สำหรับ cut <math>(x,\bar x)</math>,<math>f(x,\bar x) = \sum\limits_{u \in x} {\sum\limits_{v \in \bar x} {f(u,v)} }</math><br>
| |
| − | <br>
| |
| − | | |
| − | '''<u>Lemma</u>''' : สำหรับทุกๆ s-t cut <math>(x,\bar x),f(x,\bar x) = |f|</math><br><br>
| |
| − | '''<u>Proof</u>''' : <math>f(x,\bar x) = \sum\limits_{u \in x} {\sum\limits_{v \in \bar x} {f(u,v) = \sum\limits_{u \in x} {\sum\limits_v {f(u,v) - \sum\limits_{u \in x} {\sum\limits_{v \in x} {f(u,v)} } } } } } </math><br>
| |
| − | | |
| − | :::::= <math>\sum\limits_v {f(s,v) = |f|}</math><br>
| |
| − | <br>
| |
| − | flow ที่หน้าตัดใดๆ เท่ากับ Flow ที่ออกจาก soure นั้นๆ<br>
| |
| − | <br>
| |
| − | สำหรับ cut <math>(x,\bar x)</math> ใด ๆ ให้ <math>cap(x,\bar x) = \sum\limits_{u \in x} {\sum\limits_{v \in \bar x} {cap(u,v)} }</math><br>
| |
| − | <br>
| |
| − | '''<u>Lemma</u>''' : สำหรับ s-t cut <math>(x,\bar x)</math> ใดๆ และ flow f ใดๆ <br>
| |
| − | ::<math>|f| = f(x,\bar{x})\le cap(x,\bar{x})</math><br>
| |
| − | '''<u>Proof</u>''' : ลองคิดเอง???<br><br>
| |
| − | | |
| − | '''Ford-Fulkerson'''<br>
| |
| − | <br>
| |
| − | [[ภาพ:N03.PNG]]
| |
| − | <br>
| |
| − | สำหรับ flow f , capacity บนเส้นเชื่อม (u,v) ใน Residual graph R<sub>f</sub> ของ f เท่ากับ <br>
| |
| − | ::<math>cap(u,v) - f(u,v) \equiv r_f (u,v)</math><br>
| |
| − | <br>
| |
| − | ให้ R<sub>f</sub> มีเฉพาะเส้นเชื่อมที่มี capacity เป็นบวก <br>
| |
| − | flow f เป็น maximum flow ถ้า |f| มากที่สุด<br><br>
| |
| − | '''<u>Lemma</u>''' : ถ้า f* เป็น maximum flow, f เป็น flow ใดๆ แล้ว <br>
| |
| − | :::f'=f*-f จะเป็น flow ใน R<sub>f</sub> เมื่อ f'(x,y)=(f*-f)(x,y)=f*(x,y)-f(x,y)<br><br>
| |
| − | '''<u>Proof</u>''' : check
| |
| − | :::capaciy constraint <math>\forall \cup v,f(u,v) \le cap(u,v)</math><br>
| |
| − | :::skew symmetry <math>\forall \cup v,f(u,v) = - f(u,v)</math><br>
| |
| − | :::conservation <math>\forall v \notin \{ s,t\} ,\sum\limits_w {f(v,w) = \emptyset }</math><br>
| |
| − | | |
| − | :ตรวจสอบ capacity constraint พิจารณา (u,v)<br>
| |
| − | :::<math>f'(u,v) = f^* (u,v) - f(u,v)\le cap(u,v) - f(u,v) = r_f (u,v)</math><br>
| |
| − | | |
| − | ===Flow Augmenting Step===
| |
| − | | |
| − | เรียก path ใน R<sub>f</sub> จาก s ไป t ว่าเป็น augmenting path <br>
| |
| − | :1. <math>f \leftarrow \emptyset</math>
| |
| − | :2. คำนวณ R<sub>f</sub>
| |
| − | :3. หา augmenting path P ∈ R<sub>f</sub>
| |
| − | :4. ถ้าหาไม่ได้ จบ
| |
| − | :5. ให้ <math>C = \min _{e \in P} r_f (e)</math>
| |
| − | :6. ปรับค่า f ด้วย flow บน path p ที่มีขนาด C
| |
| − | :7. กลับไป step2
| |
| − | <br>
| |
| − | | |
| − | '''<u>Theorem</u>''' : ถ้า FF จบ, จะมี s-t cut <math>(x,\bar x)</math> ที่ <math>|f| = cap(x,\bar x)</math> นั่นคือ f เป็น maximum flow<br>
| |
| − | <br>
| |
| − | '''<u>Proof</u>''' : ถ้ามี cut ดังกล่าว f เป็น maximum flow <br>
| |
| − | พิจารณา <math>R_f</math> เนื่องจาก FF terminate ไม่มี path จาก s ไป t ใน <math>R_f</math><br>
| |
| − | | |
| − | [[ภาพ:N04.PNG]]
| |
| − | | |
| − | :<math>x = \{ v \in V|</math> มี path จาก s ไป v ใน <math>R_f \}</math> จะได้ว่า <math>x \notin t</math><br>
| |
| − | <br>
| |
| − | :1. จะแสดงว่า f(u,v)=0 สำหรับทุกๆ <math>u \in \bar x,v \in x</math><br>
| |
| − | :::Proof by Condition สมมติให้มี <math>u \in \bar x,v \in x</math> ที่ f(u,v) > 0<br>
| |
| − | :::นั่นคือ <math>r_f (v,u) = cap(v,u) - f(v,u)</math><br>
| |
| − | ::::::<math>= cap(v,u) + f(u,v) > 0</math><br>
| |
| − | :::และจะมีเส้นเชื่อม (v,u)ใน <math>R_f \Rightarrow u \in X</math> เป็นข้อขัดแย้ง
| |
| − | :::เพราะฉะนั้น 1)เป็นจริง
| |
| − | :2. สำหรับทุกๆ <math>u \in x,v \in \bar x,f(u,v) = cap(u,v)</math>
| |
| − | :::-> ถ้า f(u,v) < cap(u,v)
| |
| − | ::::<math>r_f (v,u) > 0</math> และ <math>v \in x</math> ซึ่งเป็น controdiction
| |
| − | :::>>><math>f(x,\bar x) = \sum\limits_{u \in x} {\sum\limits_{v \in \bar x} {f(u,v) = } } \sum\limits_{u \in x} {\sum\limits_{v \in \bar x} {cap(u,v) = cap(x,\bar x)} } </math>
| |
| − | '''<u>Cor</u>''' cut <math>{(x,\bar x)}</math> ข้างต้น เป็น cut ที่มีค่า <math>{cap(x,\bar x)}</math> น้อยที่สุด
| |
| − | :นั่นคือ <math>{(x,\bar x)}</math> เป็น maximum cut
| |
| − | | |
| − | ===Ford-Fulkerson Algorithm===
| |
| − | '''<u>Ex</u>'''
| |
| − | <br>
| |
| − | [[ภาพ:N05.PNG]] n=|v|, m=|E|
| |
| − | | |
| − | | |
| − | ==Running Time==
| |
| − | - ถ้ากราฟมี n โหนด m edges แต่ละ augmenting step ใช้เวลา O(m)
| |
| − | :ถ้า <math>c = |f^* |</math>, augment ไม่เกิน c รอบ เพราะแต่ละรอบขนาดของ flow จะเพิ่มขึ้น 1
| |
| − | ::-> FF ทำงานในเวลา O(mC)
| |
| − | :: *FF ไม่ใช่ Polynomial-time Algorithm
| |
| − | [[ภาพ:N06.PNG]]
| |
| − | | |
| − | ==Bipartite Matching==
| |
| − | | |
| − | กราฟ <math>G=(V,E)</math> เป็น bipartite graph ถ้าสามารถแบ่ง V ออกเป็น A&B ที่ <math>A \cap B = \emptyset ,A \cup B = V</math><br>
| |
| − | และไม่มี <math>edge(u,v) \in E</math> ที่ <math>u \in A,v \in A</math> หรือ <math>u \in B,v \in B</math><br>
| |
| − | | |
| − | | |
| − | ให้ <math>G=(A \cup B ,E)</math> เป็น bipartite graph <br>
| |
| − | [[ภาพ:N07.PNG]]
| |
| − | | |
| − | | |
| − | ให้กราฟ <math>G = (A \cup B,E)</math> เซต <math>m \le E</math> เป็น '''<u>matching</u>'''(การจับคู่) ถ้าไม่มีโหนดใดๆ G ที่ติดกับ edge ใน m มากกว่า 1 edge<br>
| |
| − | [[ภาพ:N08.PNG]]
| |
| − | <br>
| |
| − | '''Edmonds-Karp'''<br>
| |
| − | - หา shortest augmenting path ('''การบ้าน''')<br>
| |
| − | ::poly(m,n) -> strong poly-time<br>
| |
| − | - หา augmenting path ที่ augment ได้มากที่สุด<br>
| |
| − | ::poly(m,n,logC) -> weakly poly-time<br>
| |
| − | <br>
| |
| − | '''<u>Flow decomposition</u>'''
| |
| − | ::สำหรับ flow f ใดๆ มีวิธี augment ที่ไม่เกิน m ครั้งที่ทำให้ได้ flow ขนาด |f|<br>
| |
| − | <br>
| |
| − | <math>f^*</math> maximum flow<br>
| |
| − | f -> <math>R_f</math> ที่มี maximum flow ขนาด <math>|f^* | - |f|</math>, path ที่ augment มีขนาด <math>\ge \frac{{|f^* | - |f|}}{{2m}}</math><br>
| |
| − | m คือ edge ขณะนั้น<br>
| |
| − | <br>
| |
| − | พิจารณาลำดับการ augment 2m รอบติดกัน -> ได้ flow เป็น f <br>
| |
| − | :<u>case 1</u> : <math>|f^* | - |f'| \le \frac{1}{2}(|f^* | - |f|)</math>
| |
| − | :<u>case 2</u> : <math>|f^* | - |f'| \ge \frac{1}{2}(|f^* | - |f|)</math>
| |
| − | ::นั่นคือ ในทุกๆ การ augment จะ augment ได้ <math>\frac{1}{2}(\frac{{|f^* | - |f|}}{{2m}})</math>
| |
| − | <br>
| |
| − | อย่างไรก็ตาม augment ไป 2m รอบ<br>
| |
| − | ขนาดของ flow ทั้งหมดที่ augment <math>2m \bullet \frac{1}{2}(\frac{{|f^* | - |f|}}{{2m}})</math><br>
| |
| − | ::นั่นคือ มี flow เหลือ <math>\le (|f^* | - |f|) - \frac{1}{2}(|f^* | - |f|) = \frac{1}{2}(|f^* | - |f|)</math> ซึ่งเป็น contradiction<br>
| |
| − | <math>\Rightarrow</math>ทุกๆ 2m augmentation, flow ใน residual graph ลดลงอย่างน้อยครึ่งหนึ่ง<br>
| |
| − | -> augment ไม่เกิน O(mlogC)รอบ<br>
| |
