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

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

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

ประวัติ แก้

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

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

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

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

ขั้นตอนวิธี แก้

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

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

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

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

การนับ (Counting) แก้

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

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

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

ปัญหาการกำหนดตารางเวลา (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

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