204512-53/lecture8

บันทึกคำบรรยายวิชา 204512-53 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

Algorithm Lecture #8 จดบันทึกคำบรรยายโดย:

นาย บดินทร์ แสงทองล้วน 5314550113

นาย วิชา มีสุขสบาย 5314550164

นาย อภิชาติ ทวีศิริเวทย์ 5314550199

---

Network flow problem

1. กราฟมีทิศทาง

2. ความจุ (capacity) $\ c:E\rightarrow \mathbb {R+}$

3. จุดเริ่มต้น source $\ s\in V$

4. จุดสิ้นสุด sink $\ t\in V$

5. flow เป็น function จาก $V\times V\rightarrow \mathbb {R}$

เงื่อนไข

1. Capacity constraints : $\ f\leq c(u,v)$

2. Skew symmetry : $\ f(u,v)=-f(v,u)$

3. conservation : $\ \sum _{V}f(u,v)=0$

ปริมาตร flow $|f|=\ \sum _{V}f(u,v)=0$

Maximum flow problem

Maximum flow problem: ปัญหาการหาปริมาณการไหลสูงสุด ซึ่งเป็นหนึ่งในปัญหาเน็ตเวิร์คโฟล์วที่น่าสนใจ

สัญลักษณ์ที่เกี่ยวข้อง

G คือ กราฟที่เราสนใจ

G = (V,E) คือ ฟังก์ชั่นของกราฟ G โดยที่ V คือ เซตของโหนด และ E คือเซตของเส้นเชื่อม

C: E->R+ คือ Capacity ของเส้นเชื่อม เซตจำนวนจริงบวกไม่รวมศูนย์ (0, +∞)

s-t คือ เซตของเส้นทางจาก s ไปถึง t

Maximum flow คือโจทย์หนึ่งของเน็ตเวิร์คโฟล์วโจทย์นี้ต้องการหาค่ามากที่สุดของโฟล์ว จากต้นทาง(s) ที่ส่งได้ไม่เกินความจุของเส้นเชื่อม(u) แต่ละเส้น เพื่อให้ได้ค่ารวมมากที่สุดจากต้นจนถึงปลายทาง (t)

Classic problem

Maximum flow คือเท่าไหร่ : ต้องหา path มาเรื่อยๆ จนไม่มี path

หรือ

ถ้าได้รูปแบบข้างต้นก็ไม่มีปัญหา แต่ถ้าเกิดได้แบบ

จะกลายเป็นปัญหา แล้วจะแก้ไขอย่างไร?

แนวคิด

Algorithm

1. F <- 0
2. G(f) เป็น residual graph ของ f
3. ถ้ามี path จาก s ไป t ใน G(f)
4. P <- path จาก s ไป t ใน G(f)
5. C <- capacity ต่ำสุดของเส้นเชื่อมใน path P
6. Update f ด้วย flow path P ด้วยปริมาตร C
7. หา G(f) <- residual graph ของ flow f

st-cut

พิจารณา sub set ของ node กลุ่มหนึ่ง

ถ้า $s\in S,t\notin S$ จะเรียก $(S,{\bar {S}})$ ว่า st-cut ;

cut ที่ตัด s กับ t ออกจากกัน

เราสนใจ edge ทั้งหมดที่ข้ามจาก s ไป t

1) นิยาม

          $Cap(u,{\bar {v}})=\sum \limits _{u\in S,v\in {\bar {S}}}{C(u,v)}$

Flow ใดๆเราพิจารณาการส่ง volumeจาก s ไป t

ถ้าเราพิจารณา volume ที่วิ่งผ่าน cut ต้องเท่ากับ volume ที่ออกจาก S

2) นิยาม

           $f(S,{\bar {S}})$ ; flow ที่วิ่งจาก $S\Rightarrow {\bar {S}}$ ทั้งหมดเลย

flow สามารถวิ่งไปและวิ่่งกลับได้

สำหรับ st-cut ใดๆ เราได้ว่า

$f(S,{\bar {S}})\leq Cap(S,{\bar {S}})$

เราจะพิสูจน์

$|f|=f(S,{\bar {S}});|f|$ คือ Volume ของ f

พิสูจน์

$|f|=f(S,{\bar {S}})$ สำหรับ st-cut S ใดๆ

พิสูจน์

${S}=S_{0}\supset S_{1}\supset S_{2}\supset S_{3}\subset S_{4}\subset \ldots \subset S_{k}$

