ผลต่างระหว่างรุ่นของ "ทฤษฎีบทสี่สี"

เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
Danupon (คุย | ส่วนร่วม)
Danupon (คุย | ส่วนร่วม)
บรรทัด 16:
หลักฐานอ้างอิงที่มีการตีพิมพ์เป็นอันแรกถูกพบในงานของ [[อาร์เทอร์ เคย์เลย์]] (Arthur Cayley) ''On the colourings of maps.'', Proc. [[Royal Geography Society]] 1, 259-261, 1879.
 
นับตั้งแต่ข้อความคาดการณ์นี้ถูกประกาศขึ้นมา ก็มีผู้คนจำนวนมากต้องประสบความล้มเหลวในการพิสูจน์มัน บทพิสูจน์หนึ่งของทฤษฎีททฤษฎีบทนี้คืองานของ [[อัลเฟรด เคมป์]] (Alfred Kempe)ในปี [[พ.ศ.2422]] ซึ่งเป็นชิ้นที่ผู้คนยอมรับกันทั่วไป บทพิสูจน์อีกอันหนึ่งคือของ[[ปีเตอร์ เทท]](Peter Tait)ในปี [[พ.ศ.2423]] จวบจนกระทั่งปี [[พ.ศ.2433]] จึงจะมีผู้แสดงได้ว่าบทพิสูจน์ของเคมป์มีข้อผิดพลาด เขาคือ [[เพอร์ซี เฮวูด]](Percy Heawood) จึงได้แสดงว่าบทพิสูจน์ของเคมป์มีข้อผิดพลาด และใน [[พ.ศ.2434]] [[จูเลียส ปีเตอร์เซน]] (Julius Petersen) จึงได้แสดงว่าบทพิสูจน์ของเททผิดพลาด น่าแปลกใจว่าไม่มีผู้ใดเห็นข้อผิดพลาดเหล่านี้ในบทพิสูจน์แต่ละอันถึง 11 ปี
 
ใน [[พ.ศ.2433]] นอกจากเฮวูดจะชี้ให้เห็นถึงข้อผิดพลาดของบทพิสูจน์ของเคมป์แล้ว เขายังได้พิสูจน์ว่า[[กราฟเชิงระนาบ]]ทุกอันสามารถระบายได้ด้วยสี 5 สี - ดู [[ทฤษฎีบทห้าสี]]
บรรทัด 28:
จนกระทั่งปี [[พ.ศ.2516]] นั่นเอง จึงได้มีผู้พิสูจน์ข้อคาดการณ์สี่สีนี้ได้สำเร็จ โดย [[เคนเน็ท แอพเพล]] (Kenneth Appel) และ [[โวล์ฟแกง เฮเคน]] (Wolfgang Haken) แห่ง[[มหาวิทยาลัยอิลลินอยส์ เออร์บานา-แชมเปญ]] โดยได้รับคำปรึกษาทางด้านอัลกอริทึมจาก เจ คอช (J. Koch)
 
บทพิสูจน์เริ่มต้นด้วยการลดรูปแบบของแผนที่ทั้งหมดให้เหลือเพียง 1,936 รูปแบบ (และภายหลังสามารถลดลงเหลือ 1,476 รูปแบบ) จากนั้นจึงนำไปตรวจสอบทีละอันด้วยคอมพิวเตอร์ และมีการตรวจสอบซ้ำสองแยกต่างหากโดยโปรแกรมและเครื่องคอมพิวเตอร์ที่ต่างกัน อย่างไรก็ตามบทพิสูจน์นี้มีความยาวถึง 500 หน้า ที่และเต็มไปด้วยตัวอย่างค้านของตัวอย่างค้าน(counter-counter-example) ที่เขียนด้วยมือ โดยส่วนใหญ่เป็นการทดสอบ[[การระบายสีกราฟ]] ของลูกชายวัยสิบกว่า ๆ ของเฮเคน โปรแกรมคอมพิวเตอร์นี้ใช้เวลาทำงานหลายร้อยชั่วโมง
 
ในปี [[พ.ศ.2539]] [[นีล โรเบิร์ตสัน]] (Neil Robertson), [[แดเนียล แซนเดอร์ส]] (Daniel Sanders), [[พอล ซีมัวร์]] (Paul Seymour) และ [[โรบิน โทมัส]] (Robin Thomas) สร้างบทพิสูจน์ที่คล้าย ๆ กัน แต่มีกรณีที่ต้องทดสอบเพียง 633 กรณี บทพิสูจน์อันใหม่นี้ก็ยังจำเป็นต้องใช้คอมพิวเตอร์ช่วย และเป็นการยากที่จะตรวจสอบด้วยคน