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

เกี่ยวกับเครื่องคำนวณนี้

เครื่องคำนวณการระบายสีกราฟหาเลขรงค์ χ(G) คือจำนวนสีน้อยที่สุดที่ใช้ระบายจุดยอดของกราฟโดยไม่มีเส้นเชื่อมใดเชื่อมจุดยอดสองจุดที่มีสีเดียวกัน และแสดงการระบายสีที่เหมาะสมที่สุดหนึ่งแบบ ป้อนจำนวนจุดยอดและรายการเส้นเชื่อม เครื่องจะคำนวณ χ อย่างแม่นตรงด้วยการค้นหาแบบ branch-and-bound แสดงดีกรีสูงสุด Δ และกลุ่มย่อยบริบูรณ์ที่ใหญ่ที่สุด ω (ขอบเขตล่างของ χ) แจ้งกราฟสองส่วนและกราฟบริบูรณ์ และวาดกราฟที่ระบายสีแล้ว มีประโยชน์สำหรับการจัดตารางเวลา การจัดสรรรีจิสเตอร์ การระบายสีแผนที่ และการศึกษาเลขรงค์

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

1. ป้อนจำนวนจุดยอด ซึ่งมีหมายเลข 1 ถึง n
2. ระบุเส้นเชื่อมเป็นคู่ เช่น 1-2, 2-3 หนึ่งคู่ต่อหนึ่งการเชื่อมต่อ
3. อ่านเลขรงค์ χ(G) และสีที่กำหนดให้จุดยอดแต่ละจุด
4. เปรียบเทียบ χ กับกลุ่มย่อยบริบูรณ์ที่ใหญ่ที่สุด ω เพื่อดูว่าทำไมจึงต้องใช้จำนวนสีเท่านั้น หรือโหลดตัวอย่างสำเร็จรูปเพื่อสำรวจ

ตัวอย่างที่พบบ่อย

• สามเหลี่ยม (K₃) ต้องใช้ 3 สี เพราะจุดยอดทุกคู่อยู่ติดกัน
• วัฏจักรคู่เป็นกราฟสองส่วนและใช้เพียง 2 สี ส่วนวัฏจักรคี่อย่าง C₅ ต้องใช้ 3 สี
• กราฟบริบูรณ์ Kₙ ต้องใช้ n สีพอดี
• กลุ่มย่อยบริบูรณ์ที่ใหญ่ที่สุดขนาด ω บังคับให้ใช้อย่างน้อย ω สี ดังนั้น χ(G) ≥ ω
• กราฟกรอตซ์ต้องใช้ 4 สีแม้ไม่มีสามเหลี่ยมเลย χ จึงมากกว่าขนาดกลุ่มย่อยบริบูรณ์ได้