ทฤษฎีกราฟ - การครอบคลุม

กราฟที่ครอบคลุมคือกราฟย่อยที่มีจุดยอดทั้งหมดหรือขอบทั้งหมดที่ตรงกับกราฟอื่น ๆ ย่อหน้าย่อยที่มีจุดยอดทั้งหมดเรียกว่า aline/edge covering. กราฟย่อยที่มีขอบทั้งหมดเรียกว่าไฟล์vertex covering.

การครอบคลุมเส้น

ให้ G = (V, E) เป็นกราฟ เซตย่อย C (E) เรียกว่าเส้นที่ครอบคลุม G ถ้าทุกจุดยอดของ G เกิดขึ้นโดยมีอย่างน้อยหนึ่งขอบใน C กล่าวคือ

องศา (V) ≥ 1 ∀ V ∈ G

เนื่องจากจุดยอดแต่ละจุดเชื่อมต่อกับจุดยอดอื่นด้วยขอบ ดังนั้นจึงมีระดับขั้นต่ำ 1

Example

ดูกราฟต่อไปนี้ -

ย่อหน้าที่มีเส้นครอบคลุมมีดังนี้ -

1 = {{a, b}, {c, d}}

2 = {{a, d}, {b, c}}

3 = {{a, b}, {b, c}, {b, d}}

4 = {{a, b}, {b, c}, {c, d}}

ไม่มีการปิดทับเส้นของ 'G' ก็ต่อเมื่อ 'G' มีจุดยอดที่แยกได้ เส้นคลุมของกราฟที่มีจุดยอด 'n' มีขอบอย่างน้อย [n / 2]

การครอบคลุมบรรทัดน้อยที่สุด

เส้นที่ครอบคลุม C ของกราฟ G มีค่าน้อยที่สุด if no edge can be deleted from C.

Example

ในกราฟด้านบนกราฟย่อยที่มีเส้นครอบคลุมมีดังนี้ -

1 = {{a, b}, {c, d}}

2 = {{a, d}, {b, c}}

3 = {{a, b}, {b, c}, {b, d}}

4 = {{a, b}, {b, c}, {c, d}}

ในที่นี้ C 1 , C 2 , C 3เป็นการปิดทับเส้นขั้นต่ำในขณะที่ C 4ไม่ใช่เพราะเราสามารถลบ {b, c} ได้

การครอบคลุมบรรทัดขั้นต่ำ

เป็นที่รู้จักกันในชื่อ Smallest Minimal Line Covering. เส้นขั้นต่ำที่มีจำนวนขอบต่ำสุดเรียกว่าเส้นขั้นต่ำที่ครอบคลุม 'G' จำนวนขอบในเส้นขั้นต่ำที่ครอบคลุมใน 'G' เรียกว่าline covering numberของ 'G' (α 1 )

Example

ในตัวอย่างข้างต้น C 1และ C 2คือเส้นขั้นต่ำที่ครอบคลุมของ G และα 1 = 2

  • ทุกบรรทัดที่ครอบคลุมมีการปิดบรรทัดน้อยที่สุด

  • การครอบคลุมทุกบรรทัดไม่มีการปิดบรรทัดขั้นต่ำ (C 3ไม่มีการครอบคลุมบรรทัดขั้นต่ำ

  • ไม่มีการครอบคลุมบรรทัดขั้นต่ำที่ประกอบด้วยวัฏจักร

  • หากเส้นที่ครอบคลุม "C" ไม่มีเส้นทางที่มีความยาวตั้งแต่ 3 ขึ้นไป "C" จะเป็นเส้นเล็ก ๆ ที่ครอบคลุมเนื่องจากส่วนประกอบทั้งหมดของ "C" เป็นกราฟดาวและจากกราฟดาวจะไม่สามารถลบขอบได้

เวอร์เท็กซ์ครอบคลุม

ให้ 'G' = (V, E) เป็นกราฟ เซตย่อย K ของ V เรียกว่าจุดยอดที่ครอบคลุม 'G' ถ้าขอบทุกด้านของ 'G' เกิดขึ้นกับหรือปิดทับด้วยจุดยอดใน 'K'

Example

ดูกราฟต่อไปนี้ -

กราฟย่อยที่ได้มาจากกราฟด้านบนมีดังนี้ -

K 1 = {b, c}

K 2 = {a, b, c}

K 3 = {b, c, d}

K 4 = {a, d}

ที่นี่ K 1 K 2และ K 3มีจุดยอดครอบคลุมในขณะที่ K 4ไม่มีจุดยอดครอบคลุมเนื่องจากไม่ครอบคลุมขอบ {bc}

ครอบคลุมจุดยอดน้อยที่สุด

จุดยอด 'K' ของกราฟ 'G' ถูกกล่าวว่าเป็นจุดยอดขั้นต่ำที่ครอบคลุมหากไม่สามารถลบจุดยอดออกจาก 'K' ได้

Example

ในกราฟด้านบนกราฟย่อยที่มีจุดยอดครอบคลุมมีดังนี้ -

K 1 = {b, c}

K 2 = {a, b, c}

K 3 = {b, c, d}

ที่นี่ K 1และ K 2เป็นการปกปิดจุดยอดน้อยที่สุดในขณะที่ใน K 3จุดยอด 'd' สามารถลบได้

การครอบคลุมจุดยอดขั้นต่ำ

เป็นที่รู้จักกันว่าเป็นจุดยอดน้อยที่สุดที่ครอบคลุม จุดยอดขั้นต่ำที่ครอบคลุมกราฟ 'G' ที่มีจำนวนจุดยอดต่ำสุดเรียกว่าจุดยอดต่ำสุดที่ครอบคลุม

จำนวนจุดยอดในจุดยอดต่ำสุดที่ครอบคลุม 'G' เรียกว่าจุดยอดครอบคลุมจำนวน G (α 2 )

Example

ในกราฟต่อไปนี้กราฟย่อยที่มีจุดยอดครอบคลุมมีดังนี้ -

K 1 = {b, c}

K 2 = {a, b, c}

K 3 = {b, c, d}

ในที่นี้ K 1คือจุดยอดขั้นต่ำของ G เนื่องจากมีจุดยอดเพียงสองจุด α 2 = 2