Let G be a chordal graph on n verti

Let G be a chordal graph on n vertices and let S be any set of vertices in G. From the correctness of the described algorithm it follows that μ(G, S) is upper bounded by the number of leaves in the search tree corresponding to the algorithm. Let L(n) denote the maximum number of leaves in a search tree resulting from running our algorithm on an n-vertex chordal graph G = (V , E) and a subset S ⊆ V . From the description of the algorithm we see that L(n) satisfies the following inequalities; we list them in the same order as the corresponding branching vectors in the proof of Theorem 2.

ผลลัพธ์ (ไทย) 1:

ให้ G เป็นกราฟ chordal บนจุดยอด n และ S ให้สามารถตั้งค่าใด ๆ ของจุดยอดในกรัม จากความถูกต้องของอัลกอริทึมที่อธิบายได้เป็นไปตาม ที่μ (G, S) อยู่ด้านบนล้อมรอบ ด้วยจำนวนของใบในการค้นหาที่สอดคล้องกับขั้นตอนวิธีการ ให้ L(n) ที่แสดงจำนวนของใบในการค้นหาผลลัพธ์จากการใช้อัลกอริทึมของเรามีจุดยอด n chordal กราฟ G = (V E) และการย่อย S ⊆ V จากคำอธิบายของอัลกอริทึมเราเห็นว่า L(n) ตรงที่ต่อไปนี้ความเหลื่อมล้ำทาง เรารายการเหล่านั้นในใบสั่งเดียวกันเป็นเวกเตอร์โยงหัวข้อที่เกี่ยวข้องในการพิสูจน์ทฤษฎีบท 2

ผลลัพธ์ (ไทย) 2:

ให้ G เป็นกราฟที่คอร์ดั n จุดและให้ S เป็นชุดของจุดใด ๆ ในจีจากความถูกต้องของขั้นตอนวิธีที่อธิบายมันตามที่μ (G, S) เป็นบน จำกัด โดยจำนวนของใบในต้นไม้ค้นหาที่สอดคล้องกับ อัลกอริทึม ให้ L (n) หมายถึงจำนวนสูงสุดของใบในต้นไม้ค้นหาที่เกิดจากการทำงานขั้นตอนวิธีของเราในกราฟ n-จุดสุดยอดคอร์ดั G = (V, E) และเซต⊆ V จากคำอธิบายของขั้นตอนวิธีที่เราเห็นว่า L (n) สอดคล้องกับความไม่เท่าเทียมกันดังต่อไปนี้; เรารายการพวกเขาในลำดับเดียวกับเวกเตอร์สาขาที่เกี่ยวข้องในการพิสูจน์ทฤษฎีบท 2

ผลลัพธ์ (ไทย) 3:

ให้ G เป็นกราฟ chordal บน n จุดยอด และให้มีชุดของจุดยอดใน จากความถูกต้องของการอธิบายขั้นตอนวิธีได้ดังนี้ว่า μ ( G , s ) คือบนล้อมรอบด้วยจำนวนใบในการค้นหาต้นไม้ที่สอดคล้องกับวิธีทำ ให้ L ( n ) แสดงถึงจำนวนสูงสุดของใบในต้นไม้ที่เกิดจากการใช้ขั้นตอนวิธีของเราใน n-vertex chordal กราฟ G = ( V ,E ) และบางส่วนของ⊆ V . จากรายละเอียดของขั้นตอนวิธี เราพบว่า L ( n ) อสมการต่อไปนี้ เราแสดงไว้ในคำสั่งเดียวกับที่แยกเวกเตอร์ในการพิสูจน์ทฤษฎีบท 2