การระบายสีกราฟ — จำนวนโครมาติกและการประยุกต์

การระบายสีกราฟโดยทั่วไปหมายถึง การระบายสีจุดยอด: กำหนดสีให้แต่ละจุดยอดโดยที่จุดยอดที่อยู่ติดกันต้องไม่ใช้สีเดียวกัน จำนวนสีน้อยที่สุดที่ทำได้เรียกว่า จำนวนโครมาติก เขียนเป็น $\chi(G)$

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

นิยามการระบายสีกราฟในหนึ่งนาที

ในการระบายสีแบบถูกต้อง ทุกเส้นเชื่อมจะต้องเชื่อมจุดยอดสองจุดที่มีสีต่างกัน นี่คือกฎทั้งหมด

ดังนั้นถ้า $\chi(G)=3$ จะมีข้อเท็จจริงสองข้อที่เป็นจริงพร้อมกัน:

• มีการระบายสีแบบถูกต้องด้วย $3$ สี
• ไม่มีการระบายสีแบบถูกต้องด้วยเพียง $2$ สี

นี่จึงเป็นเหตุผลว่าทำไมจำนวนโครมาติกจึงเป็น “ค่าน้อยที่สุด” ไม่ใช่แค่จำนวนสีที่คุณบังเอิญใช้ในรูปวาดหนึ่งรูป

ถ้าไม่มีการระบุเป็นอย่างอื่น การระบายสีกราฟในวิชาเบื้องต้นมักหมายถึงการระบายสี จุดยอด ของกราฟไม่มีทิศทางแบบเชิงเดี่ยว การระบายสีเส้นเชื่อมเป็นอีกปัญหาหนึ่งที่มีกฎต่างออกไป

จำนวนโครมาติกวัดอะไรจริง ๆ

ชื่อของสีไม่สำคัญ คุณจะใช้สีแดง น้ำเงิน และเขียว หรือใช้ป้ายกำกับ $1$, $2$ และ $3$ ก็ได้

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

มุมมองนี้เองที่ทำให้การระบายสีกราฟมีประโยชน์ในปัญหาการจัดตารางและการจัดสรรทรัพยากร สีหนึ่งสีมักหมายถึง “รายการเหล่านี้ใช้ช่วงเวลาเดียวกันได้”

ตัวอย่างทำจริง: ทำไมวงจร 5 จุดจึงต้องใช้ 3 สี

พิจารณากราฟวงจร $C_5$ ที่มีเส้นเชื่อม $AB, BC, CD, DE,$ และ $EA$

ลองใช้ $2$ สีก่อน ให้ $A$ เป็นสี $1$ และ $B$ เป็นสี $2$ จากนั้นการระบายสีรอบวงจรจะถูกบังคับให้เป็นดังนี้:

$$A=1,\quad B=2,\quad C=1,\quad D=2$$

ตอนนี้ดูที่ $E$ จุดนี้ติดกับทั้ง $D$ และ $A$ ดังนั้นจึงใช้สี $2$ ไม่ได้เพราะชนกับ $D$ และใช้สี $1$ ไม่ได้เพราะชนกับ $A$

ดังนั้น $2$ สีจึงใช้ไม่ได้

แต่ $3$ สีใช้ได้จริง การระบายสีแบบถูกต้องแบบหนึ่งคือ

$$A=1,\quad B=2,\quad C=1,\quad D=2,\quad E=3$$

ดังนั้น

$$\chi(C_5)=3$$

ตัวอย่างนี้ควรจำไว้ เพราะมันแสดงรูปแบบสำคัญอย่างหนึ่ง: สำหรับกราฟวงจร วงจรคู่สามารถระบายได้ด้วย $2$ สี แต่วงจรคี่ต้องใช้ $3$ สี

วิธีคิดเรื่องการระบายสีกราฟในกราฟขนาดเล็ก

มีการตรวจสอบเร็ว ๆ อยู่สองอย่างที่ช่วยได้

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

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

ข้อผิดพลาดที่พบบ่อยในโจทย์การระบายสีกราฟ

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

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

นักเรียนบางคนยังสับสนระหว่างการระบายสีจุดยอดกับการระบายสีเส้นเชื่อม ในหน้านี้ กฎพูดถึง จุดยอด ที่อยู่ติดกัน ไม่ใช่เส้นเชื่อมที่อยู่ติดกัน

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

การระบายสีกราฟถูกใช้ที่ไหน

การประยุกต์ใช้มาตรฐานอย่างหนึ่งคือการจัดตารางสอบ สมมติว่าแต่ละจุดยอดแทนข้อสอบหนึ่งวิชา และเส้นเชื่อมหมายถึงข้อสอบสองวิชามีนักเรียนร่วมกัน จึงไม่สามารถจัดเวลาเดียวกันได้ ในกรณีนี้ สีหนึ่งสีสามารถแทนช่วงเวลาสอบหนึ่งช่วงได้

ในแบบจำลองนี้ จำนวนโครมาติกบอกจำนวนช่วงเวลาน้อยที่สุดที่เป็นไปได้ ถ้า $\chi(G)=4$ ก็แปลว่าไม่มีตารางที่ถูกต้องซึ่งใช้เพียง $3$ ช่วงเวลาได้

แนวคิดเดียวกันนี้ยังปรากฏในปัญหาการระบายสีแผนที่ ซึ่งพื้นที่ที่อยู่ติดกันต้องต่างสีกัน และในการออกแบบคอมไพเลอร์ ซึ่งตัวแปรที่ต้องใช้งานพร้อมกันไม่สามารถใช้รีจิสเตอร์เดียวกันได้

ลองทำโจทย์การระบายสีกราฟที่คล้ายกัน

วาดกราฟที่มีจุดยอด $P,Q,R,S,T$ และมีเส้นเชื่อม $PQ, QR, RS, ST, TP,$ และ $PR$

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