ปัญหาการระบายสีกราฟ

ไฟล์:Colorgraph.png

การระบายสีบนปมของกราฟโดยปมที่มีเส้นเชื่อมถึงกันใช้สีไม่ซ้ำกัน

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

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

ประวัติ

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

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

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

1. รงคเลข (Chromatic number χ(G)) คือจำนวนที่บอกว่ากราฟ G นั้นต้องการสีน้อยที่สุดเท่าไหร่เพื่อระบายบนปมทั้งหมดในกราฟ
2. รงคพหุนาม (Chromatic polynomial) จำนวนวิธีในการลงสีกราฟ G โดยใช้จำนวนสีไม่มากไปกว่า จำนวนสีที่ให้มา
3. การระบายสีเส้นเชื่อม (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, 48, หน้า 11–16, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.4268&rep=rep1&type=pdf 
• 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, หน้า 600–609, doi:10.1109/SFCS.2001.959936 

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

• การระบายสีจุดของกราฟ จากเว็บ ครูบ้านนอกดอทคอม (ไทย)
• ปัญหาการระบายสีกราฟ จากสารานุกรมไทยสำหรับเยาวชน (ไทย)