กลับไปหน้าบทความ

อ่าน 8 นาที

ชุดครอบงำอิสระ

ใน ทฤษฎีกราฟ เซต ครอบงำอิสระ สำหรับ กราฟ จี = ( วี , อี ) {\displaystyle G=(V,E)} เป็น เซตย่อย ดี ⊆ วี {\displaystyle D\subseteq V} ซึ่งเป็นทั้ง เซตครอบงำ และ เซตอิสระ...

ชุดครอบงำอิสระ

กราฟที่มีเซตครอบงำอิสระ ขั้นต่ำ แสดงด้วยสีแดง มีจุดยอด 3 จุดในเซต และดังนั้นจำนวนการครอบงำอิสระ ก็คือ...ฉัน(จี)=3{\displaystyle i(G)=3}(ซึ่งมากกว่าจำนวนการครอบงำ)γ(จี)=2{\displaystyle \gamma (G)=2})

ในทฤษฎีกราฟเซตครอบงำอิสระสำหรับกราฟจี=(วี,อี){\displaystyle G=(V,E)}เป็นเซตย่อยดีวี{\displaystyle D\subseteq V}ซึ่งเป็นทั้งเซตครอบงำและเซตอิสระหรือกล่าวอีกนัยหนึ่งคือเป็น เซต อิสระสูงสุด[ 1 ]

จำนวนการครอบงำอิสระฉัน(จี){\displaystyle i(G)}ของกราฟจี{\displaystyle G}คือขนาดของเซตครอบงำอิสระที่เล็กที่สุด (เทียบเท่ากับเซตอิสระสูงสุดที่เล็กที่สุด) [ 1 ]สัญลักษณ์ฉัน(จี){\displaystyle i(G)}ได้รับการแนะนำโดย Cockayne และ Hedetniemi [ 2 ] [ 3 ]

ประวัติศาสตร์

แนวคิดของเซตครอบงำอิสระเกิดขึ้นจากปัญหาหมากรุกในปี พ.ศ. 2405 เดอ จาเอนิช ได้ตั้งปัญหาในการหาจำนวนควีน ที่ไม่โจมตีกันน้อยที่สุด ที่สามารถวางบนกระดานหมากรุกได้ เพื่อให้ทุกช่องถูกโจมตีโดยควีนอย่างน้อยหนึ่งตัว[ 4 ]การจำลองกระดานหมากรุกเป็นกราฟของควีนจี{\displaystyle G}ค่าต่ำสุดนี้คือจำนวนการครอบงำที่เป็นอิสระฉัน(จี){\displaystyle i(G)}สำหรับแผนผังควีนมาตรฐานขนาด 8x8 นั้นα(จี)=8{\displaystyle \alpha (G)=8},ฉัน(จี)=7{\displaystyle i(G)=7}, และγ(จี)=5{\displaystyle \gamma (G)=5}[ 1 ]

ทฤษฎีการครอบงำแบบอิสระได้รับการกำหนดอย่างเป็นทางการโดยBergeและOreในปี พ.ศ. 2505 [ 5 ] [ 6 ] Berge สังเกตว่าเซตอิสระจะเป็นเซตอิสระสูงสุดก็ต่อเมื่อเป็นเซตครอบงำ และเซตอิสระสูงสุดทุกเซตจะเป็นเซตครอบงำขั้นต่ำ[ 5 ]

ขอบเขต

ขอบเขตทั่วไป

เบอร์เกได้กำหนดขอบเขตพื้นฐานในแง่ของลำดับn{\displaystyle n}และระดับ สูงสุดΔ{\displaystyle \Delta }ของกราฟ: [ 7 ]

n1+Δฉัน(จี)nΔ{\displaystyle \left\lceil {\frac {n}{1+\Delta }}\right\rceil \leq i(G)\leq n-\Delta }

สำหรับกราฟที่ไม่มีจุดยอดโดดเดี่ยว: [ 8 ]

ฉัน(จี)n+22n{\displaystyle i(G)\leq n+2-2{\sqrt {n}}}

และขอบเขตนี้มีความแม่นยำ สำหรับกราฟที่มีดีกรีต่ำสุดอย่างน้อยδ{\displaystyle \delta }: [ 9 ]

ฉัน(จี)n+2δ2δn{\displaystyle i(G)\leq n+2\delta -2{\sqrt {\delta n}}}

ยืนยันสมมติฐานก่อนหน้านี้ของฟาวารอน[ 8 ]

ตระกูลกราฟ

สำหรับกราฟที่ไม่มีกรงเล็บ : [ 10 ]

ฉัน(จี)=γ(จี){\displaystyle i(G)=\gamma (G)}

โดยทั่วไปแล้ว สำหรับเค1,เค{\displaystyle K_{1,k}}กราฟ แบบ -free ( star -free) ที่เค3{\displaystyle k\geq 3}: [ 11 ]

