เครื่องคำนวณการระบายสีกราฟ

เกี่ยวกับ เครื่องคำนวณการระบายสีกราฟ

เครื่องคำนวณการระบายสีกราฟ จะคำนวณ เลขโครมาติก χ(G) และการระบายสีจุดยอดที่ถูกต้องสำหรับกราฟไม่มีทิศทางใดๆ เพียงป้อนกราฟของคุณในรูปแบบรายการเส้นเชื่อมหรือรายการความใกล้ชิด แล้วเครื่องมือจะส่งคืนจำนวนสีที่น้อยที่สุดที่จำเป็นเพื่อให้ไม่มีจุดยอดที่อยู่ติดกันสองจุดใดใช้สีเดียวกัน พร้อมกับการแสดงภาพ SVG แบบโต้ตอบ แอนิเมชันการทำงานของ DSATUR และรายละเอียดการแยกสีของแต่ละจุดยอด

การระบายสีกราฟคืออะไร?

การระบายสีจุดยอดที่ถูกต้อง ของกราฟ G = (V, E) คือการกำหนดสีให้กับแต่ละจุดยอดเพื่อให้ทุกเส้นเชื่อมมีจุดปลายที่มีสีต่างกัน เลขโครมาติก เขียนแทนด้วย χ(G) คือจำนวนสีที่น้อยที่สุดที่ทำให้การระบายสีดังกล่าวยังคงถูกต้อง การคำนวณ χ(G) เป็นปัญหาประเภท NP-hard ในทางทั่วไป แต่มีทฤษฎีทางคณิตศาสตร์ที่สวยงามและการประยุกต์ใช้งานจริงมากมาย เช่น การจัดตารางสอบ, การจัดสรรความถี่วิทยุ, การจัดสรรเรจิสเตอร์ในคอมไพเลอร์ และทฤษฎีบทสี่สีอันโด่งดังสำหรับแผนที่ระนาบ

ทฤษฎีบทและขอบเขตที่สำคัญ

• ขอบเขตทั่วไป: 1 ≤ χ(G) ≤ |V| สำหรับกราฟใดๆ
• ขอบเขตล่างจาก Clique: χ(G) ≥ ω(G) โดยที่ ω(G) คือขนาดของ Clique ที่ใหญ่ที่สุด
• คุณลักษณะของกราฟสองส่วน: χ(G) ≤ 2 ก็ต่อเมื่อ G ไม่มีวงจรคี่ (König)
• ทฤษฎีบทของ Brooks: χ(G) ≤ Δ(G) เว้นแต่ G จะเป็นกราฟบริบูรณ์หรือวงจรคี่ ซึ่งในกรณีนั้น χ(G) = Δ(G) + 1 โดยที่ Δ(G) คือดีกรีสูงสุด
• ทฤษฎีบทสี่สี: กราฟระนาบ (Planar graph) ทุกกราฟสามารถระบายสีได้ด้วย 4 สี
• ขอบเขตบนแบบ Greedy: อัลกอริทึม Greedy ใดๆ จะใช้สีไม่เกิน Δ(G) + 1 สี

อัลกอริทึมที่ใช้โดยเครื่องคำนวณนี้

DSATUR (Degree of Saturation)

นำเสนอโดย Daniel Brélaz ในปี 1979 DSATUR เป็นหนึ่งในฮิวริสติกที่มีประสิทธิภาพสูงสุดสำหรับการระบายสีกราฟ โดยจะเลือกจุดยอดที่ยังไม่ได้ระบายสีซึ่งมีเพื่อนบ้านใช้สีที่แตกต่างกันมากที่สุด (ความอิ่มตัวหรือ Saturation) หากเสมอกันจะพิจารณาจากดีกรีของจุดยอด และกำหนดสีที่น้อยที่สุดที่เพื่อนบ้านยังไม่ได้ใช้ DSATUR สามารถหาคำตอบที่เหมาะสมที่สุดได้สำหรับกราฟสองส่วนและกราฟที่มีโครงสร้างเฉพาะหลายประเภท และให้ผลลัพธ์ที่มีคุณภาพสูงในเวลาเพียงเสี้ยววินาทีแม้ในกราฟที่มีจุดยอดหลายร้อยจุด

