คณิตศาสตร์ไม่ต่อเนื่อง - เพิ่มเติมเกี่ยวกับกราฟ

การระบายสีกราฟ

การระบายสีกราฟเป็นขั้นตอนของการกำหนดสีให้กับจุดยอดแต่ละจุดของกราฟ G เพื่อให้ไม่มีจุดยอดที่อยู่ติดกันได้สีเดียวกัน มีวัตถุประสงค์เพื่อลดจำนวนสีในขณะที่ระบายสีกราฟ จำนวนสีที่น้อยที่สุดที่ต้องใช้ในการระบายสีกราฟ G เรียกว่าจำนวนสีของกราฟนั้น ปัญหาการระบายสีกราฟเป็นปัญหา NP Complete

วิธีการระบายสีกราฟ

ขั้นตอนที่จำเป็นในการระบายสีกราฟ G ด้วยจำนวนจุดยอด n มีดังนี้ -

Step 1 - จัดเรียงจุดยอดของกราฟตามลำดับ

Step 2 - เลือกจุดยอดแรกและระบายสีด้วยสีแรก

Step 3- เลือกจุดยอดถัดไปและระบายสีด้วยสีที่มีตัวเลขต่ำสุดที่ไม่ได้ถูกระบายสีบนจุดยอดใด ๆ ที่อยู่ติดกับจุดยอดนั้น หากจุดยอดที่อยู่ติดกันทั้งหมดมีสีด้วยสีนี้ให้กำหนดสีใหม่ ทำซ้ำขั้นตอนนี้จนกว่าจุดยอดทั้งหมดจะเป็นสี

Example

ในรูปด้านบนที่จุดยอดแรก $ a $ เป็นสีแดง เนื่องจากจุดยอดที่อยู่ติดกันของจุดยอด a อยู่ติดกันอีกครั้งจุดยอด $ b $ และจุดยอด $ d $ จึงมีสีต่างกันสีเขียวและสีน้ำเงินตามลำดับ จากนั้นจุดยอด $ c $ จะมีสีเป็นสีแดงเนื่องจากไม่มีจุดยอดที่อยู่ติดกันของ $ c $ เป็นสีแดง ดังนั้นเราสามารถระบายสีกราฟได้ 3 สี ดังนั้นจำนวนสีของกราฟคือ 3

การประยุกต์ใช้การระบายสีกราฟ

แอพพลิเคชั่นของการระบายสีกราฟ ได้แก่ -

• ลงทะเบียนการจัดสรร
• ระบายสีแผนที่
• การตรวจสอบกราฟ Bipartite
• การกำหนดความถี่วิทยุมือถือ
• ทำตารางเวลา ฯลฯ

กราฟ Traversal

การข้ามผ่านกราฟเป็นปัญหาในการเยี่ยมชมจุดยอดทั้งหมดของกราฟตามลำดับที่เป็นระบบ ส่วนใหญ่มีสองวิธีในการสำรวจกราฟ

• การค้นหาแรกกว้าง
• การค้นหาครั้งแรกเชิงลึก

การค้นหาแรกกว้าง

Breadth First Search (BFS) เริ่มต้นที่ระดับเริ่มต้น -0 จุดยอด $ X $ ของกราฟ $ G $ จากนั้นเราไปที่จุดยอดทั้งหมดที่เป็นเพื่อนบ้านของ $ X $ หลังจากเยี่ยมชมแล้วเราทำเครื่องหมายจุดยอดเป็น "เยี่ยมชม" และวางไว้ในระดับ -1 จากนั้นเราจะเริ่มจากจุดยอดระดับ 1 และใช้วิธีการเดียวกันกับทุกจุดยอดระดับ 1 และอื่น ๆ การข้ามผ่าน BFS จะสิ้นสุดเมื่อทุกจุดยอดของกราฟถูกเยี่ยมชม

BFS Algorithm

แนวคิดคือการเยี่ยมชมจุดยอดเพื่อนบ้านทั้งหมดก่อนที่จะเยี่ยมชมจุดยอดเพื่อนบ้านอื่น ๆ ของจุดยอดเพื่อนบ้าน

• เริ่มต้นสถานะของโหนดทั้งหมดเป็น“ พร้อม”

• ใส่จุดยอดต้นทางในคิวและเปลี่ยนสถานะเป็น "กำลังรอ"

