204512-53/lecture8 - ประวัติรุ่นแก้ไข

158.108.233.60 เมื่อ 07:00, 24 กันยายน 2553

2010-09-24T07:00:48Z

158.108.233.60 เมื่อ 06:41, 24 กันยายน 2553

2010-09-24T06:41:07Z

KenMay เมื่อ 10:49, 23 กันยายน 2553

2010-09-23T10:49:52Z

KenMay เมื่อ 10:14, 23 กันยายน 2553

2010-09-23T10:14:40Z

Poipy เมื่อ 09:27, 23 กันยายน 2553

2010-09-23T09:27:32Z

Poipy เมื่อ 09:20, 23 กันยายน 2553

2010-09-23T09:20:25Z

Poipy เมื่อ 09:15, 23 กันยายน 2553

2010-09-23T09:15:48Z

Poipy เมื่อ 09:15, 23 กันยายน 2553

2010-09-23T09:15:16Z

Poipy เมื่อ 09:11, 23 กันยายน 2553

2010-09-23T09:11:09Z

Poipy เมื่อ 09:08, 23 กันยายน 2553

2010-09-23T09:08:51Z

@@ แถว 13: / แถว 13: @@
 =Network flow problem=
-In graph theory, a flow network is a directed graph where each edge has a capacity  and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes  and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, except when it is a source, which has more outgoing flow, or sink, which has more incoming flow. A network can be used to model traffic in a road system, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.
+. กราฟมีทิศทาง
 =Maximum flow problem=

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:41, 24 กันยายน 2553
แถว 10:		แถว 10:

	----		----
		+
		+	=Network flow problem=
		+
		+	In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, except when it is a source, which has more outgoing flow, or sink, which has more incoming flow. A network can be used to model traffic in a road system, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.

	=Maximum flow problem=		=Maximum flow problem=

@@ แถว 1: / แถว 1: @@
 '''จดบันทึกคำบรรยายโดย:'''
 นาย บดินทร์ แสงทองล้วน 5314550113
 นาย วิชา      มีสุขสบาย    5314550164
 นาย อภิชาติ  ทวีศิริเวทย์   5314550199
 ----

@@ แถว 1: / แถว 1: @@
 '''จดบันทึกคำบรรยายโดย:'''
-นาย
+นาย บดินทร์ แสงทองล้วน 5314550113
-นาย
+นาย วิชา      มีสุขสบาย    5314550164
-นาย
+นาย อภิชาติ  ทวีศิริเวทย์   5314550199
 ----
@@ แถว 57: / แถว 57: @@
 พิจารณา sub set ของ node  กลุ่มหนึ่ง
 ถ้า <math>  s \in S ,t \notin S </math>   จะเรียก  <math>(S,\bar S)</math> ว่า  st-cut ;
@@ แถว 77: / แถว 78: @@
 S</math> ทั้งหมดเลย
 สำหรับ st-cut ใดๆ เราได้ว่า
@@ แถว 91: / แถว 96: @@
 พิสูจน์
 <math>{S}=S_0 \supset S_1 \supset S_2 \supset S_3 \subset S_4 \subset \ldots \subset
@@ แถว 99: / แถว 106: @@
 พิสูจน์ โดย Induction ตั้งแต่ 0 ถึง k
 <math>f(S_0,\bar S_0) = |f|</math> เป็น base case ซึ่งจะเท่ากันตามนิยาม
@@ แถว 105: / แถว 114: @@
 <math>f(S_{i+1},\bar S_{i+1}) = |f|</math>
 ได้ <math>S_i</math> มี flow ที่วิ่งเข้าวิ่งออกของ c กับ d สุดท้ายรวม flow เส้นปะเข้า
@@ แถว 147: / แถว 158: @@
 หา s-t cut <math>(S^*,\bar S^*)</math> ที่ <math>Cap(S^*,\bar S^*)</math>
 เราต้องการ <math>|f|= f(S^*,\bar S^*) = Cap(S^*,\bar S^*)</math>
@@ แถว 157: / แถว 170: @@
 เราพิสูจน์โดย By Contradition
 พิจารณา e=(u,v) ที่ <math>u \in S^*;v \in \bar S^*</math>
