ผลต่างระหว่างรุ่นของ "ทฤษฎีบทสี่สี"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ลไม่มีความย่อการแก้ไข |
เพิ่มหัวข้อ ''ไม่เกี่ยวกับการทำแผนที่'' |
||
บรรทัด 35:
ตั้งแต่ได้มีการพิสูจน์ทฤษฎีบทนี้สำเร็จ อัลกอริทึมที่มีประสิทธิภาพมากมายก็ได้ถูกสร้างขึ้นสำหรับระบายสีแผนที่ด้วนสี่สี โดยทำงานในเวลาเพียง O(''n''<sup>2</sup>) เมื่อ ''n'' คือจำนวนจุดยอด นอกจากนี้ยังมีอัลกอริทึมทรงประสิทธิภาพที่สามารถตรวจสอบได้ว่าแผนที่ใช้สี 1 หรือ 2 สีระบายได้หรือไม่ สำหรับกรณี 3 สีนั้นเป็นปัญหา[[เอ็นพีสมบูรณ์]] และดังนั้นจึงเป็นไปได้สูงว่าจะไม่มีวิธีการเร็ว ๆ การตรวจสอบว่ากราฟโดยทั่วไป (ไม่จำเป็นต้องเป็นกราฟเชิงระนาบ) สามารถระบายด้วยสี่สีได้หรือไม่ ก็เป็นปัญหา[[เอ็นพีสมบูรณ์]]เช่นกัน
== ไม่เกี่ยวกับการทำแผนที่ ==
ทฤษฎีบทสี่สีนี้ไม่ได้ถูกค้นพบ หรือมีต้นกำเนิด เกี่ยวข้องใดๆกับการเขียนแผนที่จริงๆ ตามคำกล่าวอ้างของเคนเนธ เมย์ นักประวัติศาสตร์คณิตศาสตร์ ซึ่งได้ศึกษาตัวอย่างของสมุดแผนที่ในห้องสมุดรัฐสภาสหรัฐฯ เขาสรุปว่า ไม่มีข้อบ่งชี้เลยว่าจะมีความพยายามที่จะลดจำนวนสีที่ใช้ แผนที่ส่วนใหญ่ใช้มากกว่าสี่สี และเมื่อใดก็ตามที่ใช้เพียงสี่สี จำนวนสีที่ต้องการจริงๆกลับน้อยกว่านั้น
หนังสือเรียนวิชาการเขียนแผนที่ และประวัติศาสตร์การเขียนแผนที่ ไม่ได้กล่าวถึงทฤษฎีบทสี่สีเลย ถึงแม้ว่าการระบายสีแผนที่จะเป็นหัวข้อหนึ่งที่ให้ความสนใจกัน นักเขียนแผนที่บอกว่า โดยทั่วไปพวกเขาจะสนถึงการระบายสีให้เกิดความสมดุลย์ ไม่ให้มีสีใดกลืนสีอื่นไปหมดมากกว่า เรื่องจำนวนสีไม่ได้อยู่ในความสนใจของพวกเขาเท่าใดนัก
==รูปอย่างเป็นทางการในทฤษฎีกราฟ==
| |||