Biconnectedness (ค่ายวันที่ 11 มีนาคม 2551) - ประวัติรุ่นแก้ไข

Cardcaptor: /* การระบุ biconnected component */

2008-03-12T17:05:59Z

การระบุ biconnected component

Cardcaptor: /* การระบุ biconnected component */

2008-03-12T17:05:29Z

การระบุ biconnected component

Cardcaptor: /* การระบุ biconnected component */

2008-03-12T17:05:03Z

การระบุ biconnected component

Cardcaptor: /* การระบุ biconnected component */

2008-03-12T16:52:09Z

การระบุ biconnected component

Cardcaptor: /* การระบุ biconnected component */

2008-03-12T16:44:42Z

การระบุ biconnected component

Cardcaptor: /* การระบุ biconnected component */

2008-03-12T16:27:33Z

การระบุ biconnected component

Cardcaptor: /* การระบุ biconnected component */

2008-03-12T16:26:54Z

การระบุ biconnected component

Cardcaptor: /* การระบุ biconnected component */

2008-03-12T16:24:08Z

การระบุ biconnected component

Cardcaptor: /* การระบุ biconnected component */

2008-03-12T16:00:02Z

การระบุ biconnected component

Cardcaptor: /* การระบุ biconnected component */

2008-03-12T15:56:41Z

การระบุ biconnected component

@@ แถว 164: / แถว 164: @@
 * เมื่อเราพิจารณา vertex v และ edge (v,w) ที่ต่ออยู่กับมัน เราจะได้ว่า
 ** ถ้า (v,w) เป็น back edge เราสามารถกำหนด bcc[(v,w)] = alpha
-** ถ้า (v,w) มีลักษณะเหมือน <math>(v,x)\,</math> กล่าวคือ low[w] < d[v] เราสามารถกำหนด bcc[(v,w)] = alpha ได้เช่นกันถ้า alpha มีค่าไม่เท่ากับ -1 หลังจากนั้นเราจะเรียก assign_bcc(w, alpha) เพื่อให้หมายเลขกับ edge ใน subtree ที่มี w เป็น root ต่อไป ถ้า alpha มีค่าเท่ากับ -1 แล้วเราต้องเพิ่มค่า last_component ขึ้นหนึ่งแล้วให้ bcc[(v,w)] = last_component] หลังจากนั้นจึงเรียก assign_bcc(w, last_component)
+** ถ้า (v,w) มีลักษณะเหมือน <math>(v,x)\,</math> กล่าวคือ low[w] < d[v] เราสามารถกำหนด bcc[(v,w)] = alpha ได้เช่นกันถ้า alpha มีค่าไม่เท่ากับ -1 หลังจากนั้นเราจะเรียก assign_bcc(w, alpha) เพื่อให้หมายเลขกับ edge ใน subtree ที่มี w เป็น root ต่อไป ถ้า alpha มีค่าเท่ากับ -1 แล้วเราต้องเพิ่มค่า last_component ขึ้นหนึ่งแล้วให้ bcc[(v,w)] = last_component หลังจากนั้นจึงเรียก assign_bcc(w, last_component)
 ** ถ้า (v,w) มีลักษณะเหมือน <math>(v,y)\,</math> กล่าวคือ low[w] = d[v] เราจะเพิ่ม last_component ขึ้น 1 แล้วให้ bcc[(v,w)] = last_component หลังจากนั้นเราจะเรียก assign_bcc(w, last_component)
 ** ถ้า (v,w) มีลักษณะเหมือน <math>(v,z)\,</math> กล่าวคือ low[w] > d[v] เราจะเรียก assign_bcc(w, -1) ทันที

@@ แถว 166: / แถว 166: @@
 ** ถ้า (v,w) มีลักษณะเหมือน <math>(v,x)\,</math> กล่าวคือ low[w] < d[v] เราสามารถกำหนด bcc[(v,w)] = alpha ได้เช่นกันถ้า alpha มีค่าไม่เท่ากับ -1 หลังจากนั้นเราจะเรียก assign_bcc(w, alpha) เพื่อให้หมายเลขกับ edge ใน subtree ที่มี w เป็น root ต่อไป ถ้า alpha มีค่าเท่ากับ -1 แล้วเราต้องเพิ่มค่า last_component ขึ้นหนึ่งแล้วให้ bcc[(v,w)] = last_component] หลังจากนั้นจึงเรียก assign_bcc(w, last_component)
 ** ถ้า (v,w) มีลักษณะเหมือน <math>(v,y)\,</math> กล่าวคือ low[w] = d[v] เราจะเพิ่ม last_component ขึ้น 1 แล้วให้ bcc[(v,w)] = last_component หลังจากนั้นเราจะเรียก assign_bcc(w, last_component)
-** ถ้า (v,w) มีลักษณะเหมือน <math>(v,ผ)\,</math> กล่าวคือ low[w] > d[v] เราจะเรียก assign_bcc(w, -1) ทันที
+** ถ้า (v,w) มีลักษณะเหมือน <math>(v,z)\,</math> กล่าวคือ low[w] > d[v] เราจะเรียก assign_bcc(w, -1) ทันที
 เมื่อเขียนเป็น pseudocode จะได้ดังต่อไปนี้

