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

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

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

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

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

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

## บทนิยามที่เกี่ยวข้อง
# **รงคเลข (Chromatic number χ (G) ) ** คือจำนวนที่บอกว่ากราฟ G นั้นต้องการสีน้อยที่สุดเท่าไหร่เพื่อระบายบนปมทั้งหมดในกราฟ
# **รงคพหุนาม (Chromatic polynomial) ** จำนวนวิธีในการลงสีกราฟ G โดยใช้จำนวนสีไม่มากไปกว่า จำนวนสีที่ให้มา
# **การระบายสีเส้นเชื่อม (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 ไว้ด้วยกัน จากนั้นตรวจสอบว่าจำนวนสีที่ได้มานั้นมีค่าน้อยกว่าความกว้างของตารางโจทย์หรือไม่ ถ้าหากน้อยกว่าจึงตอบจำนวนสีที่ได้มานั้นเป็นผลเฉลยออกมาได้เลย แต่ถ้าหากมากกว่าแสดงว่าโจทย์นี้ไม่สามารถแก้ได้

## ทฤษฎีที่เกี่ยวข้อง
* ทฤษฎีกราฟ
* ทฤษฎีบทสี่สี
* ทฤษฎีบทห้าสี

## อ้างอิง
* 
* 
* 

## แหล่งข้อมูลอื่น
* การระบายสีจุดของกราฟ จากเว็บ ครูบ้านนอกดอตคอม
* ปัญหาการระบายสีกราฟ จากสารานุกรมไทยสำหรับเยาวชน

หมวดหมู่:การให้สีกราฟ
หมวดหมู่:ทฤษฎีกราฟ
หมวดหมู่:ปัญหาการคำนวณในทฤษฎีกราฟ
หมวดหมู่:ปัญหาเอ็นพีบริบูรณ์