Graph Coloring
Graph coloring หรือบางที่เรียก vertex coloring เป็นการให้สีหรือติดป้าย (labeling) แก่ vertices โดยที่ vertices ทุกคู่ที่เชื่อมต่อกัน (adjacent vertices) จะต้องไม่มีสีเดียวกัน
1. เมื่อกระบวนการ coloring เสร็จสิ้นลง ถ้าจำนวนสีที่ใช้เป็น k จะเรียกว่า k-coloring เช่น 2-coloring, 3-coloring
2. ค่า \( k \) ที่น้อยที่สุดเรียกว่า chromatic number ของ graph นั้นๆ
 |
| รูปที่ 1 |
ตัวอย่าง graph ในรูปที่ 1 เรียกว่าเป็น colored properly graph มีค่า \( k =5 \) แต่ค่านี้อาจยังไม่ใช่ chromatic number ก็ได้
มีการประยุกต์ใช้งาน graph coloring ในหลายด้าน เช่น การจัดตารางเวลาทำงาน (Scheduling) , Time table, Sudoku,Conflick resolution ฯลฯ ตัวอย่างงานที่เป็นที่รู้จักกันคือการให้สีแผนที่ด้วย four colors theorem ซึ่งพิสูจน์ว่าที่ใช้สีเพียง 4 สีก็เพียงพอสำหรับการให้สีทุกพื้นที่ในแผนที่โดยที่พื้นที่ที่ติดกันจะไม่ใช้สีเดียวกัน (รูปที่ 2)
 |
| รูปที่ 2 |
การหาค่า Chromatic Number
ถ้ากำหนด graph มาใช้ตามรูปที่ 3 วิธีการง่ายที่สุดในการให้สีคือให้สีแต่ละ vertice แยกกันไป จะใช้จำนวนสีทั้งหมด 5 สี แต่วิธีการนี้ไม่ใช่การหาค่า chromatic number เพราะ 5 อาจไม่ใช่ค่าที่น้อยที่สุด ในตอนนี้จะยกตัวอย่างวิธีการหาค่า chromatic number ด้วย backtracking algorithm ซึ่งมีขั้นตอนดังนี้
 |
| รูปที่ 3 |
1. เริ่มต้นด้วย กำหนดให้สี node ใด node หนึ่งในที่นี้ให้เป็น A ด้วยสี CL1 (ใช้อักษรแทน ยังไม่ต้องกำหนดสีจริง) ในขณะนี้ chromatic number = 1
2. ไปยัง node ที่เชื่อมกับ A ซึ่งคือ B และ C เลือก B มาพิจารณาก่อน ให้สีแก่ B แต่ต้องไม่ซ้ำกับ A ดังนั้นให้ค่าสีของ B เป็น CL2 ในขณะนี้ chromatic number = 2
3. ไปยัง node ถัดไปคือ C ที่เชื่อมกับ A แต่ไม่เชื่อมกับ B ดังนั้น C จะให้ค่าสี CL1 (ซ้ำกับ A) เพื่อให้ได้ chromatic number เป็นมีค่าน้อยที่สุด จึงเลือกสีที่ใช้กับ node อื่นที่ไม่เชื่อมกับ C นั่นคือ CL2 ในขณะนี้ chromatic number ยังคงเป็น 2 เท่าเดิม
4. ไปยัง node ถัดไปคือ D ที่เชื่อมกับ B และ C แต่ไม่เชื่อมกับ A ดังนั้นใช้หลักการเดียวกับข้อ 3 คือไม่ใช้สีเดียวกับ B และ C แต่ใช้สี CL1 ซ้ำกับ A ได้ เพื่อให้ได้ chromatic number เป็นมีค่าน้อยที่สุด ในขณะนี้ chromatic number ยังคงเป็น 2 เท่าเดิม
5. ไปยัง node สุดท้ายคือ D ที่เชื่อมกับ D จึงให้ค่าสี CL1 (ซ้ำกับ A,D)ไม่ได้ เพื่อให้ได้ chromatic number เป็นมีค่าน้อยที่สุด จึงเลือกสีที่ใช้กับ node อื่นที่ไม่เชื่อม นั่นคือ CL2
สุดท้ายก็สามารถให้ค่าสีได้ครบทุก node โดยยังทำให้ค่า chromatic number น้อยที่สุดคือ 2 ไม่ใช่ 5 ตามแบบวิธี naive ถ้ากำหนดให้ CL1 เป็นสีฟ้าและ CL2 เป็นสีเขียว ผลที่ได้จะแสดงในรูปที่ 4
 |
| รูปที่ 4 |
ตัวอย่างการประยุกต์ใช้
การนำไปใช้ในการจัดตารางเวลา สมมุติมีนักศึกษาแผนก A,B,C,D และ E มีวิชาที่ต้องเรียนวิชา Physics, Microprocessor, Operating system, Calculus และ Electronics แยกตามสาขาตามตารางที่ 1 ตามที่แสดงเป็นจุดสีเขียว
 |
| ตารางที่ 1 |
จากตารางจะเห็นว่าทุกวิชาที่นักศึกษาลงทะเบียนมากกว่า 1 สาขา ดังนั้นการจัดตารางเวลาสอบจะต้องไม่ทำให้เกิดปัญหาว่านักศึกษาต้องสอบมากกว่า 1 วิชาในเวลาเดียวกัน
ในการแก้ปัญหานี้ สามารถใช้หลักการของ graph coloring มาช่วยแก้ได้ ดังนี้
1. สร้าง graph ของรายวิชาที่ต้องเรียน แยกตามสาขา โดยใช้ vertices แทนรายวิชา และ edges แทนความสัมพันธ์ว่ารายวิชาว่านั้นต้องเรียนในสาขาเดียวกัน
2. รวม graph ทั้งหมดให้เป็น graph เดียว
3. ใช้ขั้นตอนการทำงาน backtracking algorithm
จะได้ chromatic number 3 ถ้าแทนสีแต่ละสีด้วยวันที่ก็จะได้ว่าการจัดสอบตัองจัด 3 วัน โดย
⊕ Microprocessor และ Operating system สอบในวันเดียวกัน
⊕ Calculus และ Physics สอบในวันเดียวกัน
⊕ Electronics สอบวันอื่น
ความคิดเห็น
แสดงความคิดเห็น