$f(S,{\bar {S}})=|f|$ สำหรับทุกๆ $0\leq i\leq k$

พิสูจน์ โดย Induction ตั้งแต่ 0 ถึง k

$f(S_{0},{\bar {S}}_{0})=|f|$ เป็น base case ซึ่งจะเท่ากันตามนิยาม

เราจะพิสูจน์ว่า

$f(S_{i+1},{\bar {S}}_{i+1})=|f|$

ได้ $S_{i}$ มี flow ที่วิ่งเข้าวิ่งออกของ c กับ d สุดท้ายรวม flow เส้นปะเข้า

ไปเราได้ว่า

$a+c=|f|$

เนื่องจากเรารู้ว่า

$c+d=0$

$c=-d$

$d=-b$

$c=b$

$a+c=|f|$

Claim(1)

               $f(S,{\bar {S}})\leq Cap(S,{\bar {S}})$

Claim(2)

               $|f|=f(S,{\bar {S}})$

Ford-Fullerson

สำหรับ st-cut ใดๆ

$|f|=Cap(S,{\bar {S}})$

เราพิจารณา flow มีขนาดเท่ากับ cut ใดๆ แปลว่า flow นั้นมีขนาดใหญ่สุด

เราสามารถพิสูจน์ต่อได้ว่า flow ที่มีขนาดเท่ากับ $Cap(S,{\bar {S}})$ เราจะได้ flow ที่มีขนาดใหญ่ที่สุด

พิสูจน์ว่า

flow f ที่ out-put โดย Ford-Fullerson เป็น maximum flow

หา s-t cut $(S^{*},{\bar {S}}^{*})$ ที่ $Cap(S^{*},{\bar {S}}^{*})$

เราต้องการ $|f|=f(S^{*},{\bar {S}}^{*})=Cap(S^{*},{\bar {S}}^{*})$

พิสูจน์

1) flowต้องเต็ม

2) edgeที่วิ่งกลับต้องไม่มีflowเลย

เราพิสูจน์โดย By Contradition

พิจารณา e=(u,v) ที่ $u\in S^{*};v\in {\bar {S}}^{*}$

Claim

       $f(u,v)=c(u,v)$

ถ้าไม่เท่ากัน flow จะไม่เต็ม เท่ากับว่ามี path อีก 1 path ใน residual graph เพราะฉะนั้น $f(u,v)=c(u,v)$ เป็นจริง

สิ่งที่เราได้นอกจากจะได้ max flow เราจะได้ min cut เพราะ max flow = min cap

เวลาในการทำงาน

ความคืบหน้าของมันคือจำนวน |f| เพิ่มขึ้นเรื่อยๆ แต่ต้องมันใจว่าไปถึง max flow ไม่ใช่เพิ่มขึ้นน้อยลงเรื่อยก็ไม่มีทางไปถึง

m คือจำนวน edge, n คือ จำนวน node; ทำทั่วไป $O(n+m)$ ; หา path $O(n+m)$ ;

ถ้า Capacity เป็น integer จำนวนรอบที่ใช้จะเท่ากับจำนวนของ max flow

ตัวอย่างที่ Fold-Fullerson ล้มเหลว

Bipatite Matching

ปัญหาที่สามารถมองเป็น max flow ได้

กราฟ G จะเรียกว่าเป็น Bipatite graph ถ้า set ของ vertex V สามารถแบ่งเป็น

A,B ที่ $A\bigcup B=V;A\bigcap B=\emptyset$

แล้วไม่มีเส้นเชื่อม (u,v) ที่ $u\in A,V\in A$ หรือ $u\in B,V\in B$

เซต $M\subseteq E$ เรียกว่าเป็น matching ถ้าไม่มีโหนดใดๆ ติดกับเส้นเชื่อม M เกิน 1 เส้น

ปัญหา Bipartite Matching

สมมุติว่า มีคน n คน ซื้อกับข้าว n ห่อ เส้นเชื่อมที่โยงไปคือ ที่สามารถกินข้าวห่อได้ ทำอย่างไรให้ทุกคนได้กินข้าวห่อ

สร้าง Supernode S กับSupernode T ใส่ทิศทางและ Capasity

หาคำตอบในกราฟนี้โดยใช้ maxflow จะ work ได้ maxflow ต้องเป็นจำนวนเต็ม