204512/บรรยาย 13 - ประวัติรุ่นแก้ไข

203.113.85.18: /* ปัญหา Vertex Cover */

2010-10-07T03:14:15Z

ปัญหา Vertex Cover

Therawat: /* ปัญหา 3-Color */

2007-10-12T14:48:45Z

ปัญหา 3-Color

Therawat: /* ปัญหา 3-Color */

2007-10-12T14:22:15Z

ปัญหา 3-Color

Therawat: /* ปัญหา 3-Color */

2007-10-12T14:06:01Z

ปัญหา 3-Color

Therawat: /* ปัญหา Independent Set */

2007-10-12T13:51:07Z

ปัญหา Independent Set

58.64.70.209: /* ปัญหา Independent Set */

2007-10-12T13:21:58Z

ปัญหา Independent Set

58.64.70.209: /* ปัญหา 3-Color */

2007-10-12T12:56:45Z

ปัญหา 3-Color

58.64.70.209: /* ปัญหา 3-Color */

2007-10-12T12:56:04Z

ปัญหา 3-Color

58.64.70.209: /* ปัญหา 3-Color */

2007-10-12T12:39:08Z

ปัญหา 3-Color

58.64.70.209: /* ปัญหา 3-Color */

2007-10-12T12:38:37Z

ปัญหา 3-Color

@@ แถว 130: / แถว 130: @@
 === ปัญหา Vertex Cover ===
-เซต <math>\mathbf{C}</math> เป็น Vertex Corner ของกราฟ <math>\mathbf{G} = (\mathbf{V},\mathbf{E})</math> ถ้า <math>C \subseteq V</math> และทุกๆ edge <math>(U,V) \in E, U \in C</math> หรือ <math> V \in C</math><br/>
+เซต <math>\mathbf{C}</math> เป็น Vertex Corver ของกราฟ <math>\mathbf{G} = (\mathbf{V},\mathbf{E})</math> ถ้า <math>C \subseteq V</math> และทุกๆ edge <math>(U,V) \in E, U \in C</math> หรือ <math> V \in C</math><br/>
-ปัญหา Vertex Corner จะให้กราฟ <math>\mathbf{G}</math>, integer k ถามว่า <math>\mathbf{G}</math> มี vertex corner ที่มีขนาด <math>\le</math> k หรือไม่ ?<br\>
+ปัญหา Vertex Corver จะให้กราฟ <math>\mathbf{G}</math>, integer k ถามว่า <math>\mathbf{G}</math> มี vertex corver ที่มีขนาด <math>\le</math> k หรือไม่ ?<br\>
-*Independent set <math>\le_p</math> Vertex Corner<br\>
+*Independent set <math>\le_p</math> Vertex Corver<br\>
 **'''Lemma''' พิจารณากราฟ <math>\mathbf{G} = (\mathbf{V},\mathbf{E}), I \subseteq V</math> เป็น Independent Set<br/>
 (รูปภาพ)
 <br/>
 รับกราฟ <math>\mathbf{G}</math> ถามว่ามี independent set <math>\le</math> k ?
-สร้าง instance ของ Vertex Corner ที่มีกราฟ <math>\mathbf{G}</math> ถามว่าใน <math>\mathbf{G}</math> มี Vertex Corner ขนาด n-k หรือไม่ ? เมื่อ n = จำนวนโหนดใน <math>\mathbf{G}</math><br\>
+สร้าง instance ของ Vertex Corver ที่มีกราฟ <math>\mathbf{G}</math> ถามว่าใน <math>\mathbf{G}</math> มี Vertex Corver ขนาด n-k หรือไม่ ? เมื่อ n = จำนวนโหนดใน <math>\mathbf{G}</math><br\>
 <br/>
-Vertex Corner เป็น NP Complete เนื่องจากสามารถตรวจได้ว่ากราฟมี Vertex Corner ขนาดไม่เกิน k โดยใช้ Certificate เป็น Vertex Corner นั้น <math>\Rightarrow VC \in NP</math>
+Vertex Corver เป็น NP Complete เนื่องจากสามารถตรวจได้ว่ากราฟมี Vertex Corver ขนาดไม่เกิน k โดยใช้ Certificate เป็น Vertex Corver นั้น <math>\Rightarrow VC \in NP</math>
 === ปัญหา 3-Color ===

