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

110.76.153.3 เมื่อ 06:42, 12 ตุลาคม 2553

2010-10-12T06:42:07Z

2010-10-11T10:46:54Z

2010-10-11T10:41:08Z

ปัญหา 3-Satisfiability (3-SAT)

2010-10-11T10:34:58Z

2010-10-11T10:27:26Z

2010-10-11T10:11:45Z

2010-10-11T09:54:01Z

2010-10-11T09:49:34Z

2010-10-11T09:43:12Z

2010-10-11T09:39:45Z

@@ แถว 1: / แถว 1: @@
 '''จดบันทึกคำบรรยายโดย:''
    นายชัชพล      นุโยค รหัส 5214550049 (Part I)
    นายสุรเดช      วัฒนอุดมโรจน์ รหัส 5214550324 (Part I)

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

@@ แถว 122: / แถว 122: @@
 == ปัญหา 3-Satisfiability (3-SAT) ==
-  [[ไฟล์:TB-3SAT.jpg]]
-รับค่า CNF Formula <math>\boldsymbol{\phi}</math> ที่แต่ละ clause มีตัวแปร <math>\le</math> 3 ตัว
+[[ไฟล์:TB-3SAT.jpg]]
 ถามว่าทำให้ <math>\boldsymbol{\phi}</math> เป็นจริงได้หรือไม่ ?
 :::กรณี <math>3-SAT \le_p SAT</math>
 ในกรณีนี้เป็นจริงอยู่แล้วเพราะ 3-SAT เป็นกรณีเฉพาะของ SAT แต่เราต้องการพิสูจน์ว่า
@@ แถว 145: / แถว 147: @@
 === ปัญหา Independent Set ===
 นิยาม ให้ Undirected graph G = (V,E) จะกล่าวว่า <math>I \subseteq V</math> เป็น Independent Set ถ้าทุกๆ คู่ของโหนด <math>U, V \subseteq I</math> ไม่มีเส้นเชื่อมกัน<br/>
-[[ภาพ:independent_set.jpg]]<br/>
+[[ภาพ:Independenset.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/>

@@ แถว 119: / แถว 119: @@
 == SAT ==
-   [[ไฟล์:TB-SAT.jpg]]
+   [[ไฟล์:TB-SAT.jpg]] '''Note :''' Clause ที่เป็นการ OR กับของตัวแปรหรือนิเสธของตัวแปร เรียกว่า Disjunction ตัวอย่างเช่น <math>(X_1 \lor X_2)</math>
-== 3-SAT ==
+== ปัญหา 3-Satisfiability (3-SAT) ==
    [[ไฟล์:TB-3SAT.jpg]]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:11, 11 ตุลาคม 2553
แถว 115:		แถว 115:
	เนทาองจาก \|I\| = K , G plus มี Clique ขนาด k 9k,9hv'dki		เนทาองจาก \|I\| = K , G plus มี Clique ขนาด k 9k,9hv'dki
	Proof (<-)		Proof (<-)
		+	[[ไฟล์:TB-CLIQUE1.jpg]]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:54, 11 ตุลาคม 2553
แถว 112:		แถว 112:
	จากนิยามของ G clique , จะได้ว่า (u,v) [[ไฟล์:NPComplete6.gif]] E clique		จากนิยามของ G clique , จะได้ว่า (u,v) [[ไฟล์:NPComplete6.gif]] E clique
	ดังนั้นทุกๆ u,v [[ไฟล์:NPComplete6.gif]] I ที่ u[[ไฟล์:NPComplete5.gif‎]]v ,(u,v)[[ไฟล์:NPComplete6.gif]] E Clique		ดังนั้นทุกๆ u,v [[ไฟล์:NPComplete6.gif]] I ที่ u[[ไฟล์:NPComplete5.gif‎]]v ,(u,v)[[ไฟล์:NPComplete6.gif]] E Clique
		+	นั้นคือ I เป็น Clique ใน G clique
		+	เนทาองจาก \|I\| = K , G plus มี Clique ขนาด k 9k,9hv'dki
		+	Proof (<-)

@@ แถว 102: / แถว 102: @@
   ให้กราฟ G = (V,E) และจำนวนเต็ม K
-  กราฟ G pow c = (V,E') เป็น Complement ของ G
+  กราฟ G clique = (V,E') เป็น Complement ของ G
   ถ้า
    (u,v)[[ไฟล์:NPComplete6.gif]] E <--> (u,v)[[ไฟล์:Np-notnot.jpg]] E'
-  Lemma  กราฟ G = (V,E) มี Independent Set ขนาด K ใน G pow c = (V,E') มี Clique ของ K
+  Lemma  กราฟ G = (V,E) มี Independent Set ขนาด K ใน G clique = (V,E') มี Clique ของ K
   Proof (->)
          ให้ I เป็น Independent Set ขนาด K ใน G
          พิจารณาโหนด u,v [[ไฟล์:NPComplete6.gif]] I ใดๆ ที่ u[[ไฟล์:NPComplete5.gif‎]]v เนื่องจาก ณ เป็น Indep ใน G(u,v)[[ไฟล์:Np-notnot.jpg]] E