ฉัน(จี)(เค2)γ(จี)(เค3){\displaystyle i(G)\leq (k-2)\gamma (G)-(k-3)}

สำหรับกราฟสองส่วน ใดๆ ที่ไม่มีจุดยอดโดดเดี่ยวบนn{\displaystyle n}จุดยอด: [ 1 ]

ฉัน(จี)n/2{\displaystyle i(G)\leq n/2}

สำหรับต้นไม้ถ้าต้นไม้มีn{\displaystyle n}จุดยอดและ{\displaystyle \ell }ใบ: [ 12 ]

ฉัน(จี)(n+)/3{\displaystyle i(G)\leq (n+\ell )/3}

ถ้าจี{\displaystyle G}เป็น{\displaystyle r}- กราฟปกติบนn{\displaystyle n}จุดยอดที่ไม่มีจุดยอดโดดเดี่ยว จากนั้น: [ 13 ]

ฉัน(จี)α(จี)n/2{\displaystyle i(G)\leq \alpha (G)\leq n/2}

สำหรับกราฟลูกบาศก์ที่เชื่อมต่อกัน อื่นๆ นอกเหนือจากเค3,3{\displaystyle K_{3,3}}: [ 14 ]

ฉัน(จี)2n/5{\displaystyle i(G)\leq 2n/5}

มีการคาดการณ์ว่าขอบเขตดังกล่าวสามารถปรับปรุงให้ดีขึ้นได้3n/8{\displaystyle 3n/8}สำหรับกราฟลูกบาศก์ที่เชื่อมต่อทั้งหมดที่มีลำดับมากกว่า 10 [ 1 ]

เกี่ยวกับอัตราส่วนระหว่างการครอบงำและการครอบงำอิสระในกราฟลูกบาศก์ที่เชื่อมต่อกัน นอกเหนือจากนั้นเค3,3{\displaystyle K_{3,3}}: [ 15 ]

ฉัน(จี)/γ(จี)4/3{\displaystyle i(G)/\gamma (G)\leq 4/3}

สำหรับกราฟระนาบ ใดๆ บนn{\displaystyle n}จุดยอด: [ 16 ]

ฉัน(จี)3n/42{\displaystyle i(G)\leq 3n/4-2}

สำหรับกราฟระนาบที่มีเส้นผ่านศูนย์กลาง 2 ขอบเขตสามารถปรับปรุงได้: [ 16 ]

ฉัน(จี)n/3{\displaystyle i(G)\leq \lceil n/3\rceil }

ความสัมพันธ์กับกราฟเส้นและการครอบงำของขอบ

สำหรับกราฟใดๆจี{\displaystyle G}กราฟเส้นของมันแอล(จี){\displaystyle L(G)}ไม่มีกรงเล็บ ดังนั้นจึงเป็นเซตอิสระขั้นต่ำสุดสูงสุดในแอล(จี){\displaystyle L(G)}นอกจากนี้ยังเป็นเซตครอบงำขั้นต่ำในแอล(จี){\displaystyle L(G)}ชุดอิสระในแอล(จี){\displaystyle L(G)}สอดคล้องกับการจับคู่ในจี{\displaystyle G}และชุดที่โดดเด่นในแอล(จี){\displaystyle L(G)}สอดคล้องกับเซตที่ครอบงำขอบในจี{\displaystyle G}ดังนั้นการจับคู่สูงสุดขั้นต่ำ จึง มีขนาดเท่ากับเซตที่ครอบคลุมขอบขั้นต่ำ

ความสัมพันธ์กับพารามิเตอร์การครอบงำอื่นๆ

เนื่องจากการหาค่าต่ำสุดนั้นพิจารณาจากเซตจำนวนน้อยกว่า (โดยพิจารณาเฉพาะเซตครอบงำที่เป็นอิสระเท่านั้น)γ(จี)ฉัน(จี){\displaystyle \gamma (G)\leq i(G)}สำหรับกราฟทั้งหมดจี{\displaystyle G}ในทำนองเดียวกัน เนื่องจากเซตอิสระสูงสุดทุกเซตเป็นเซตอิสระฉัน(จี)α(จี){\displaystyle i(G)\leq \alpha (G)}, ที่ไหนα(จี){\displaystyle \alpha (G)}คือจำนวนความเป็นอิสระยิ่งไปกว่านั้น เนื่องจากเซตอิสระสูงสุดทุกเซตเป็นเซตครอบงำขั้นต่ำα(จี)Γ(จี){\displaystyle \alpha (G)\leq \Gamma (G)}, ที่ไหนΓ(จี){\displaystyle \Gamma (G)}คือจำนวนการครอบงำสูงสุด (ขนาดสูงสุดของเซตการครอบงำขั้นต่ำ) ซึ่งจะทำให้เกิดห่วงโซ่การครอบงำ : [ 17 ]