@@ แถว 162: / แถว 162: @@
 * เราจะเขียนอัลกอริทึมเราในฟังก์ชัน assign_bcc(v, alpha) โดย v คือ vertex ที่เรากำลังจะทำ DFS ส่วน alpha คือหมายเลข biconnected component ที่เราใส่ให้ tree edge ที่นำเรามาสู่ v หาก tree edge นั้นเป็น bridge เราจะให้ alpha มีค่าพิเศษ ในที่นี้สมมติให้เป็น -1
 * เราจะให้มีตัวแปร global ชื่อ last_component ซึ่งเป็นหมายเลขของ biconnected component หมายเลขสุดท้ายที่เคยใช้ไปแล้ว เริ่มต้น last_component จะมีค่าเท่ากับ 0 เพื่อให้ biconnected component แรกได้หมายเลข 1
+* เมื่อเราพิจารณา vertex v และ edge (v,w) ที่ต่ออยู่กับมัน เราจะได้ว่า

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 16:52, 12 มีนาคม 2551
แถว 157:		แถว 157:
	*# กรณี <math>(v,y)\,</math> ซึ่งมี back edge จาก subtree ที่มี root อยู่ที่ y มายัง <math>v\,</math> เอง ในกรณีนี้ <math>bcc[(v,x)] = \beta\,</math> โดยที่ <math>\beta \neq \alpha\,</math> เนื่องจาก <math>(v,y)</math> ไม่ได้อยู่ใน simple cycle เดียวกับ <math>(u,v)\,</math> แล้ว		*# กรณี <math>(v,y)\,</math> ซึ่งมี back edge จาก subtree ที่มี root อยู่ที่ y มายัง <math>v\,</math> เอง ในกรณีนี้ <math>bcc[(v,x)] = \beta\,</math> โดยที่ <math>\beta \neq \alpha\,</math> เนื่องจาก <math>(v,y)</math> ไม่ได้อยู่ใน simple cycle เดียวกับ <math>(u,v)\,</math> แล้ว
	*# กรณี <math>(v,z)\,</math> เป็น bridge ในกรณีนี้เราไม่จำเป็นต้องใส่หมายเลขให้ <math>(v,z)\,</math> แต่ edge ใดๆ ก็ตามที่อยู่ใน subtree ที่ีมี <math>z\,</math> เป็น root จะต้องได้หมายเลขไม่ซ้ำกับที่ edge อื่นๆ ในกราฟเคยได้มาแล้ว		*# กรณี <math>(v,z)\,</math> เป็น bridge ในกรณีนี้เราไม่จำเป็นต้องใส่หมายเลขให้ <math>(v,z)\,</math> แต่ edge ใดๆ ก็ตามที่อยู่ใน subtree ที่ีมี <math>z\,</math> เป็น root จะต้องได้หมายเลขไม่ซ้ำกับที่ edge อื่นๆ ในกราฟเคยได้มาแล้ว
		+
		+	เราใช้ข้อสังเกตข้างต้นในการออกแบบอัลกอริทึมดังต่อไปนี้
		+	* อัลกอริทึมของเราจะท่องไปในกราฟแบบ DFS ตามลำดับการเยี่ยมเยือน vertex เหมือนตอนที่เราคำนวณ <math>low[v]\,</math> ตอนแรก
		+	* เราจะเขียนอัลกอริทึมเราในฟังก์ชัน assign_bcc(v, alpha) โดย v คือ vertex ที่เรากำลังจะทำ DFS ส่วน alpha คือหมายเลข biconnected component ที่เราใส่ให้ tree edge ที่นำเรามาสู่ v หาก tree edge นั้นเป็น bridge เราจะให้ alpha มีค่าพิเศษ ในที่นี้สมมติให้เป็น -1
		+	* เราจะให้มีตัวแปร global ชื่อ last_component ซึ่งเป็นหมายเลขของ biconnected component หมายเลขสุดท้ายที่เคยใช้ไปแล้ว เริ่มต้น last_component จะมีค่าเท่ากับ 0 เพื่อให้ biconnected component แรกได้หมายเลข 1
		+	*

@@ แถว 152: / แถว 152: @@
 เราใช้ข้อสังเกตต่อไปนี้ในการออกแบบอัลกอริทึม
 * สมมติว่าขณะนี้เรากำลังทำ DFS ครั้งที่สอง และเรามาอยู่ที่ vertex <math>v\,</math> โดยตาม edge <math>(u,v)\,</math> ลงมา และเราได้ให้หมายเลข <math>bcc[(u,v)] = \alpha\,</math>
-* สำหรับ back edge <math>(v,w)\,</math> ใดๆ มันก็ควรได้หมายเลข <math>bcc[(v,w)] = \alpha\,</math> ไปด้วย เพราะว่ามันอยู่ใน cycle เดียวกับ <math>(u,v)\,</math>
+* สำหรับ back edge <math>(v,w)\,</math> ใดๆ มันก็ควรได้หมายเลข <math>bcc[(v,w)] = \alpha\,</math> ไปด้วย เพราะว่ามันอยู่ใน simple cycle เดียวกับ <math>(u,v)\,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 16:26, 12 มีนาคม 2551
แถว 150:		แถว 150:
	[[ภาพ:biconnectedness-03.JPG\|400px]]		[[ภาพ:biconnectedness-03.JPG\|400px]]

