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

ใช้โหมดรายการเส้นเชื่อมเพื่อพิมพ์หนึ่งเส้นเชื่อมต่อหนึ่งบรรทัด เช่น A-B หรือคั่นด้วยจุลภาค เช่น A-B, B-C, C-A ใช้โหมดรายการความใกล้ชิดเพื่อเขียนจุดยอดแต่ละจุดตามด้วยเครื่องหมายทวิภาคและเพื่อนบ้าน เช่น A: B, C ส่วนวงวนในตัว (Self-loops) จะถูกปฏิเสธเนื่องจากจุดยอดไม่สามารถระบายสีให้ต่างจากตัวมันเองได้

การระบายสีกราฟใช้ในโลกแห่งความเป็นจริงอย่างไร?

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

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

ไม่ จำนวนคลิก (Clique number) omega(G) เป็นขอบเขตล่างของเลขโครมาติก chi(G) เสมอ และจะเท่ากันสำหรับกราฟสมบูรณ์ (Perfect graphs) เช่น กราฟสองส่วน, ต้นไม้, กราฟช่วง และกราฟคอร์ดัล สำหรับกราฟทั่วไป chi(G) อาจมากกว่า omega(G) ได้ ตัวอย่างคลาสสิกคือกราฟ Mycielski ซึ่งไม่มีรูปสามเหลี่ยมแต่ต้องการจำนวนสีมากอย่างไม่จำกัด

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

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

⚡ ลองตัวอย่าง:

4-cycle C₄ Triangle K₃ Complete K₅ Pentagon C₅ Wheel W₆ Bipartite K₃,₃ ตัวอย่างความใกล้ชิด การจัดตารางสอบ

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

⬌ รายการขอบ (Edge list)

⧇ รายการประชิด (Adjacency list)

ข้อมูลกราฟ

รูปแบบเส้นเชื่อม: A-B หรือ A B คั่นด้วยจุลภาคหรือขึ้นบรรทัดใหม่ สูงสุด 60 จุดยอด และ 600 เส้นเชื่อม

รูปแบบความใกล้ชิด: A: B, C, D — หนึ่งจุดยอดต่อบรรทัด ตามด้วยเพื่อนบ้าน

อัลกอริทึม

โหมด 'อัตโนมัติ' จะเลือก Backtracking แบบแม่นยำสำหรับกราฟขนาดเล็ก และ DSATUR สำหรับกราฟขนาดใหญ่

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

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

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

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

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

นิยามเลขโครมาติก

χ(G) = min { k : G admits a proper k-coloring }

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

ขอบเขตทั่วไป: 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)

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

A-B, B-C, C-D, D-A
A-C

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

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

A: B, C, D
B: A, D
C: A
D: A, B

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

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

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

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

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

ให้แต่ละวิชาเป็นจุดยอด และลากเส้นเชื่อมระหว่างวิชาที่มีนักเรียนลงทะเบียนซ้ำกันอย่างน้อยหนึ่งคน การระบายสีที่ถูกต้องด้วย 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 แทนเพื่อป้องกันความล่าช้า ซึ่งเพียงพอสำหรับการเรียนรู้และการใช้งานในระดับเล็กถึงกลางส่วนใหญ่