Welsh-Powell

อัลกอริทึม Welsh-Powell จะจัดเรียงจุดยอดตาม ลำดับดีกรีจากมากไปน้อย แล้วทำการระบายสีแบบ Greedy มีความซับซ้อนของเวลาอยู่ที่ O(|V|²) และรับประกันว่าจะใช้สีไม่เกิน Δ(G) + 1 สี เป็นวิธีที่รวดเร็วมากและมักเป็นการประมาณการที่ดี แม้ว่าบางครั้งอาจได้ผลลัพธ์ด้อยกว่า DSATUR ในกราฟที่มีโครงสร้างเฉพาะตัว

Greedy (ตามลำดับการนำเข้า)

อัลกอริทึมที่ง่ายที่สุด: ไล่ระบายสีจุดยอดตามลำดับที่ผู้ใช้ป้อน และกำหนดสีที่น้อยที่สุดที่เพื่อนบ้านที่ระบายสีไปแล้วยังไม่ได้ใช้ ผลลัพธ์จะขึ้นอยู่กับลำดับการป้อนข้อมูล แต่การเรียงลำดับแบบสุ่มก็สามารถใช้เป็นฐานเปรียบเทียบกับฮิวริสติกที่ฉลาดกว่าได้

Exact Backtracking (การค้นหาแบบย้อนรอยแม่นยำ)

สำหรับกราฟขนาดเล็ก (ไม่เกินประมาณ 18 จุดยอด) เครื่องคำนวณสามารถหา เลขโครมาติกที่แท้จริง โดยการลอง k = 2, 3, 4, ... และพยายามระบายสี k สีด้วยวิธี Backtracking แบบค้นหาตามแนวลึก เมื่ออัลกอริทึมแบบแม่นยำทำงานสำเร็จ ผลลัพธ์จะแสดงป้ายกำกับว่า "แม่นยำ"

รูปแบบการนำเข้าข้อมูล

รายการเส้นเชื่อม (Edge list)

เขียนเส้นเชื่อมแต่ละเส้นโดยระบุชื่อจุดยอดสองชื่อคั่นด้วยยัติภังค์ (-), ช่องว่าง หรือลูกศร แยกแต่ละเส้นเชื่อมด้วยจุลภาคหรือการขึ้นบรรทัดใหม่ ชื่อจุดยอดสามารถประกอบด้วยตัวอักษร ตัวเลข หรือขีดล่าง ตัวอย่าง:

รายการความใกล้ชิด (Adjacency list)

เขียนชื่อจุดยอดตามด้วยเครื่องหมายทวิภาค (:) และรายชื่อเพื่อนบ้านที่คั่นด้วยจุลภาค ตัวอย่าง:

ระบบจะปฏิเสธวงวนในตัว (Self-loops) เพราะจุดยอดไม่สามารถมีสีต่างจากตัวมันเองได้ เส้นเชื่อมที่ซ้ำกันจะถูกลบออกโดยอัตโนมัติ และกราฟจะถูกประมวลผลเป็นกราฟไม่มีทิศทาง

วิธีใช้เครื่องคำนวณนี้

1. เลือกรูปแบบ: สลับระหว่าง 'รายการเส้นเชื่อม' และ 'รายการความใกล้ชิด' ด้วยปุ่มตัวเลือก
2. ป้อนข้อมูลกราฟ: วางข้อมูลของคุณหรือคลิกตัวอย่างด่วน (สามเหลี่ยม, กราฟบริบูรณ์ K₅, กราฟวงล้อ Petersen, กราฟสองส่วน K₃,₃, ตารางสอบ)
3. เลือกอัลกอริทึม: เลือก 'อัตโนมัติ' เพื่อผลลัพธ์ที่ดีที่สุด หรือระบุเฉพาะเจาะจง เช่น Welsh-Powell, Greedy, DSATUR หรือ Exact Backtracking
4. คลิก "ระบายสีกราฟ": เลขโครมาติก, รายการแยกตามสี, กราฟ SVG ที่โต้ตอบได้ และแอนิเมชันทีละขั้นตอนจะปรากฏด้านล่าง
5. สำรวจ: กด 'เล่น' เพื่อดูขั้นตอนการระบายสี, ลากโหนดเพื่อจัดตำแหน่ง และใช้ปุ่ม 'ถอยหลัง / ถัดไป' เพื่อดูทีละขั้นตอนด้วยตนเอง

