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