−	เราใช้ข้อสังเกตต่อไปนี้ในการออกแบบอัลกอริทึม:	+	เราใช้ข้อสังเกตต่อไปนี้ในการออกแบบอัลกอริทึม
		+	* สมมติว่าขณะนี้เรากำลังทำ DFS ครั้งที่สอง และเรามาอยู่ที่ vertex <math>v\,</math> โดยตาม edge <math>(u,v)\,</math> ลงมา และเราได้ให้หมายเลข <math>bcc[(u,v)] = \alpha\,</math>
		+	* สำหรับ back edge <math>(v,w)\,</math> ใดๆ มันก็ควรได้หมายเลข <math>\alpha\,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 16:24, 12 มีนาคม 2551
แถว 145:		แถว 145:

	เราทำการใส่เลข <math>bcc[e]\,</math> ได้ใน <math>O(\|V\|+\|E\|)\,</math> หลังจากเราคำนวณค่า <math>low[v]\,</math> และ <math>parent[v]\,</math> ข้างต้นเสร็จแล้ว โดยเราจะทำ DFS ลงไปในกราฟอีกครั้ง โดยมีลำดับการเข้าไปเยี่ยมเยือน vertex ต่างๆ เหมือนกับตอนที่เราทำ DFS เพื่อคำนวณ <math>low[v]\,</math> ครั้งแรก		เราทำการใส่เลข <math>bcc[e]\,</math> ได้ใน <math>O(\|V\|+\|E\|)\,</math> หลังจากเราคำนวณค่า <math>low[v]\,</math> และ <math>parent[v]\,</math> ข้างต้นเสร็จแล้ว โดยเราจะทำ DFS ลงไปในกราฟอีกครั้ง โดยมีลำดับการเข้าไปเยี่ยมเยือน vertex ต่างๆ เหมือนกับตอนที่เราทำ DFS เพื่อคำนวณ <math>low[v]\,</math> ครั้งแรก
		+
		+	พิจารณาภาพข้างล่าง
		+
		+	[[ภาพ:biconnectedness-03.JPG\|400px]]
		+
		+	เราใช้ข้อสังเกตต่อไปนี้ในการออกแบบอัลกอริทึม:

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 16:00, 12 มีนาคม 2551
แถว 143:		แถว 143:
	== การระบุ biconnected component ==		== การระบุ biconnected component ==
	ในหัวข้อนี้เราจะสนใจการใส่เลข <math>bcc[e]\,</math> (ย่อมาจาก '''b'''i'''c'''onnected '''c'''omponent) สำำหรับ edge <math>e\,</math> แต่ละ edge โดยที่ <math>e\,</math> และ <math>e'\,</math> อยู่ใน biconnected component เดียวกัน ก็ต่อเมื่อ <math>bcc[e] = bcc[e']\,</math>		ในหัวข้อนี้เราจะสนใจการใส่เลข <math>bcc[e]\,</math> (ย่อมาจาก '''b'''i'''c'''onnected '''c'''omponent) สำำหรับ edge <math>e\,</math> แต่ละ edge โดยที่ <math>e\,</math> และ <math>e'\,</math> อยู่ใน biconnected component เดียวกัน ก็ต่อเมื่อ <math>bcc[e] = bcc[e']\,</math>
		+
		+	เราทำการใส่เลข <math>bcc[e]\,</math> ได้ใน <math>O(\|V\|+\|E\|)\,</math> หลังจากเราคำนวณค่า <math>low[v]\,</math> และ <math>parent[v]\,</math> ข้างต้นเสร็จแล้ว โดยเราจะทำ DFS ลงไปในกราฟอีกครั้ง โดยมีลำดับการเข้าไปเยี่ยมเยือน vertex ต่างๆ เหมือนกับตอนที่เราทำ DFS เพื่อคำนวณ <math>low[v]\,</math> ครั้งแรก

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 15:56, 12 มีนาคม 2551
แถว 142:		แถว 142:

	== การระบุ biconnected component ==		== การระบุ biconnected component ==
−	ในหัวข้อนี้เราจะสนใจการใส่เลข <math>bcc[e]\,</math> ~~ให้สำำหรับ~~ edge <math>e\,</math> แต่ละ edge โดยที่ <math>e\,</math> และ <math>e'\,</math> อยู่ใน biconnected component เดียวกัน ก็ต่อเมื่อ <math>bcc[e] = bcc[e']\,</math>	+	ในหัวข้อนี้เราจะสนใจการใส่เลข <math>bcc[e]\,</math> (ย่อมาจาก '''b'''i'''c'''onnected '''c'''omponent) สำำหรับ edge <math>e\,</math> แต่ละ edge โดยที่ <math>e\,</math> และ <math>e'\,</math> อยู่ใน biconnected component เดียวกัน ก็ต่อเมื่อ <math>bcc[e] = bcc[e']\,</math>