@@ แถว 155: / แถว 155: @@
 :ถ้าให้ clause <math> X_1 \lor \neg X_2 \lor X_3</math> ต้องสร้างกราฟให้มีตัวใดตัวหนึ่งเป็นจริงและอีก 2 ตัวเป็น false ได้กราฟดังนี้<br/>
 [[ภาพ:3-Color3.jpg]]<br/>
-*กราฟนี้จะบังคับให้ต้องมีตัวใดตัวหนึ่งเป็น True
+:กราฟนี้จะบังคับให้ต้องมีตัวใดตัวหนึ่งเป็น True นั่นคือ <math>3-Color \le_p 3-SAT</math><br/>

@@ แถว 152: / แถว 152: @@
 . แสดงว่า <math>3-Color \le_p 3-SAT</math><br/>
 :กำหนดโหนด 3 โหนดแทนสี 3 สี จากนั้นสร้างกราฟดังนี้<br/>
-(รูปภาพ)<br/>
+[[ภาพ:3-Color2.jpg]]<br/>
 :ถ้าให้ clause <math> X_1 \lor \neg X_2 \lor X_3</math> ต้องสร้างกราฟให้มีตัวใดตัวหนึ่งเป็นจริงและอีก 2 ตัวเป็น false ได้กราฟดังนี้<br/>
-(รูปภาพ)<br/>
+[[ภาพ:3-Color3.jpg]]<br/>
 *กราฟนี้จะบังคับให้ต้องมีตัวใดตัวหนึ่งเป็น True

@@ แถว 143: / แถว 143: @@
 === ปัญหา 3-Color ===
 ให้กราฟ <math>\mathbf{G}</math> ต้องการกำหนดสีให้กับแต่ละโหนด โดยที่คู่ของโหนดที่มีเส้นเชื่อมถึงกันห้ามใช้สีเดียวกัน สามารถทำได้โดยใช้สี <math>\le</math> 3 สีหรือไม่ ?<br/>
-(รูปภาพ)<br/>
+[[ภาพ:3-Color.jpg]]<br/>
 จะแสดงว่า 3-Color เป็น NP Complete<br/>
 . แสดงว่า <math>3-Color \in NP</math>

@@ แถว 112: / แถว 112: @@
 *สำหรับโหนดที่แทนตัวแปรกับนิเสธของตัวแปรเดียวกับเพิ่มเส้นเชื่อมระหว่างโหนดเหล่านี้<br/><br/>
 :::<math>(X_1 \lor X_2 \lor X_3) \land (\neg X_1 \lor X_2 \lor \neg X_4) \land (X_4 \lor \neg X_3 \lor \neg X_2)</math>
-(รูปภาพ)<br/>
+[[ภาพ:3-SAT.jpg]]<br/>
 :::ถ้า <math>\boldsymbol{\phi} \in 3-SAT</math> จะมี independence set ขนาด m ใน G
 :::ถ้ามี independence set ขนาด m ใน G <math>\Rightarrow \boldsymbol{\phi} \in 3-SAT</math>

@@ แถว 103: / แถว 103: @@
 === ปัญหา Independent Set ===
 นิยาม ให้ Undirected graph G = (V,E) จะกล่าวว่า <math>I \subseteq V</math> เป็น Independent Set ถ้าทุกๆ คู่ของโหนด <math>U, V \subseteq I</math> ไม่มีเส้นเชื่อมกัน<br/>
-(รูปภาพ)<br/>
+[[ภาพ:independent_set.jpg]]<br/>
 ปัญหา Independent set ให้กราฟ G = (V,E) และ integer k, มี Independent set I ใน G ที่ <math>|I| \ge k</math> หรือไม่ ?<br/>
 เราสามารถลดรูปปัญหา 3-SAT ไปเป็นปัญหา Independent set ได้<br/><br/>

@@ แถว 149: / แถว 149: @@
 ::1) ใช้สีไม่เกิน 3 สี
 ::2)ไม่มี edge เติมโหนดที่มีปัญหาทำได้ polynomial time
-::ซึ่งสามารถทำได้ใน Polynomail time
+::ซึ่งสามารถทำได้ใน polynomial time
 (รูปภาพ)