ทฤษฎีบทห้าสี

จากวิกิพีเดีย สารานุกรมเสรี

ทฤษฎีบทห้าสี (five color theorem) ในทางทฤษฎีกราฟ กล่าวว่า แผนที่สามารถระบายสีได้ด้วยสีไม่เกินห้าสี ที่จริงแล้วมันเป็นจริงโดยอัตโนมัติตามทฤษฎีบทสี่สีอยู่แล้ว แต่ทฤษฎีบทนี้มีความน่าสนใจตรงที่มันสามารถพิสูจน์ได้ง่ายกว่ามาก

[แก้] บทพิสูจน์โดยสังเขป

จุดยอด v, จุดยอดโดยรอบ และวิถีสองวิถีที่มีเส้นทับกัน ซึ่งทำให้ขัดกับความเป็นระนาบของ G

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

ทฤษฎีนี้ใช้ความจริงที่ว่า กราฟเชิงระนาบทุกกราฟต้องมีอย่างน้อย 1 จุดยอด ที่มีดีกรีไม่เกิน 5 (วิธีการพิสูจน์วิธีหนึ่ง คือ การใช้ลักษณะเฉพาะของออยเลอร์)

ให้ v คือ จุดยอดที่มีดีกรีไม่เกิน 5 นี้ เราสามารถลบ v ออกจาก G และอ้างโดยอุปนัยว่า G−{v} สามารถระบายได้ด้วยสีไม่เกิน 5 สี จากนั้นนำ v ใส่กลับเข้ามาแล้วระบายสีให้กับมัน ถ้าเราไม่สามารถระบายสี v ได้ด้วยสีใดสีหนึ่ง แสดงว่า v เชื่อมอยู่กับจุดยอด 5 จุด ที่มีสีต่างๆกัน ให้จุด 5 จุดนี้ชื่อ v₁, v₂, v₃, v₄, v₅ ตามลำดับเข็มนาฬิกา (ลำดับนี้สามารถขึ้นอยู่กับวิธีการที่เราวาดรูปกราฟ G) และสมมติให้จุดยอดเหล่านี้มีสี 1, 2, 3, 4, 5 ตามลำดับ

เปลี่ยนสี v₁ ให้เป็น 3 แล้วเปลี่ยนสีจุดยอดทุกอันที่ชน (การชนในที่นี้ คือ มีสีซ้ำกันและมีเส้นเชื่อมต่อถึงกันอยู่) ให้มีสี 1 จากนั้นเปลี่ยนจุดยอดทุกอันที่ชนกับสี 1 นี้ ให้เป็นสี 3 ทำลักษณะเช่นนี้ไปเรื่อย ๆ จนกระทั้งไม่มีการชนเกิดขึ้นอีก หากการทำเช่นนี้ไม่ได้ไปเปลี่ยนสี v₃ เราจะสามารถระบายสี 1 ลงบน v ได้ แต่หาก v₃ ถูกเปลี่ยนสี แสดงว่ามีวิถีที่ประกอบด้วยจุดยอดที่มีสี 1 และ 3 เท่านั้น เชื่อม v₁ กับ v₃ อยู่ (ดูรูปประกอบ)

เปลี่ยนสีของ v₂ ให้เป็น 4 โดยใช้วิธีการเดียวกับการเปลี่ยนสีของ v₁ เราแน่ใจว่า v₄ จะไม่ถูกเปลี่ยนสีเป็น 2 มิฉะนั้นแล้ววิถีที่มีจุดยอดสี 2 และ 4 เท่านั้น ที่เชื่อมระหว่าง v₂ กับ v₄ จะตัดกับวิถีที่เชื่อม v₁ กับ v₃ ที่ได้กล่าวก่อนหน้านี้ ซึ่งขัดกับความเป็นระนาบของ G (ดูรูปประกอบ) ดังนั้น เราสามารถระบาย v ด้วยสี 2 ได้