ทฤษฎีกราฟ - เซตอิสระ

เซตอิสระจะแสดงเป็นเซตซึ่ง

• ไม่ควรมี any edges adjacent to each other. ไม่ควรมีจุดยอดทั่วไประหว่างสองขอบใด ๆ

• ไม่ควรมี any vertices adjacent to each other. ไม่ควรมีขอบร่วมระหว่างจุดยอดทั้งสอง

ชุดสายอิสระ

ให้ 'G' = (V, E) เป็นกราฟ ส่วนย่อย L ของ E เรียกว่าชุดบรรทัดอิสระของ 'G' ถ้าไม่มีขอบสองด้านใน L อยู่ติดกัน ชุดดังกล่าวเรียกว่าชุดสายอิสระ

Example

ให้เราพิจารณาส่วนย่อยต่อไปนี้ -

L1 = {a,b}
L2 = {a,b} {c,e}
L3 = {a,d} {b,c}

ในตัวอย่างนี้ส่วนย่อย L2 และ L3 ไม่ใช่ขอบที่อยู่ติดกันในกราฟที่กำหนดอย่างชัดเจน เป็นชุดสายอิสระ อย่างไรก็ตาม L1 ไม่ใช่ชุดเส้นอิสระสำหรับการสร้างชุดเส้นอิสระควรมีอย่างน้อยสองขอบ

ชุดเส้นอิสระสูงสุด

ชุดเส้นอิสระถูกกล่าวว่าเป็นชุดเส้นอิสระสูงสุดของกราฟ 'G' ถ้าไม่สามารถเพิ่มขอบอื่นของ 'G' ใน 'L' ได้

Example

ให้เราพิจารณาส่วนย่อยต่อไปนี้ -

L1 = {a, b}
L2 = {{b, e}, {c, f}}
L3 = {{a, e}, {b, c}, {d, f}}
L4 = {{a, b}, {c, f}}

L ₂และ L ₃เป็นชุดเส้นอิสระสูงสุด / การจับคู่สูงสุด สำหรับเพียงสองส่วนย่อยนี้จะไม่มีโอกาสเพิ่มขอบอื่น ๆ ที่ไม่ใช่ส่วนที่อยู่ติดกัน ดังนั้นทั้งสองชุดย่อยจึงถือเป็นชุดบรรทัดอิสระสูงสุด

ชุดสายอิสระสูงสุด

ชุดเส้นอิสระสูงสุดของ 'G' ที่มีจำนวนขอบสูงสุดเรียกว่าชุดเส้นอิสระสูงสุด 'G'

Number of edges in a maximum independent line set of G (β1)
   = Line independent number of G
   = Matching number of G

Example

ให้เราพิจารณาส่วนย่อยต่อไปนี้ -

L1 = {a, b}
L2 = {{b, e}, {c, f}}
L3 = {{a, e}, {b, c}, {d, f}}
L4 = {{a, b}, {c, f}}

L ₃คือชุดเส้นอิสระสูงสุดของ G ที่มีขอบสูงสุดซึ่งไม่ใช่ขอบที่อยู่ติดกันในกราฟและแสดงด้วยβ1 = 3

Note - สำหรับกราฟ G ใด ๆ ที่ไม่มีจุดยอดแยก

α1 + β1 = จำนวนจุดยอดในกราฟ = | V |

Example

บรรทัดครอบคลุมจำนวน K _n / C _n / w _n ,

$$ \ alpha 1 = \ lceil \ frac {n} {2} \ rceil \ begin {cases} \ frac {n} {2} \: if \: n \: is \: even \\\ frac {n + 1} {2} \: if \: n \: is \: odd \ end {cases} $$

หมายเลขอิสระของเส้น (หมายเลขที่ตรงกัน) = β ₁ = [n / 2] α ₁ + β ₁ = n

ชุดจุดยอดอิสระ

ให้ 'G' = (V, E) เป็นกราฟ ชุดย่อยของ 'V' เรียกว่าชุดอิสระของ 'G' หากไม่มีจุดยอดสองจุดใน 'S' อยู่ติดกัน

Example

พิจารณาชุดย่อยต่อไปนี้จากกราฟด้านบน -

S1 = {e}

S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

เห็นได้ชัดว่า S ₁ไม่ใช่เซตจุดยอดอิสระเนื่องจากในการรับเซตจุดยอดอิสระควรมีจุดยอดอย่างน้อยสองจุดในกราฟจากกราฟ แต่ที่นี่ไม่เป็นเช่นนั้น เซ็ตย่อย S ₂ , S ₃และ S ₄เป็นเซตจุดยอดอิสระเนื่องจากไม่มีจุดยอดที่อยู่ติดกับจุดยอดใดจุดยอดหนึ่งจากเซตย่อย

ชุดจุดยอดอิสระสูงสุด

ให้ 'G' เป็นกราฟจากนั้นชุดจุดยอดอิสระของ 'G' จะถูกกล่าวว่าสูงสุดหากไม่สามารถเพิ่มจุดยอดอื่นของ 'G' ใน 'S' ได้

Example

พิจารณาส่วนย่อยต่อไปนี้จากกราฟด้านบน

S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

S ₂และ S ₃เป็นชุดจุดยอดอิสระสูงสุดของ 'G' ใน S ₁และ S ₄เราสามารถเพิ่มจุดยอดอื่น ๆ แต่ใน S ₂และ S ₃เราไม่สามารถเพิ่มจุดยอดอื่นได้

ชุดจุดยอดอิสระสูงสุด

ชุดจุดยอดอิสระสูงสุดของ 'G' ที่มีจำนวนจุดยอดสูงสุดเรียกว่าชุดจุดยอดอิสระสูงสุด

Example

พิจารณาชุดย่อยต่อไปนี้จากกราฟด้านบน -

S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

เฉพาะ S ₃เท่านั้นที่เป็นชุดจุดยอดอิสระสูงสุดเนื่องจากครอบคลุมจุดยอดสูงสุดจำนวนมาก จำนวนจุดยอดในชุดจุดยอดอิสระสูงสุดของ 'G' เรียกว่าจำนวนจุดยอดอิสระของ G (β ₂ )

Example

สำหรับฉบับสมบูรณ์กราฟ K _n ,

จุดยอดครอบคลุมจำนวน = α ₂ = n − 1

จำนวนอิสระจุดยอด = β ₂ = 1

คุณมีα ₂ + β ₂ = n

ในกราฟที่สมบูรณ์จุดยอดแต่ละจุดอยู่ติดกับจุดยอดที่เหลือ (n - 1) ดังนั้นชุดอิสระสูงสุดของ K _{n จึง}มีจุดยอดเพียงจุดเดียว

ดังนั้นβ ₂ = 1

และα ₂ = | v | - β ₂ = n-1

Note - สำหรับกราฟ 'G' = (V, E)

• α ₂ + β ₂ = | v |
• ถ้า 'S' เป็นชุดจุดยอดอิสระของ 'G' ดังนั้น (V - S) จะเป็นจุดยอดปกของ G