• ทำซ้ำสองขั้นตอนต่อไปนี้จนกว่าคิวจะว่าง -

  • ลบจุดยอดแรกออกจากคิวและทำเครื่องหมายว่า "เยี่ยมแล้ว"

  • เพิ่มที่ด้านหลังของคิวเพื่อนบ้านทั้งหมดของจุดยอดที่ถูกลบซึ่งมีสถานะ "พร้อม" ทำเครื่องหมายสถานะเป็น "กำลังรอ"

Problem

ให้เราใช้กราฟ (จุดยอดต้นทางคือ 'a') และใช้อัลกอริทึม BFS เพื่อค้นหาลำดับการข้ามผ่าน

Solution -

• เริ่มต้นสถานะของจุดยอดทั้งหมดเป็น“ พร้อม”

• ใส่ในคิวและเปลี่ยนสถานะเป็น“รอ”

• นำจากคิวทำเครื่องหมายว่าเป็น“ผู้เข้าชม”

• เพิ่มเพื่อนบ้านใน ‘พร้อม’ รัฐB, DและEที่ส่วนท้ายของคิวและทำเครื่องหมายว่า ‘รอ’

• ลบbออกจากคิวทำเครื่องหมายว่า "เยี่ยมแล้ว" ใส่เพื่อนบ้าน "พร้อม" cที่ท้ายคิวและทำเครื่องหมายcเป็น "กำลังรอ"

• ลบdออกจากคิวและทำเครื่องหมายว่า "เยี่ยมแล้ว" ไม่มีเพื่อนบ้านอยู่ในสถานะ“ พร้อม”

• ลบeออกจากคิวและทำเครื่องหมายว่า "เยี่ยมแล้ว" ไม่มีเพื่อนบ้านอยู่ในสถานะ“ พร้อม”

• ลบcออกจากคิวและทำเครื่องหมายว่า "เยี่ยมแล้ว" ไม่มีเพื่อนบ้านอยู่ในสถานะ“ พร้อม”

• คิวว่างจึงหยุด

ดังนั้นลำดับการส่งผ่านคือ -

$ a \ rightarrow b \ rightarrow d \ rightarrow e \ rightarrow c $

คำสั่งอื่นของการส่งผ่านคือ -

$ a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c $

หรือ$ a \ rightarrow d \ rightarrow b \ rightarrow e \ rightarrow c $

หรือ$ a \ rightarrow e \ rightarrow b \ rightarrow d \ rightarrow c $

หรือ$ a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c $

หรือ$ a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c $

Application of BFS

• ค้นหาเส้นทางที่สั้นที่สุด
• ต้นไม้ที่ครอบคลุมขั้นต่ำสำหรับกราฟที่ไม่มีการถ่วงน้ำหนัก
• ระบบนำทาง GPS
• การตรวจจับรอบในกราฟที่ไม่มีทิศทาง
• ค้นหาโหนดทั้งหมดภายในส่วนประกอบที่เชื่อมต่อกัน

Complexity Analysis

ให้ $ G (V, E) $ เป็นกราฟที่มี $ | V | $ จำนวนจุดยอดและ $ | E | $ จำนวนขอบ หากอัลกอริทึมการค้นหาแรกกว้างเข้าชมทุกจุดยอดในกราฟและตรวจสอบทุกขอบความซับซ้อนของเวลาจะเป็น -

$$ O (| V | + | E |). O (| E |) $$

อาจแตกต่างกันระหว่าง $ O (1) $ และ $ O (| V2 |) $

การค้นหาครั้งแรกเชิงลึก

อัลกอริธึม Depth First Search (DFS) เริ่มต้นจากจุดยอด $ v $ จากนั้นจะข้ามไปยังจุดยอดที่อยู่ติดกัน (พูด x) ที่ไม่เคยเยี่ยมชมมาก่อนและทำเครื่องหมายเป็น "เยี่ยมชม" และไปต่อด้วยจุดยอดที่อยู่ติดกันที่ $ x $ และ เป็นต้น.

หากอยู่ที่จุดยอดใดจุดยอดหนึ่งพบว่ามีการเยี่ยมชมจุดยอดที่อยู่ติดกันทั้งหมดจากนั้นจะย้อนกลับไปจนกว่าจะพบจุดยอดแรกที่มีจุดยอดที่อยู่ติดกันซึ่งยังไม่เคยข้ามผ่านมาก่อน จากนั้นมันจะเคลื่อนผ่านจุดยอดนั้นไปเรื่อย ๆ โดยมีจุดยอดที่อยู่ติดกันจนกว่ามันจะข้ามผ่านจุดยอดเยี่ยมทั้งหมดและต้องย้อนรอยอีกครั้ง ด้วยวิธีนี้มันจะข้ามจุดยอดทั้งหมดที่เข้าถึงได้จากจุดยอดเริ่มต้น $ v $