การประยุกต์ใช้งานในทางปฏิบัติ

การจัดตารางสอบ

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

การจัดสรรความถี่วิทยุ

เครื่องส่งสัญญาณที่อยู่ในระยะรบกวนกันต้องใช้ความถี่ที่ต่างกัน เลขโครมาติกของกราฟการรบกวนคือจำนวนความถี่ที่น้อยที่สุดที่ต้องใช้

การจัดสรรเรจิสเตอร์

ในคอมไพเลอร์ ช่วงเวลาการใช้งานของตัวแปรคือจุดยอด ถ้าช่วงเวลาทับซ้อนกันจะมีเส้นเชื่อมระหว่างกัน การระบายสี k สีจะช่วยกำหนดตัวแปรให้กับเรจิสเตอร์ CPU จำนวน k ตัวโดยไม่เกิดการชนกัน

การระบายสีแผนที่

ประเทศที่มีพรมแดนติดกันต้องใช้สีต่างกัน ทฤษฎีบทสี่สี (Appel-Haken, 1976) พิสูจน์ว่าสี่สีเพียงพอสำหรับแผนที่บนระนาบใดๆ เสมอ

ซูโดกุและปริศนาเงื่อนไข

ซูโดกุที่สมบูรณ์คือการระบายสี 9 สีของกราฟที่มีจุดยอด 81 จุด (ช่อง) และเส้นเชื่อมเชื่อมโยงช่องที่อยู่ในแถวเดียวกัน คอลัมน์เดียวกัน หรือบล็อก 3×3 เดียวกัน การระบายสีกราฟเป็นแกนกลางทางคณิตศาสตร์ของปริศนาเงื่อนไขมากมาย

กรณีพิเศษที่น่าสนใจ

• กราฟบริบูรณ์ K_n: χ(K_n) = n เนื่องจากทุกจุดยอดเชื่อมถึงกันหมด จึงต้องใช้สีต่างกันทั้งหมด
• กราฟวงจร C_n: χ(C_n) = 2 ถ้า n เป็นเลขคู่ และ 3 ถ้า n เป็นเลขคี่
• ต้นไม้ (Tree): ต้นไม้ใดๆ ที่มีจุดยอดตั้งแต่ 2 จุดขึ้นไปจะมี χ = 2 (ต้นไม้เป็นกราฟสองส่วน)
• กราฟสองส่วน (Bipartite graph): χ = 2 หากกราฟมีเส้นเชื่อมอย่างน้อยหนึ่งเส้น
• กราฟ Petersen: กราฟ 3-regular ที่มีชื่อเสียง มี χ = 3
• กราฟวงล้อ W_n: จุดยอดศูนย์กลางเชื่อมกับวงจร n จุด χ = 3 ถ้า n เป็นเลขคู่ และ 4 ถ้า n เป็นเลขคี่

คำถามที่พบบ่อย

เลขโครมาติกของกราฟคืออะไร?

เลขโครมาติก χ(G) คือจำนวนสีที่น้อยที่สุดที่ใช้ในการระบายสีจุดยอดของกราฟ โดยที่ไม่มีจุดยอดที่อยู่ติดกันใช้สีเดียวกัน กราฟสองส่วนมีเลขโครมาติกไม่เกิน 2 กราฟที่มีรูปสามเหลี่ยมมีเลขโครมาติกอย่างน้อย 3 และตามทฤษฎีบทของ Brooks เลขโครมาติกจะไม่เกินดีกรีสูงสุด ยกเว้นกราฟบริบูรณ์และวงจรคี่

เครื่องคำนวณนี้ใช้อัลกอริทึมใด?