γ(จี)ฉัน(จี)α(จี)Γ(จี).{\displaystyle \gamma (G)\leq i(G)\leq \alpha (G)\leq \Gamma (G).}

ความไม่เท่าเทียมกันอาจเป็นแบบเข้มงวด มีกราฟอยู่ด้วยจี{\displaystyle G}ซึ่งγ(จี)<ฉัน(จี){\displaystyle \gamma (G)<i(G)}ตัวอย่างเช่น สมมติว่าจี{\displaystyle G}เป็นกราฟดาวคู่ที่ประกอบด้วยจุดยอดx1,,xพี,เอ,,y1,,yq{\displaystyle x_{1},\ldots ,x_{p},a,b,y_{1},\ldots ,y_{q}}, ที่ไหนพี,q>1{\displaystyle p,q>1}ขอบของจี{\displaystyle G}แต่ละคำนิยามไว้ดังนี้:xฉัน{\displaystyle x_{i}}อยู่ติดกับเอ{\displaystyle a},เอ{\displaystyle a}อยู่ติดกับ{\displaystyle b}, และ{\displaystyle b}อยู่ติดกับแต่ละyเจ{\displaystyle y_{j}}. แล้วγ(จี)=2{\displaystyle \gamma (G)=2}เนื่องจาก{เอ,}{\displaystyle \{a,b\}}เป็นเซตครอบงำที่เล็กที่สุด ถ้าพีq{\displaystyle p\leq q}, แล้วฉัน(จี)=พี+1{\displaystyle i(G)=p+1}เนื่องจาก{x1,,xพี,}{\displaystyle \{x_{1},\ldots ,x_{p},b\}}เป็นเซตครอบงำที่เล็กที่สุดที่เป็นอิสระด้วย (เป็นเซตอิสระสูงสุดที่เล็กที่สุด)

อย่างไรก็ตาม ขอบเขตγ(จี)ฉัน(จี)α(จี){\displaystyle \gamma (G)\leq i(G)\leq \alpha (G)}มีความคมชัดพร้อมกันสำหรับโคโรนาชมเค1{\displaystyle H\circ K_{1}}ของกราฟใดๆชม{\displaystyle H}ซึ่งเป็นที่น่าพอใจγ(จี)=ฉัน(จี)=α(จี)=|วี(ชม)|{\displaystyle \gamma (G)=i(G)=\alpha (G)=|V(H)|}[ 1 ]

Cockayne และ Mynhardt ได้ระบุลำดับของค่าที่เป็นไปได้ไว้ดังนี้: [ 18 ]ลำดับ(1,2,3,4){\displaystyle (s_{1},s_{2},s_{3},s_{4})}ของจำนวนเต็มสามารถเกิดขึ้นได้ดังนี้(γ(จี),ฉัน(จี),α(จี),Γ(จี)){\displaystyle (\gamma (G),i(G),\alpha (G),\Gamma (G))}สำหรับกราฟบางส่วนจี{\displaystyle G}ก็ต่อเมื่อ11234{\displaystyle 1\leq s_{1}\leq s_{2}\leq s_{3}\leq s_{4}},1=1{\displaystyle s_{1}=1}หมายความว่า2=1{\displaystyle s_{2}=1}, และ3=1{\displaystyle s_{3}=1}หมายความว่า4=1{\displaystyle s_{4}=1}.

ความซับซ้อนในการคำนวณ

การพิจารณาว่าฉัน(จี)เค{\displaystyle i(G)\leq k}สำหรับกราฟที่กำหนดจี{\displaystyle G}และจำนวนเต็มเค{\displaystyle k}โดยทั่วไปแล้ว P เป็นปัญหา NP-complete [ 19 ]และยังคงเป็น NP-complete แม้ว่าจะจำกัดเฉพาะกราฟสองส่วนกราฟเส้นกราฟวงกลมกราฟดิสก์หน่วยหรือกราฟลูกบาศก์ระนาบ[ 1 ] ยิ่งไปกว่านั้น Irving แสดงให้เห็นว่าไม่มีอัลกอริทึมเวลาพหุนามใดที่จะประมาณจำนวนการครอบงำอิสระภายในปัจจัยคงที่ได้ เว้นแต่ว่าP = NP [ 20 ]

ในทางกลับกัน จำนวนการครอบงำอิสระสามารถคำนวณได้ในเวลาเชิงเส้นสำหรับต้นไม้[ 21 ]และในเวลาพหุนามสำหรับกราฟคอร์ดัล[ 22 ]และกราฟโคคอมแพริบิลิตี้[ 23 ]

กราฟที่สมบูรณ์แบบในการครอบงำ

