ผลต่างระหว่างรุ่นของ "VC-SNDP:spider decomposition"

รุ่นแก้ไขเมื่อ 05:11, 24 กุมภาพันธ์ 2552

This page describes spider decompositions and the approach of CK and ChK.

ให้กราฟ $G=(V,E)$ เซตของ terminals $T$ และจำนวนเต็มบวก $k$ เรียกโหนดใน $T$ เป็น black vertices, นอกจากนั้นเป็น white vertices.

Spider คือ

tree ที่มีโหนดที่มีดีกรีมากกว่าสองไม่เกิน 1 จุดยอด (ถ้ามี vertex ดังกล่าว จะเรียกว่าเป็น head ถ้าไม่มี spider จะเป็น path และจะสามารถเรียกโหนดใดเป็น head ก็ได้; เรียกจุดยอดที่ไม่ใช่ leaf และ head ว่า intermediate vertex)
ทุก ๆ leaf เป็น black vertex เรียกว่า foot. แต่ละกิ่งเรียกว่า leg
ทุก ๆ intermediate vertex เป็น white vertex (สังเกตว่า head เป็น black vertex ได้)

ตัวอย่างของ spiders

@@ แถว 1: / แถว 1: @@
 This page describes '''spider decompositions''' and the approach of CK and ChK.
+ให้กราฟ <math>G=(V,E)</math> เซตของ terminals <math>T</math> และจำนวนเต็มบวก <math>k</math> เรียกโหนดใน <math>T</math> เป็น black vertices, นอกจากนั้นเป็น white vertices.
+'''Spider''' คือ
+* tree ที่มีโหนดที่มีดีกรีมากกว่าสองไม่เกิน 1 จุดยอด (ถ้ามี vertex ดังกล่าว จะเรียกว่าเป็น head  ถ้าไม่มี spider จะเป็น path และจะสามารถเรียกโหนดใดเป็น head ก็ได้; เรียกจุดยอดที่ไม่ใช่ leaf และ head ว่า intermediate vertex)
+* ทุก ๆ leaf เป็น black vertex เรียกว่า foot.  แต่ละกิ่งเรียกว่า leg
+* ทุก ๆ intermediate vertex เป็น white vertex  (สังเกตว่า head เป็น black vertex ได้)
+ตัวอย่างของ spiders
 [[ภาพ:Spiders.png]]