@@ แถว 167: / แถว 182: @@
 สิ่งที่เราได้นอกจากจะได้ max flow เราจะได้ min cut เพราะ max flow = min cap
 ==เวลาในการทำงาน==
@@ แถว 177: / แถว 194: @@
 ตัวอย่างที่ Fold-Fullerson ล้มเหลว
 ==Bipatite Matching==
@@ แถว 189: / แถว 208: @@
 เซต <math> M \subseteq E </math> เรียกว่าเป็น matching ถ้าไม่มีโหนดใดๆ ติดกับเส้นเชื่อม M เกิน 1 เส้น

@@ แถว 27: / แถว 27: @@
 Maximum flow คือเท่าไหร่ : ต้องหา path มาเรื่อยๆ จนไม่มี path
-[[ไฟล์:Example.jpg]] หรือ [[ไฟล์:Example.jpg]]
+[[ไฟล์:Untitled2.png‎]] หรือ [[ไฟล์:Untitled3.png‎]]
 ถ้าได้รูปแบบข้างต้นก็ไม่มีปัญหา แต่ถ้าเกิดได้แบบ
-[[ไฟล์:Example.jpg]]
+[[ไฟล์:Untitled4.png‎]]
 จะกลายเป็นปัญหา แล้วจะแก้ไขอย่างไร?
@@ แถว 37: / แถว 37: @@
 แนวคิด
-[[ไฟล์:Example.jpg]]
+[[ไฟล์:Untitled5.png‎]]
-[[ไฟล์:Example.jpg]]
+[[ไฟล์:Untitled6.png‎]]
-[[ไฟล์:Example.jpg]]
+[[ไฟล์:Untitled7.png‎]]
 Algorithm

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:20, 23 กันยายน 2553
แถว 36:		แถว 36:

	แนวคิด		แนวคิด
		+
		+	[[ไฟล์:Example.jpg]]

	[[ไฟล์:Example.jpg]]		[[ไฟล์:Example.jpg]]

@@ แถว 48: / แถว 48: @@
 :#	C <- capacity ต่ำสุดของเส้นเชื่อมใน path P
 :#	Update f ด้วย flow path P ด้วยปริมาตร C
-:#	หา G(f) ,_ residual graph ของ flow f
+:#	หา G(f) <- residual graph ของ flow f

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:15, 23 กันยายน 2553
แถว 24:		แถว 24:

	[[ไฟล์:Untitled1.png‎ ]]		[[ไฟล์:Untitled1.png‎ ]]
		+
		+	Maximum flow คือเท่าไหร่ : ต้องหา path มาเรื่อยๆ จนไม่มี path
		+
		+	[[ไฟล์:Example.jpg]] หรือ [[ไฟล์:Example.jpg]]
		+
		+	ถ้าได้รูปแบบข้างต้นก็ไม่มีปัญหา แต่ถ้าเกิดได้แบบ
		+
		+	[[ไฟล์:Example.jpg]]
		+
		+	จะกลายเป็นปัญหา แล้วจะแก้ไขอย่างไร?
		+
		+	แนวคิด
		+
		+	[[ไฟล์:Example.jpg]]
		+
		+	[[ไฟล์:Example.jpg]]
		+
		+	Algorithm
		+	:# F <- 0
		+	:# G(f) เป็น residual graph ของ f
		+	:# ถ้ามี path จาก s ไป t ใน G(f)
		+	:# P <- path จาก s ไป t ใน G(f)
		+	:# C <- capacity ต่ำสุดของเส้นเชื่อมใน path P
		+	:# Update f ด้วย flow path P ด้วยปริมาตร C
		+	:# หา G(f) ,_ residual graph ของ flow f
		+

	=st-cut=		=st-cut=

@@ แถว 23: / แถว 23: @@
 =Classic problem=
-[[ไฟล์:Example.jpg]]
+[[ไฟล์:Untitled1.png‎ ]]
 =st-cut=

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:08, 23 กันยายน 2553
แถว 22:		แถว 22:

	=Classic problem=		=Classic problem=
		+
		+	[[ไฟล์:Example.jpg]]

	=st-cut=		=st-cut=