กราฟจี{\displaystyle G}เรียกว่ากราฟที่สมบูรณ์แบบการครอบงำ (domination-perfect graph)ถ้าγ(ชม)=ฉัน(ชม){\displaystyle \gamma (H)=i(H)}ในทุกซับกราฟที่เหนี่ยวนำชม{\displaystyle H}ของจี{\displaystyle G}[ 24 ]เนื่องจากกราฟย่อยที่เหนี่ยวนำของกราฟที่ไม่มีกรงเล็บเป็นกราฟที่ไม่มีกรงเล็บ ดังนั้นกราฟที่ไม่มีกรงเล็บทุกกราฟจึงเป็นกราฟที่สมบูรณ์แบบในการครอบงำด้วย[ 25 ]

จากผลการศึกษาของซัมเนอร์และมัวร์ กราฟจะเป็นกราฟสมบูรณ์แบบเชิงการครอบงำก็ต่อเมื่อγ(ชม)=ฉัน(ชม){\displaystyle \gamma (H)=i(H)}สำหรับกราฟย่อยเหนี่ยวนำทุกกราฟชม{\displaystyle H}กับγ(ชม)=2{\displaystyle \gamma (H)=2}[ 24 ] Zverovich และ Zverovich ได้ให้ลักษณะเฉพาะที่สมบูรณ์: กราฟจะสมบูรณ์แบบการครอบงำก็ต่อเมื่อไม่มีกราฟเฉพาะ 17 กราฟใดเป็นกราฟย่อยที่เหนี่ยวนำ[ 26 ]

กราฟที่ครอบคลุมดี

กราฟจะครอบคลุมพื้นที่ได้ดีหากฉัน(จี)=α(จี){\displaystyle i(G)=\alpha (G)}นั่นคือ เซตอิสระสูงสุดทุกเซตเป็นเซตอิสระสูงสุด แนวคิดนี้ได้รับการแนะนำโดย Plummer [ 27 ] Ravindra ได้กำหนดลักษณะของกราฟสองส่วนที่ครอบคลุมอย่างดี: กราฟสองส่วนที่เชื่อมต่อกันจะถูกครอบคลุมอย่างดีก็ต่อเมื่อมีการจับคู่ที่สมบูรณ์แบบเอ็ม{\displaystyle M}โดยที่สำหรับทุกขอบคุณวีเอ็ม{\displaystyle uv\in M}กราฟย่อยที่เกิดจากเอ็น[คุณ]เอ็น[วี]{\displaystyle N[u]\cup N[v]}เป็นกราฟสองส่วนที่สมบูรณ์[ 28 ]ผลที่ตามมาคือ ต้นไม้จะได้รับการครอบคลุมอย่างดีก็ต่อเมื่อเป็นเช่นนั้นเค1{\displaystyle K_{1}}หรือโคโรนาของต้นไม้[ 1 ]

ดูเพิ่มเติม

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ชุดครอบงำอิสระ

ใน ทฤษฎีกราฟ เซต ครอบงำอิสระ สำหรับ กราฟ จี = ( วี , อี ) {\displaystyle G=(V,E)} เป็น เซตย่อย ดี ⊆ วี {\displaystyle D\subseteq V} ซึ่งเป็นทั้ง เซตครอบงำ และ เซตอิสระ...

ประวัติศาสตร์

แนวคิดของเซตครอบงำอิสระเกิดขึ้นจาก ปัญหาหมากรุก ในปี พ.ศ. 2405 เดอ จาเอนิช ได้ตั้งปัญหาในการหาจำนวน ควีน ที่ไม่โจมตีกันน้อยที่สุด ที่สามารถวางบนกระดานหมากรุกได้ เพื่อให้ทุกช่องถูกโจมตีโดยควีนอย่างน้อยหนึ่งตัว [ 4 ] การจำลองกระดานหมากรุกเป็น กราฟของควีน จี...

ขอบเขตทั่วไป

เบอร์เกได้กำหนดขอบเขตพื้นฐานในแง่ของ ลำดับ n {\displaystyle n} และ ระดับ สูงสุด Δ {\displaystyle \Delta } ของกราฟ: [ 7 ]

ความสัมพันธ์กับกราฟเส้นและการครอบงำของขอบ

สำหรับกราฟใดๆ จี {\displaystyle G} กราฟเส้น ของมัน แอล ( จี ) {\displaystyle L(G)} ไม่มีกรงเล็บ ดังนั้นจึงเป็นเซตอิสระขั้นต่ำสุดสูงสุดใน แอล ( จี ) {\displaystyle L(G)} นอกจากนี้ยังเป็นเซตครอบงำขั้นต่ำใน แอล ( จี ) {\displaystyle L(G)} ชุดอิสระใน แอล ( จี )...