สำหรับกราฟขนาดเล็กจะใช้ Exact Backtracking เพื่อหาค่าที่ถูกต้องที่สุด สำหรับกราฟขนาดใหญ่จะใช้ฮิวริสติก DSATUR ซึ่งระบายสีจุดยอดที่ถูกล้อมรอบด้วยสีต่างๆ มากที่สุดก่อน คุณยังสามารถเลือก Welsh-Powell หรือ Greedy ได้เอง

ฉันควรใส่ข้อมูลกราฟอย่างไร?

ใช้โหมด 'รายการเส้นเชื่อม' เพื่อพิมพ์แบบ A-B ทีละบรรทัด หรือใช้ 'รายการความใกล้ชิด' เพื่อพิมพ์จุดยอดตามด้วยจุดที่เชื่อมต่อ เช่น A: B, C วงวนในตัวจะไม่ได้รับอนุญาต

ทำไม DSATUR ถึงไม่พบเลขโครมาติกที่แท้จริงเสมอไป?

เนื่องจากการระบายสีกราฟเป็นปัญหา NP-hard อัลกอริทึมที่ทำงานเร็วอาจไม่ได้คำตอบที่ดีที่สุดเสมอในกราฟที่ซับซ้อนมาก อย่างไรก็ตาม เครื่องคำนวณจะให้ขอบเขตล่างจาก Clique ที่ใหญ่ที่สุดเพื่อให้คุณประเมินความแม่นยำของคำตอบได้

การระบายสีกราฟใช้ทำอะไรในชีวิตจริง?

ใช้ในการจัดตารางสอบ, การจัดสรรความถี่คลื่นวิทยุ, การบริหารจัดการทรัพยากรในคอมพิวเตอร์, การระบายสีแผนที่ และการแก้ปัญหาที่มีข้อจำกัดด้านความขัดแย้ง

เลขโครมาติกเท่ากับจำนวน Clique ที่ใหญ่ที่สุดเสมอหรือไม่?

ไม่เสมอไป จำนวน Clique ω(G) เป็นเพียงขอบเขตล่างเท่านั้น สำหรับกราฟทั่วไป χ(G) อาจสูงกว่า ω(G) มาก เช่น ในกราฟ Mycielski ที่ไม่มีรูปสามเหลี่ยมเลยแต่ต้องการสีจำนวนมาก

เครื่องคำนวณนี้รองรับกราฟขนาดใหญ่แค่ไหน?

รองรับสูงสุด 60 จุดยอด และ 600 เส้นเชื่อม สำหรับอัลกอริทึมแบบแม่นยำ หากกราฟมีมากกว่า 18 จุดยอด ระบบอาจเปลี่ยนไปใช้ DSATUR แทนเพื่อป้องกันความล่าช้า ซึ่งเพียงพอสำหรับการเรียนรู้และการใช้งานในระดับเล็กถึงกลางส่วนใหญ่

อ่านเพิ่มเติม

• การระบายสีกราฟ — Wikipedia
• อัลกอริทึม DSATUR — Wikipedia
• พหุนามโครมาติก — Wikipedia
• ทฤษฎีบทสี่สี — Wikipedia
• ทฤษฎีบทของ Brooks — Wikipedia

การดำเนินการทางคณิตศาสตร์ขั้นสูง:

• เครื่องคิดเลข Antilog
• เครื่องคิดเลขฟังก์ชันเบต้า
• เครื่องคิดเลขสัมประสิทธิ์ทวินาม
• เครื่องคำนวณการแจกแจงแบบทวินาม
• เครื่องคิดเลขบิต
• เครื่องคำนวณทฤษฎีบทขีดจำกัดกลาง
• เครื่องคิดเลขรวม
• เครื่องคิดเลขฟังก์ชันข้อผิดพลาดเสริม
• เครื่องคิดเลขจำนวนเชิงซ้อน
• เครื่องคำนวณเอนโทรปี
• เครื่องคิดเลขฟังก์ชันผิดพลาด
• เครื่องคำนวณการสลายตัวแบบเอกซ์โพเนนเชียล
• เครื่องคำนวณการเติบโตแบบทวีคูณ ความแม่นยำสูง
• เครื่องคิดเลขเอกซ์โพเนนเชียลอินทิกรัล
• เครื่องคำนวณเลขยกกำลัง (ความแม่นยำสูง) แนะนำ
• เครื่องคำนวณแฟกทอเรียล
• เครื่องคิดเลขฟังก์ชันแกมมา
• เครื่องคำนวณอัตราส่วนทองคำ
• เครื่องคิดเลขครึ่งชีวิต
• เครื่องคำนวณอัตราการเติบโตเป็นเปอร์เซ็นต์
• เครื่องคิดเลขเรียงสับเปลี่ยน
• เครื่องคิดเลขการแจกแจงแบบปัวซง
• เครื่องคำนวณรากของพหุนามพร้อมขั้นตอนละเอียด
• เครื่องคิดเลขความน่าจะเป็น
• เครื่องคิดเลขการแจกแจงความน่าจะเป็น
• เครื่องคำนวณสัดส่วน
• เครื่องคิดเลขสูตรกำลังสอง
• เครื่องคำนวณวิทยาศาสตร์
• เครื่องคิดเลขสัญกรณ์วิทยาศาสตร์
• เครื่องคำนวณเลขนัยสำคัญ ใหม่
• เครื่องคำนวณผลรวมของลูกบาศก์
• เครื่องคิดเลขหาผลรวมของจำนวนเต็มบวก
• เครื่องคำนวณผลรวมกำลังสอง
• เครื่องสร้างตารางค่าความจริง
• เครื่องคิดเลขทฤษฎีเซต
• เครื่องสร้างแผนภาพเวนน์3เซต
• เครื่องคิดเลขทฤษฎีเศษเหลือจีน
• เครื่องคิดเลขฟังก์ชันโทเชียนต์ออยเลอร์
• เครื่องคำนวณอัลกอริทึมยูคลิดขยาย
• เครื่องคำนวณอินเวอร์สการคูณแบบโมดูลาร์
• เครื่องคำนวณเศษส่วนต่อเนื่อง
• เครื่องคำนวณเส้นทางสั้นสุดของไดค์สตรา
• เครื่องคำนวณต้นไม้แผ่ทั่วน้อยสุด
• เครื่องตรวจสอบลำดับดีกรีของกราฟ
• เครื่องคำนวณดีเรนจ์เมนต์ ซับแฟกทอเรียล
• เครื่องคำนวณจำนวนสเตอร์ลิง
• เครื่องคำนวณหลักรังนกพิราบ
• เครื่องคำนวณการแจกแจงนิ่งโซ่มาร์คอฟ
• เครื่องคำนวณการปัดเศษ ใหม่
• เครื่องคำนวณการแจกแจงทวินามลบ ใหม่
• เครื่องคำนวณการเรียงสับเปลี่ยนแบบซ้ำได้ ใหม่
• เครื่องคำนวณเลขชี้กำลังมอดุลาร์ ใหม่
• เครื่องคำนวณรากดั้งเดิม
• ตัวลดรูปพีชคณิตบูลีน ใหม่
• ตัวแก้แผนผังคาร์นอฟ (K-Map Solver) ใหม่
• เครื่องคำนวณการระบายสีกราฟ ใหม่
• เครื่องคำนวณการเรียงลำดับทอพอโลยี ใหม่
• เครื่องคำนวณเมทริกซ์ประชิด ใหม่
• เครื่องคำนวณหลักการรวม-แยก ใหม่
• ตัวแก้ปัญหาโปรแกรมเชิงเส้น ใหม่
• เครื่องแก้ปัญหาพนักงานขายเดินทาง (TSP) ใหม่
• เครื่องตรวจสอบเส้นทางฮามิลตัน ใหม่
• เครื่องตรวจสอบกราฟระนาบ ใหม่
• เครื่องคำนวณการไหลในเครือข่าย (การไหลสูงสุด) ใหม่
• ตัวแก้ปัญหาการจับคู่แต่งงานที่เสถียร ใหม่
• เครื่องคำนวณลำดับทฤษฎีกรุป ใหม่
• เครื่องคำนวณริงและฟิลด์ ใหม่