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

ปัญหาที่ได้รับความสนใจอย่างมากในเรื่องทฤษฎีกราฟ คือ ปัญหาการระบายสีกราฟ (อังกฤษ: Graph coloring problem) ซึ่งเป็นปัญหาที่เกี่ยวกับการพยายามระบายสีจุดของกราฟ โดยให้จุดที่อยู่ติดกันมีสีต่างกันและใช้สีให้น้อยที่สุด

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

ประวัติ

สาเหตุหนึ่งที่ทำให้ปัญหาเกี่ยวกับการระบายสีจุดของกราฟได้รับความสนใจศึกษาค้นคว้าเป็นอันมา ได้แก่ ความเกี่ยวข้องกันระหว่างปัญหาเช่นนี้กับปัญหาการระบายสีแผนที่ โดยไม่ให้เนื้อที่ซึ่งมีเส้นเขตแดนร่วมกันมีสีเดียวกัน เราอาจพิจารณาให้เห็นความเกี่ยวข้องอันนี้ได้ไม่ยากนัก

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

บทนิยามที่เกี่ยวข้อง

รงคเลข (Chromatic number χ (G) ) คือจำนวนที่บอกว่ากราฟ G นั้นต้องการสีน้อยที่สุดเท่าไหร่เพื่อระบายบนปมทั้งหมดในกราฟ
รงคพหุนาม (Chromatic polynomial) จำนวนวิธีในการลงสีกราฟ G โดยใช้จำนวนสีไม่มากไปกว่า จำนวนสีที่ให้มา
การระบายสีเส้นเชื่อม (Edge coloring) มีความคล้ายคลึงกับการระบายสีปม แต่จะเป็นการระบายสีลงบนเส้นเชื่อมในกราฟแทน ซึ่งมีข้อจำกัดว่าเส้นเชื่อมที่ต่อกับปมเดียวกัน จะต้องมีสีต่างกัน

ขั้นตอนวิธี

การตัดสินใจ (Decision)

Input : กราฟ G ซึ่งมีปมเป็นจำนวน v ปม, จำนวนสีเป็นจำนวนเต็ม k สี
Output : ค่าความจริงว่ากราฟ G ลงสีได้ด้วยจำนวนสีน้อยกว่าหรือเท่ากับ k สีหรือไม่
เวลาในการทำงาน : O (2ⁿn)
ความซับซ้อน : เอ็นพีบริบูรณ์

การหาค่าเหมาะสมที่สุด (Optimization)

Input : กราฟ G ซึ่งมีปมเป็นจำนวน v ปม
Output : รงคเลขของกราฟ G
เวลาในการทำงาน : O (n (log n) ⁻³ (log log n) ²)
ความซับซ้อน : เอ็นพียาก

การนับ (Counting)

Input : กราฟ G ซึ่งมีปมเป็นจำนวน v ปม, จำนวนสีเป็นจำนวนเต็ม k สี
Output : รงคพหุนามของกราฟ G
เวลาในการทำงาน : O (2ⁿn)
ความซับซ้อน : ชาร์ปพีบริบูรณ์

การประยุกต์ใช้

ปัญหาการระบายสีกราฟสามารถนำไปใช้แก้ปัญหาต่าง ๆ ในชีวิตประจำวันได้อย่างมากมาย เช่น

ปัญหาการกำหนดตารางเวลา (Scheduling problem)

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

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

ปัญหาเกม Sudoku

Input : ตารางโจทย์เกม Sudoku
Output : คำตอบของโจทย์ข้อนั้น ๆ
การแก้ปัญหา Sudoku ด้วยการระบายสีกราฟทำได้โดยการแทนช่องในตารางด้วยปมของกราฟ แล้วลากเส้นเชื่อมช่องในตารางที่ห้ามมีเลขซ้ำกันตามกฎของ Sudoku ไว้ด้วยกัน จากนั้นตรวจสอบว่าจำนวนสีที่ได้มานั้นมีค่าน้อยกว่าความกว้างของตารางโจทย์หรือไม่ ถ้าหากน้อยกว่าจึงตอบจำนวนสีที่ได้มานั้นเป็นผลเฉลยออกมาได้เลย แต่ถ้าหากมากกว่าแสดงว่าโจทย์นี้ไม่สามารถแก้ได้

ทฤษฎีที่เกี่ยวข้อง

อ้างอิง

Marx, Dániel (2004), "Graph colouring problems and their applications in scheduling", Periodica Polytechnica, Electrical Engineering, vol. 48, pp. 11–16
Björklund, A.; Husfeldt, T.; Koivisto, M. (2009), "Set partitioning via inclusion–exclusion", SIAM Journal on Computing, 39 (2): 546–563, doi:10.1137/070683933
Khot, S. (2001), "Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring", Proc. 42nd Annual Symposium on Foundations of Computer Science, pp. 600–609, doi:10.1109/SFCS.2001.959936

แหล่งข้อมูลอื่น

การระบายสีจุดของกราฟ จากเว็บ ครูบ้านนอกดอตคอม (ไทย)
ปัญหาการระบายสีกราฟ^{[ลิงก์เสีย]} จากสารานุกรมไทยสำหรับเยาวชน (ไทย)