ผลต่างระหว่างรุ่นของ "VC-SNDP:spider decomposition"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 1: | แถว 1: | ||
This page describes '''spider decompositions''' and the approach of CK and ChK. | 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]] | [[ภาพ:Spiders.png]] | ||
รุ่นแก้ไขเมื่อ 05:11, 24 กุมภาพันธ์ 2552
This page describes spider decompositions and the approach of CK and ChK.
ให้กราฟ เซตของ terminals และจำนวนเต็มบวก เรียกโหนดใน เป็น 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
