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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(VC-SNDP/spider decomposition ถูกเปลี่ยนชื่อเป็น VC-SNDP:spider decomposition ทับหน้าเปลี่ยนทาง)
แถว 10: แถว 10:
 
# ทุก ๆ leaf เป็น black vertex
 
# ทุก ๆ leaf เป็น black vertex
 
# ทุก ๆ black vertex เป็น leg ของ ''k'' spiders พอดี
 
# ทุก ๆ black vertex เป็น leg ของ ''k'' spiders พอดี
# ทุก ๆ intermediate vertex เป็น white vertex  (สังเกตว่า head เป็น black vertex ได้)
+
# ทุก ๆ intermediate vertex เป็น white vertex  (สังเกตว่า head เป็น black vertex ได้) และสำหรับกรณีที่ spider มี white vertex เป็น head จะต้องมี leg อย่างน้อย 2 legs
  
 
ด้านล่างแสดงตัวอย่างของ spiders
 
ด้านล่างแสดงตัวอย่างของ spiders

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

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

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

Spider คือ tree ที่มีโหนดที่มีดีกรีมากกว่าสองไม่เกิน 1 จุดยอด ถ้ามี vertex ดังกล่าว จะเรียกว่าเป็น head ถ้าไม่มี spider จะเป็น path และจะสามารถเรียกโหนดใดเป็น head ก็ได้; เรียกจุดยอดที่ไม่ใช่ leaf และ head ว่า intermediate vertex, เรียก leaf ว่า foot, เรียก path จาก head ไป leaf ว่า leg

Decomposition

ChK แสดงว่า ให้กราฟ G ที่ทุก ๆ คู่ของจุดยอดสีดำ k-element connected, มีสับกราฟ H ของ G ที่สามารถ partition เป็น spiders ที่

  1. ทุก ๆ leaf เป็น black vertex
  2. ทุก ๆ black vertex เป็น leg ของ k spiders พอดี
  3. ทุก ๆ intermediate vertex เป็น white vertex (สังเกตว่า head เป็น black vertex ได้) และสำหรับกรณีที่ spider มี white vertex เป็น head จะต้องมี leg อย่างน้อย 2 legs

ด้านล่างแสดงตัวอย่างของ spiders

Spiders.png

Approximating SS-k-VC-SNDP

Reduction lemma

Proof of the spider decomposition with the reduction lemma