DFS Algorithm

แนวคิดคือการเยี่ยมชมจุดยอดเพื่อนบ้านทั้งหมดของจุดยอดเพื่อนบ้านก่อนที่จะไปเยี่ยมชมจุดยอดเพื่อนบ้านอื่น ๆ

• เริ่มต้นสถานะของโหนดทั้งหมดเป็น“ พร้อม”

• ใส่จุดยอดต้นทางในสแต็กและเปลี่ยนสถานะเป็น "กำลังรอ"

• ทำซ้ำสองขั้นตอนต่อไปนี้จนกว่าสแต็กจะว่างเปล่า -

  • นำจุดยอดบนสุดออกจากสแต็กและทำเครื่องหมายเป็น "เยี่ยมชม"

  • ดันไปที่ด้านบนสุดของสแต็กเพื่อนบ้านทั้งหมดของจุดยอดที่ถูกลบซึ่งมีสถานะ "พร้อม" ทำเครื่องหมายสถานะเป็น "กำลังรอ"

Problem

ให้เราใช้กราฟ (จุดยอดที่มาคือ 'a') และใช้อัลกอริทึม DFS เพื่อค้นหาลำดับการข้ามผ่าน

Solution

• เริ่มต้นสถานะของจุดยอดทั้งหมดเป็น“ พร้อม”

• ผลักดันในกองและเปลี่ยนสถานะเป็น“รอ”

• Pop และทำเครื่องหมายเป็น“ผู้เข้าชม”

• ผลักดันเพื่อนบ้าน ‘ใน‘พร้อม’รัฐE, DและBไปด้านบนของสแต็คและทำเครื่องหมายว่า‘รอ’

• ป๊อปbจากสแต็กทำเครื่องหมายเป็น "เยี่ยมแล้ว" ดันเพื่อนบ้าน "พร้อม" cลงบนสแต็ก

• ป๊อปcจากสแต็กและทำเครื่องหมายเป็น "เยี่ยมชม" ไม่มีเพื่อนบ้านที่“ พร้อม”

• ป๊อปdจากสแต็กและทำเครื่องหมายเป็น "เยี่ยมชม" ไม่มีเพื่อนบ้านที่“ พร้อม”

• ป๊อปeจากสแต็กและทำเครื่องหมายเป็น "เยี่ยมชม" ไม่มีเพื่อนบ้านที่“ พร้อม”

• สแต็คว่างเปล่า ดังนั้นหยุดเถอะ

ดังนั้นลำดับการส่งผ่านคือ -

$ a \ rightarrow b \ rightarrow c \ rightarrow d \ rightarrow e $

คำสั่งอื่นของการส่งผ่านคือ -

$ a \ rightarrow e \ rightarrow b \ rightarrow c \ rightarrow d $

หรือ$ a \ rightarrow b \ rightarrow e \ rightarrow c \ rightarrow d $

หรือ$ a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c $

หรือ$ a \ rightarrow d \ rightarrow c \ rightarrow e \ rightarrow b $

หรือ$ a \ rightarrow d \ rightarrow c \ rightarrow b \ rightarrow e $

Complexity Analysis

ให้ $ G (V, E) $ เป็นกราฟที่มี $ | V | $ จำนวนจุดยอดและ $ | E | $ จำนวนขอบ หากอัลกอริทึม DFS เข้าชมทุกจุดยอดในกราฟและตรวจสอบทุกขอบความซับซ้อนของเวลาคือ -

$$ \ circleddash (| V | + | E |) $$

Applications

• การตรวจจับวงจรในกราฟ
• เพื่อค้นหาการเรียงลำดับโทโพโลยี
• เพื่อทดสอบว่ากราฟเป็นสองฝ่ายหรือไม่
• ค้นหาส่วนประกอบที่เชื่อมต่อ
• การหาสะพานของกราฟ
• ค้นหา bi-connectivity ในกราฟ
• การแก้ปัญหาทัวร์อัศวิน
• การแก้ปริศนาด้วยวิธีแก้ปัญหาเดียว