ทฤษฎีบทห้าสี - วิกิพีเดีย

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

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

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

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

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

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

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

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

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

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

## [แก้] ดูเพิ่ม

- ทฤษฎีบทสี่สี

ดึงข้อมูลจาก "http://th.wikipedia.org../../../%E0%B8%97/%E0%B8%A4/%E0%B8%A9/%E0%B8%97%E0%B8%A4%E0%B8%A9%E0%B8%8E%E0%B8%B5%E0%B8%9A%E0%B8%97%E0%B8%AB%E0%B9%89%E0%B8%B2%E0%B8%AA%E0%B8%B5.html".

หมวดหมู่: ทฤษฎีบท | ทฤษฎีกราฟ

##### Views

- บทความ
- อภิปราย
- รุ่นปัจจุบัน

##### ค้นหา

##### ภาษาอื่น

- Deutsch
- English
- Suomi
- Magyar