วิกิพีเดียภาษาไทย
กลับไปหน้าบทความ

อ่าน 14 นาที

ทฤษฎีสี่สี

เปลี่ยนทางจากการสะกดแบบอังกฤษ/การเปลี่ยนเส้นทางที่ไม่สามารถพิมพ์ได้

ในทางคณิตศาสตร์ทฤษฎีบทสี่สีหรือทฤษฎีบทแผนที่สี่สีระบุว่าไม่จำเป็นต้องใช้สีมากกว่าสี่สีในการระบายสีบริเวณต่างๆ ของแผนที่เพื่อไม่ให้บริเวณที่อยู่ติดกันสองบริเวณมีสีเดียวกัน คำ

ทฤษฎีสี่สี

ตัวอย่างแผนที่สี่สี
แผนที่สี่สีแสดงรัฐต่างๆ ของสหรัฐอเมริกา (ไม่รวมทะเลสาบและมหาสมุทร)

ในทางคณิตศาสตร์ทฤษฎีบทสี่สีหรือทฤษฎีบทแผนที่สี่สีระบุว่าไม่จำเป็นต้องใช้สีมากกว่าสี่สีในการระบายสีบริเวณต่างๆ ของแผนที่เพื่อไม่ให้บริเวณที่อยู่ติดกันสองบริเวณมีสีเดียวกัน คำ ว่าติดกันหมายความว่าสองบริเวณนั้นมีขอบเขตร่วมกันที่มีความยาวไม่เป็นศูนย์ (กล่าวคือ ไม่ใช่เพียงแค่จุดมุมที่บริเวณสามบริเวณขึ้นไปมาบรรจบกัน) [ 1 ] นับเป็น ทฤษฎีบทสำคัญแรกที่ได้รับการพิสูจน์โดยใช้คอมพิวเตอร์ ในตอนแรก การพิสูจน์นี้ไม่ได้รับการยอมรับจากนักคณิตศาสตร์ทุกคน เพราะการพิสูจน์โดยใช้คอมพิวเตอร์ช่วยนั้นเป็นไปไม่ได้ที่มนุษย์จะตรวจสอบด้วยมือ [ 2 ] นับตั้งแต่นั้นมา การพิสูจน์นี้ได้รับการยอมรับอย่างกว้างขวาง แม้ว่าจะยังคงมีข้อสงสัยอยู่บ้าง[ 3 ]

ทฤษฎีบทนี้เป็นเวอร์ชันที่แข็งแกร่งกว่าของทฤษฎีบทห้าสีซึ่งสามารถพิสูจน์ได้โดยใช้เหตุผลที่ง่ายกว่ามาก แม้ว่าทฤษฎีบทห้าสีที่อ่อนกว่าจะได้รับการพิสูจน์แล้วในช่วงปี 1800 แต่ทฤษฎีบทสี่สีกลับไม่ได้รับการพิสูจน์จนกระทั่งปี 1976 เมื่อKenneth AppelและWolfgang Haken ได้พิสูจน์มัน ด้วยการพิสูจน์โดยใช้คอมพิวเตอร์ช่วยซึ่งเกิดขึ้นหลังจากมีการพิสูจน์ที่ผิดพลาดและตัวอย่างค้านที่เข้าใจผิดมากมายในช่วงหลายทศวรรษก่อนหน้านั้น

การพิสูจน์ของ Appel–Haken ดำเนินการโดยการวิเคราะห์ "การจัดเรียงที่ลดรูปได้" จำนวนมาก ซึ่งเป็นตัวอย่างของแผนที่ที่มีคุณสมบัติเฉพาะอย่างหนึ่ง ต่อมาในปี 1997 Robertson, Sanders, Seymour และ Thomas ได้ปรับปรุงวิธีการนี้ โดยลดจำนวนการจัดเรียงดังกล่าวเหลือเพียง 633 ตัวอย่าง ซึ่งก็ยังคงเป็นการวิเคราะห์กรณีที่ยาวมากอยู่ดี ในปี 2005 Georges Gonthier ได้ตรวจสอบทฤษฎีบทนี้โดยใช้ ซอฟต์แวร์พิสูจน์ทฤษฎีบทอเนกประสงค์

สูตร

การระบายสีแผนที่สามารถอธิบายได้ในแง่ของทฤษฎีกราฟโดยพิจารณาในแง่ของการสร้างการระบายสีกราฟของกราฟระนาบของความสัมพันธ์ระหว่างภูมิภาค ในแง่ของทฤษฎีกราฟ ทฤษฎีบทกล่าวว่าสำหรับกราฟระนาบที่ไม่มีวงวนจี{\displaystyle G}โดยแสดงด้วยχ(จี){\displaystyle \chi (G)}จำนวนสีของมันχ(จี)≤4{\displaystyle \chi (G)\leq 4}.

เพื่อให้สิ่งนี้มีความหมาย จำเป็นต้องตีความข้อความที่เข้าใจง่ายของทฤษฎีสี่สีที่ว่า "เมื่อแบ่งระนาบออกเป็นส่วนๆ ที่อยู่ติดกันแล้ว ส่วนต่างๆ เหล่านั้นสามารถระบายสีได้โดยใช้สีไม่เกินสี่สี โดยที่ไม่มีส่วนใดที่อยู่ติดกันมีสีเดียวกัน"

ประการแรก พื้นที่จะถือว่าอยู่ติดกันหากมีส่วนของเส้นแบ่งเขตที่ใช้ร่วมกัน พื้นที่สองแห่งที่ใช้เส้นแบ่งเขตที่ใช้ร่วมกันเพียงบางส่วนจะไม่ถือว่าอยู่ติดกัน (มิเช่นนั้น แผนที่ในรูปทรงแผนภูมิวงกลมจะทำให้มีพื้นที่จำนวนมากที่ 'อยู่ติดกัน' ที่มุมร่วมกัน และจะทำให้ต้องใช้สีจำนวนมากตามไปด้วย) ประการที่สอง ไม่อนุญาตให้มีพื้นที่แปลกประหลาด เช่น พื้นที่ที่มีพื้นที่จำกัดแต่มีเส้นรอบวงยาวไม่สิ้นสุด แผนที่ที่มีพื้นที่ดังกล่าวอาจต้องใช้สีมากกว่าสี่สี[ 4 ] (เพื่อความปลอดภัย เราสามารถจำกัดเฉพาะภูมิภาคที่มีขอบเขตประกอบด้วยส่วนของเส้นตรงจำนวนจำกัดเท่านั้น อนุญาตให้ภูมิภาคมีส่วนที่ล้อมรอบ กล่าวคือ ภูมิภาคนั้นล้อมรอบภูมิภาคอื่นตั้งแต่หนึ่งภูมิภาคขึ้นไป) โปรดทราบว่าแนวคิดของ "ภูมิภาคที่ต่อเนื่องกัน" (ในทางเทคนิค: เซตย่อย เปิดที่เชื่อมต่อกัน ของระนาบ) ไม่เหมือนกับ "ประเทศ" บนแผนที่ปกติ เนื่องจากประเทศไม่จำเป็นต้องต่อเนื่องกัน: อาจมีส่วนที่ล้อมรอบเช่นแองโกลากับจังหวัดกาบินดา อาเซอร์ไบจานกับสาธารณรัฐปกครองตนเองนัคชิวานรัสเซียกับแคว้นคาลินินกราดฝรั่งเศสกับดินแดนโพ้นทะเลและสหรัฐอเมริกากับรัฐอะแลสกาหากเราต้องการให้ดินแดนทั้งหมดของประเทศได้รับสีเดียวกัน สีทั้งสี่สีอาจไม่เพียงพอเสมอไป ตัวอย่างเช่น ลองพิจารณาแผนที่แบบง่าย:

ในแผนที่นี้ พื้นที่สองแห่งที่ระบุว่าAอยู่ในประเทศเดียวกัน หากเราต้องการให้พื้นที่ทั้งสองแห่งมีสีเดียวกัน จะต้องใช้สีทั้งหมดห้าสี เนื่องจาก พื้นที่ A ทั้งสอง แห่งอยู่ติดกับพื้นที่อีกสี่แห่ง ซึ่งแต่ละแห่งก็อยู่ติดกับพื้นที่อื่นๆ ทุกแห่งอีกเช่นกัน

แผนที่ที่มีสี่ภูมิภาค และกราฟระนาบที่สอดคล้องกันซึ่งมีสี่จุดยอด

การกล่าวถึงทฤษฎีบทอย่างง่ายกว่านี้ใช้ทฤษฎีกราฟเซตของภูมิภาคในแผนที่สามารถแสดงได้อย่างเป็นนามธรรมมากขึ้นในรูปของกราฟแบบไม่มีทิศทางซึ่งมีจุดยอดสำหรับแต่ละภูมิภาคและขอบสำหรับทุกคู่ของภูมิภาคที่ใช้ส่วนของขอบเขตร่วมกัน กราฟนี้เป็นกราฟระนาบ กล่าว คือ สามารถวาดลงบนระนาบได้โดยไม่มีจุดตัด โดยการวางจุดยอดแต่ละจุดไว้ในตำแหน่งที่เลือกไว้โดยพลการภายในภูมิภาคที่จุดยอดนั้นสอดคล้อง และโดยการวาดขอบเป็นเส้นโค้งที่ไม่มีจุดตัด ซึ่งนำจากจุดยอดของภูมิภาคหนึ่ง ข้ามส่วนของขอบเขตร่วมกัน ไปยังจุดยอดของภูมิภาคที่อยู่ติดกัน ในทางกลับกัน กราฟระนาบใดๆ ก็สามารถสร้างขึ้นจากแผนที่ได้ด้วยวิธีนี้ ในศัพท์ทางทฤษฎีกราฟ ทฤษฎีบทสี่สีระบุว่าจุดยอดของกราฟระนาบทุกกราฟสามารถระบายสีได้ด้วยสีอย่างมากที่สุดสี่สี โดยที่ไม่มีจุดยอดที่อยู่ติดกันสองจุดใดได้รับสีเดียวกัน หรือกล่าวโดยย่อคือ กราฟระนาบทุกกราฟสามารถระบายสีได้ด้วยสี่สี[ 5 ]

ประวัติศาสตร์

ความพยายามพิสูจน์เบื้องต้น

จดหมายจากเดอ มอร์แกนถึงวิลเลียม โรวัน แฮมิลตันลงวันที่ 23 ตุลาคม ค.ศ. 1852

เท่าที่ทราบ[ 6 ]ข้อสันนิษฐานนี้ได้รับการเสนอครั้งแรกเมื่อวันที่ 23 ตุลาคม พ.ศ. 2495 [ 7 ]เมื่อฟรานซิส กัทรีขณะพยายามระบายสีแผนที่มณฑลของอังกฤษ สังเกตเห็นว่าจำเป็นต้องใช้สีที่แตกต่างกันเพียงสี่สีเท่านั้น ในขณะนั้นเฟรเดอริก น้องชายของกัทรี เป็นนักศึกษาของออกัสตัส เดอ มอร์แกน (อดีตอาจารย์ที่ปรึกษาของฟรานซิส) ที่มหาวิทยาลัยคอลเลจลอนดอนฟรานซิสสอบถามเฟรเดอริกเกี่ยวกับเรื่องนี้ ซึ่งเฟรเดอริกก็ได้นำไปเสนอต่อเดอ มอร์แกน (ฟรานซิส กัทรี สำเร็จการศึกษาในปลายปี พ.ศ. 2495 และต่อมาได้เป็นศาสตราจารย์ด้านคณิตศาสตร์ในแอฟริกาใต้) ตามคำกล่าวของเดอ มอร์แกน:

นักเรียนคนหนึ่งของฉัน [กัทรี] ถามฉันวันนี้ให้เหตุผลกับข้อเท็จจริงที่ฉันไม่รู้ว่าเป็นข้อเท็จจริง—และยังไม่รู้ เขาบอกว่าถ้าแบ่งรูปทรงออกเป็นส่วนๆ และแต่ละส่วนมีสีต่างกัน โดยที่รูปทรงที่มีเส้น ขอบร่วมกัน จะมีสีต่างกัน—อาจต้องการสี่สี แต่ไม่มากกว่านั้น—ต่อไปนี้คือกรณีของเขาที่ต้องการสี่สีไม่สามารถตั้งคำถามถึงความจำเป็นสำหรับห้าสีหรือมากกว่านั้นได้หรือ... [ 8 ]

"FG" ซึ่งอาจเป็นหนึ่งในสอง Guthries ได้ตีพิมพ์คำถามในThe Athenaeumในปี พ.ศ. 2397 [ 9 ]และ De Morgan ได้ตั้งคำถามอีกครั้งในนิตยสารเดียวกันในปี พ.ศ. 2303 [ 10 ]การอ้างอิงที่ตีพิมพ์ในช่วงต้นอีกฉบับโดยArthur Cayley ( พ.ศ. 2322 )ระบุว่าข้อสันนิษฐานนี้มาจาก De Morgan 

มีการพยายามพิสูจน์ทฤษฎีบทนี้หลายครั้งในช่วงแรกแต่ไม่สำเร็จ เดอ มอร์แกนเชื่อว่าทฤษฎีบทนี้ได้มาจากข้อเท็จจริงง่ายๆ เกี่ยวกับสี่ภูมิภาค แม้ว่าเขาจะไม่เชื่อว่าข้อเท็จจริงนั้นจะสามารถอนุมานได้จากข้อเท็จจริงพื้นฐานมากกว่านั้นก็ตาม

สิ่งนี้เกิดขึ้นในลักษณะดังต่อไปนี้ เราไม่จำเป็นต้องใช้สีสี่สีในละแวกบ้านเว้นแต่จะมีสี่เขต ซึ่งแต่ละเขตมีเส้นเขตแดนร่วมกันกับอีกสามเขตที่เหลือ สิ่งนั้นไม่สามารถเกิดขึ้นได้กับพื้นที่สี่แห่งเว้นแต่หนึ่งหรือมากกว่านั้นจะถูกล้อมรอบด้วยส่วนที่เหลือ และสีที่ใช้สำหรับเขตที่ถูกล้อมรอบจึงถูกปล่อยให้ใช้ต่อไปได้ หลักการนี้ที่ว่าพื้นที่สี่แห่งไม่สามารถมีเส้นเขตแดนร่วมกันกับอีกสามเขตที่เหลือได้หากไม่มีการล้อมรอบนั้น เราเชื่ออย่างเต็มที่ว่าไม่สามารถพิสูจน์ได้ด้วยสิ่งใดที่ชัดเจนและเป็นพื้นฐานกว่านี้ มันจึงต้องถือเป็นสมมติฐาน[ 10 ]

หลักฐานที่เสนอชิ้นหนึ่งถูกนำเสนอโดยAlfred Kempeในปี พ.ศ. 2322 ซึ่งได้รับการยกย่องอย่างกว้างขวาง[ 11 ]อีกชิ้นหนึ่งถูกนำเสนอโดยPeter Guthrie Taitในปี พ.ศ. 2323 จนกระทั่งในปี พ.ศ. 2333 หลักฐานของ Kempe ก็ถูกพิสูจน์ว่าไม่ถูกต้องโดยPercy Heawoodและในปี พ.ศ. 2334 หลักฐานของ Tait ก็ถูกพิสูจน์ว่าไม่ถูกต้องโดยJulius Petersen —หลักฐานที่ผิดพลาดแต่ละชิ้นยังคงอยู่โดยไม่มีใครโต้แย้งเป็นเวลา 11 ปี[ 12 ]

ในปี พ.ศ. 2433 นอกจากการเปิดเผยข้อบกพร่องในการพิสูจน์ของ Kempe แล้ว Heawood ยังพิสูจน์ทฤษฎีบทห้าสีและขยายความคาดการณ์สี่สีไปยังพื้นผิวที่มีจีนัส ใด ๆ อีกด้วย [ 13 ]

ในปี พ.ศ. 2423 Tait ได้แสดงให้เห็นว่าทฤษฎีบทสี่สีเทียบเท่ากับข้อความที่ว่ากราฟประเภทหนึ่ง (เรียกว่าsnarkในศัพท์สมัยใหม่) จะต้องไม่เป็นระนาบ[ 14 ]

ในปี พ.ศ. 2486 Hugo Hadwigerได้กำหนดสมมติฐาน Hadwiger [ 15 ]ซึ่งเป็นการขยายความปัญหา 4 สีในวงกว้างที่ยังคงไม่มีคำตอบ

พิสูจน์โดยคอมพิวเตอร์

ในช่วงทศวรรษ 1960 และ 1970 นักคณิตศาสตร์ชาวเยอรมันHeinrich Heeschได้พัฒนาวิธีการใช้คอมพิวเตอร์เพื่อค้นหาการพิสูจน์ ที่น่าสังเกตคือ เขาเป็นคนแรกที่ใช้การปล่อยประจุเพื่อพิสูจน์ทฤษฎีบท ซึ่งกลายเป็นสิ่งสำคัญในส่วนของความไม่สามารถหลีกเลี่ยงได้ของการพิสูจน์ Appel–Haken ในเวลาต่อมา เขายังได้ขยายแนวคิดเรื่องการลดรูป และร่วมกับ Ken Durre พัฒนาการทดสอบด้วยคอมพิวเตอร์สำหรับแนวคิดนี้ น่าเสียดายที่ในช่วงเวลาสำคัญนี้ เขาไม่สามารถจัดหาเวลาใช้งานซูเปอร์คอมพิวเตอร์ที่จำเป็นเพื่อดำเนินการต่อได้[ 16 ]

คนอื่นๆ นำวิธีการของเขาไปใช้ รวมถึงวิธีการที่ใช้คอมพิวเตอร์ช่วย ในขณะที่ทีมนักคณิตศาสตร์อื่นๆ กำลังเร่งรีบเพื่อพิสูจน์ให้เสร็จสิ้นเคนเนธ แอปเปลและโวล์ฟกัง ฮาเคนที่มหาวิทยาลัยอิลลินอยส์ประกาศเมื่อวันที่ 21 มิถุนายน พ.ศ. 2519 [ 17 ]ว่าพวกเขาได้พิสูจน์ทฤษฎีบทแล้ว พวกเขาได้รับความช่วยเหลือในงานด้านอัลกอริทึมบางส่วนจากจอห์น เอ. โคช[ 18 ]

หากสมมติฐานสี่สีเป็นเท็จ จะต้องมีแผนที่อย่างน้อยหนึ่งแผนที่ที่มีจำนวนภูมิภาคน้อยที่สุดที่ต้องใช้ห้าสี หลักฐานแสดงให้เห็นว่าตัวอย่างค้านขั้นต่ำดังกล่าวไม่สามารถมีอยู่ได้ โดยใช้แนวคิดทางเทคนิคสองประการ: [ 19 ]

  1. เซตที่หลีกเลี่ยงไม่ได้ คือเซตของการจัดเรียงรูปทรงต่างๆ โดยที่แผนที่ทุกแผนที่ซึ่งตรงตามเงื่อนไขที่จำเป็นบางประการสำหรับการเป็น สามเหลี่ยมที่ไม่สามารถระบายสีด้วย 4 สีได้(เช่น มีดีกรีต่ำสุดที่ 5) จะต้องมีการจัดเรียงรูปทรงอย่างน้อยหนึ่งแบบจากเซตนี้
  2. การจัดเรียงแบบลดรูปได้ (Reducible configuration)คือการจัดเรียงประเทศที่ไม่สามารถเกิดขึ้นในตัวอย่างค้านที่เล็กที่สุด (Minimal counterexample) ได้ หากแผนที่ประกอบด้วยการจัดเรียงแบบลดรูปได้ แผนที่นั้นสามารถลดรูปให้เหลือแผนที่ขนาดเล็กกว่าได้ แผนที่ขนาดเล็กนี้มีเงื่อนไขว่า หากสามารถระบายสีด้วยสีสี่สีได้ แผนที่เดิมก็สามารถระบายสีด้วยสีสี่สีได้เช่นกัน ซึ่งหมายความว่า หากแผนที่เดิมไม่สามารถระบายสีด้วยสีสี่สีได้ แผนที่ขนาดเล็กก็ไม่สามารถทำได้เช่นกัน ดังนั้นแผนที่เดิมจึงไม่ใช่ตัวอย่างค้านที่เล็กที่สุด

โดยใช้กฎและขั้นตอนทางคณิตศาสตร์ที่อิงตามคุณสมบัติของการกำหนดค่าที่ลดรูปได้ Appel และ Haken พบชุดของการกำหนดค่าที่ลดรูปได้ที่ไม่สามารถหลีกเลี่ยงได้ จึงพิสูจน์ได้ว่าตัวอย่างค้านขั้นต่ำสำหรับสมมติฐานสี่สีนั้นไม่มีอยู่จริง การพิสูจน์ของพวกเขาลดจำนวนแผนที่ที่เป็นไปได้ที่ไม่มีที่สิ้นสุดลงเหลือ 1,834 การกำหนดค่าที่ลดรูปได้ (ต่อมาลดเหลือ 1,482) ซึ่งต้องตรวจสอบทีละรายการด้วยคอมพิวเตอร์และใช้เวลากว่าพันชั่วโมง ส่วนการลดรูปของงานนี้ได้รับการตรวจสอบซ้ำโดยอิสระด้วยโปรแกรมและคอมพิวเตอร์ที่แตกต่างกัน อย่างไรก็ตาม ส่วนที่ไม่สามารถหลีกเลี่ยงได้ของการพิสูจน์ได้รับการตรวจสอบในไมโครฟิช มากกว่า 400 หน้า ซึ่งต้องตรวจสอบด้วยมือโดยได้รับความช่วยเหลือจากDorothea Blostein ลูกสาวของ Haken [ 20 ]

การประกาศของ Appel และ Haken ได้รับการรายงานอย่างกว้างขวางโดยสื่อข่าวทั่วโลก[ 21 ]และภาควิชาคณิตศาสตร์ที่มหาวิทยาลัยอิลลินอยส์ใช้ตราประทับไปรษณีย์ที่ระบุว่า "สี่สีก็เพียงพอแล้ว" [ 22 ]ในขณะเดียวกัน ลักษณะที่ผิดปกติของการพิสูจน์—ซึ่งเป็นทฤษฎีบทสำคัญแรกที่ได้รับการพิสูจน์ด้วยความช่วยเหลือจากคอมพิวเตอร์อย่างกว้างขวาง—และความซับซ้อนของส่วนที่มนุษย์ตรวจสอบได้ก่อให้เกิดข้อโต้แย้งอย่างมาก[ 23 ]ไม่ใช่ว่านักคณิตศาสตร์ทุกคนจะยอมรับว่าการสาธิตโดยใช้คอมพิวเตอร์สามารถมีคุณสมบัติเป็นการพิสูจน์ที่แท้จริงได้ แม้แต่บางคนที่ยอมรับ เช่นIan Stewartก็พบว่าการพิสูจน์นั้นไม่น่าพอใจ เนื่องจากมันเกิดขึ้นโดยบังเอิญและขาดโครงสร้าง "คำตอบปรากฏออกมาในลักษณะของความบังเอิญที่น่าตกใจ" Stewart เขียนHSM Coxeterพบว่า "ไม่น่าเป็นไปได้มากที่ใครจะสามารถแยกการพิสูจน์นั้นออกเป็นสิ่งที่ถือว่าเป็นการพิสูจน์ธรรมดาได้" [ 24 ]

ในช่วงต้นทศวรรษ 1980 มีข่าวลือแพร่กระจายเกี่ยวกับข้อบกพร่องในบทพิสูจน์ของ Appel – Haken Ulrich Schmidt ที่RWTH Aachenได้ตรวจสอบบทพิสูจน์ของ Appel และ Haken สำหรับวิทยานิพนธ์ปริญญาโทของเขาซึ่งตีพิมพ์ในปี 1981 [ 25 ]เขาได้ตรวจสอบส่วนที่หลีกเลี่ยงไม่ได้ประมาณ 40% และพบข้อผิดพลาดที่สำคัญในขั้นตอนการระบาย( Appel & Haken 1989 )ในปี 1986 บรรณาธิการของMathematical Intelligencer ได้ขอให้ Appel และ Haken เขียนบทความเพื่อชี้แจงข่าวลือเกี่ยวกับข้อบกพร่องในบทพิสูจน์ของพวกเขา พวกเขาตอบว่าข่าวลือเกิดจาก "การตีความผลลัพธ์ของ [Schmidt] ผิดพลาด" และได้เขียนบทความโดยละเอียด[ 25 ] ผล งานชิ้นเอกของพวกเขาEvery Planar Map is Four-Colorableซึ่งเป็นหนังสือที่อ้างว่ามีบทพิสูจน์ที่สมบูรณ์และละเอียด (พร้อมเอกสารเสริมไมโครฟิชมากกว่า 400 หน้า) ปรากฏในปี 1989 อธิบายและแก้ไขข้อผิดพลาดที่ Schmidt ค้นพบ รวมถึงข้อผิดพลาดอื่นๆ อีกหลายข้อที่ผู้อื่นค้นพบ[ 20 ]

การทำให้ง่ายขึ้นและการตรวจสอบ

นับตั้งแต่การพิสูจน์ทฤษฎีบท แนวทางใหม่ได้นำไปสู่ทั้งการพิสูจน์ที่สั้นลงและอัลกอริทึมที่มีประสิทธิภาพมากขึ้นสำหรับแผนที่ 4 สี ในปี 1996 Neil Robertson , Daniel P. Sanders , Paul SeymourและRobin Thomasได้สร้าง อัลกอริทึม เวลาควาดราติก (ต้องการเวลา เพียง O ( n² ) โดยที่ nคือจำนวนจุดยอด) ซึ่งปรับปรุงจากอัลกอริ ทึมเวลา ควาดราติกที่อิงจากการพิสูจน์ของ Appel และ Haken [ 26 ]การพิสูจน์ใหม่นี้ซึ่งอิงตามแนวคิดเดียวกัน คล้ายกับของ Appel และ Haken แต่มีประสิทธิภาพมากกว่าเนื่องจากลดความซับซ้อนของปัญหาและต้องตรวจสอบการกำหนดค่าที่ลดรูปได้เพียง 633 รายการเท่านั้น ทั้งส่วนที่หลีกเลี่ยงไม่ได้และส่วนที่ลดรูปได้ของการพิสูจน์ใหม่นี้จะต้องดำเนินการโดยคอมพิวเตอร์และไม่สามารถตรวจสอบด้วยมือได้ในทางปฏิบัติ[ 27 ]ในปี 2001 ผู้เขียนกลุ่มเดียวกันได้ประกาศการพิสูจน์ทางเลือกโดยการพิสูจน์ ข้อ สันนิษฐานsnark [ 28 ]อย่างไรก็ตาม หลักฐานนี้ยังไม่ได้รับการเผยแพร่

ในปี พ.ศ. 2548 เบนจามิน เวอร์เนอร์และจอร์จส์ กอนเทียร์ได้จัดทำบทพิสูจน์ทฤษฎีบทอย่างเป็นทางการภายในตัว ช่วยพิสูจน์ Coqซึ่งทำให้ไม่จำเป็นต้องเชื่อถือโปรแกรมคอมพิวเตอร์ต่างๆ ที่ใช้ในการตรวจสอบกรณีเฉพาะอีกต่อไป จำเป็นต้องเชื่อถือเฉพาะเคอร์เนลของ Coq เท่านั้น[ 29 ]

สรุปแนวคิดการพิสูจน์

ต่อไปนี้เป็นการสรุปจากบทนำของบทความเรื่องEvery Planar Map is Four Colorable ( Appel & Haken 1989 )แม้ว่าจะมีข้อบกพร่องอยู่บ้าง แต่บทพิสูจน์ดั้งเดิมของทฤษฎีบทสี่สีที่ Kempe เสนอมานั้นได้ให้เครื่องมือพื้นฐานบางอย่างที่ใช้ในการพิสูจน์ทฤษฎีบทนี้ในภายหลัง คำอธิบายในที่นี้ได้เรียบเรียงใหม่โดยใช้สูตรทฤษฎีกราฟสมัยใหม่ดังที่กล่าวมาข้างต้น

ข้อโต้แย้งของ Kempe มีดังนี้ ขั้นแรก หากบริเวณระนาบที่แยกออกจากกันด้วยกราฟไม่ได้เป็นรูปสามเหลี่ยม (กล่าวคือ ไม่มีขอบสามเส้นที่ขอบเขตของมัน) เราสามารถเพิ่มขอบได้โดยไม่ต้องสร้างจุดยอดใหม่ เพื่อทำให้ทุกบริเวณเป็นรูปสามเหลี่ยม รวมถึงบริเวณภายนอกที่ไม่มีขอบเขตด้วย หากกราฟที่เป็นรูปสามเหลี่ยม นี้ สามารถระบายสีได้โดยใช้สีสี่สีหรือน้อยกว่า กราฟเดิมก็สามารถระบายสีได้เช่นกัน เนื่องจากวิธีการระบายสีแบบเดียวกันยังคงใช้ได้แม้ว่าจะมีการลบขอบออกไป ดังนั้น การพิสูจน์ทฤษฎีบทสี่สีสำหรับกราฟที่เป็นรูปสามเหลี่ยมจึงเพียงพอที่จะพิสูจน์ทฤษฎีบทนี้สำหรับกราฟระนาบทั้งหมด และโดยไม่เสียความเป็นทั่วไป เราจะถือว่ากราฟนั้นเป็นรูปสามเหลี่ยม

สมมติว่าv , eและfคือจำนวนจุดยอด ขอบ และบริเวณ (หน้า) ตามลำดับ เนื่องจากแต่ละบริเวณเป็นรูปสามเหลี่ยมและแต่ละขอบใช้ร่วมกันโดยสองบริเวณ เราจึงได้ว่า 2e = 3f ซึ่งเมื่อรวมกับสูตรของออยเลอร์ v − e + f = 2 จะสามารถแสดงได้ว่า 6v − 2e = 12 ทีนี้ดีกรีของจุดยอดคือจำนวนขอบที่ติดกับจุดยอดนั้น ถ้าvn คือจำนวนจุดยอดที่มีดีกรีnและDคือดีกรีสูงสุดของจุดยอดใด

6วี−2อี=6∑ฉัน=1ดีวีฉัน−∑ฉัน=1ดีฉันวีฉัน=∑ฉัน=1ดี(6−ฉัน)วีฉัน=12.{\displaystyle 6v-2e=6\sum _{i=1}^{D}v_{i}-\sum _{i=1}^{D}iv_{i}=\sum _{i=1}^{D}(6-i)v_{i}=12.}

แต่เนื่องจาก 12 > 0 และ 6 − i ≤ 0 สำหรับทุกi ≥ 6 จึงแสดงให้เห็นว่ามีจุดยอดอย่างน้อยหนึ่งจุดที่มีดีกรี 5 หรือน้อยกว่า

ถ้ามีกราฟที่ต้องการสี 5 สี ก็จะมี กราฟ ที่เล็กที่สุดที่ต้องการสีนั้น โดยที่การลบจุดยอดใดๆ ออกไปจะทำให้กราฟนั้นสามารถระบายสีได้ด้วย 4 สี เรียกกราฟนี้ว่าGแล้วGจะต้องไม่มีจุดยอดที่มีดีกรี 3 หรือน้อยกว่า เพราะถ้าd ( v ) ≤ 3 เราสามารถลบv ออก จากGระบายสีกราฟที่เล็กลงด้วย 4 สี จากนั้นเพิ่มv กลับเข้าไป และขยายการระบายสีด้วย 4 สีไปยังกราฟนั้นโดยเลือกสีที่แตกต่างจากจุดยอดข้างเคียง

กราฟที่ประกอบด้วยสายโซ่ Kempe ซึ่งประกอบด้วยจุดยอดสีน้ำเงินและสีแดงสลับกัน

Kempe ยังแสดงให้เห็นอย่างถูกต้องว่าGไม่สามารถมีจุดยอดที่มีดีกรี 4 ได้ เช่นเดียวกับก่อนหน้านี้ เราลบจุดยอดv ออก และระบายสีจุดยอดที่เหลือด้วยสีสี่สี ถ้าจุดยอดข้างเคียงทั้งสี่ของvมีสีต่างกัน เช่น สีแดง สีเขียว สีน้ำเงิน และสีเหลือง เรียงตามเข็มนาฬิกา เราจะมองหาเส้นทางสลับสีของจุดยอดที่ระบายสีแดงและสีน้ำเงินเชื่อมต่อจุดยอดข้างเคียงสีแดงและสีน้ำเงิน เส้นทางดังกล่าวเรียกว่าโซ่ Kempeอาจมีโซ่ Kempe ที่เชื่อมต่อจุดยอดข้างเคียงสีแดงและสีน้ำเงิน และอาจมีโซ่ Kempe ที่เชื่อมต่อจุดยอดข้างเคียงสีเขียวและสีเหลือง แต่จะไม่มีทั้งสองอย่างพร้อมกัน เนื่องจากเส้นทางทั้งสองนี้จะต้องตัดกัน และจุดยอดที่ตัดกันนั้นไม่สามารถระบายสีได้ สมมติว่าเป็นจุดยอดข้างเคียงสีแดงและสีน้ำเงินที่ไม่ได้เชื่อมต่อกันเป็นโซ่ สำรวจจุดยอดทั้งหมดที่เชื่อมต่อกับจุดยอดข้างเคียงสีแดงด้วยเส้นทางสลับสีแดง-น้ำเงิน จากนั้นสลับสีแดงและสีน้ำเงินบนจุดยอดทั้งหมดเหล่านี้ ผลลัพธ์ยังคงเป็นการระบายสีสี่สีที่ถูกต้อง และตอนนี้สามารถเพิ่มv กลับเข้าไปและระบายสีแดงได้

เหลือเพียงกรณีที่Gมีจุดยอดที่มีดีกรี 5 เท่านั้น แต่ข้อโต้แย้งของ Kempe มีข้อบกพร่องในกรณีนี้ Heawood สังเกตเห็นข้อผิดพลาดของ Kempe และยังสังเกตอีกว่า หากพอใจกับการพิสูจน์ว่าต้องการเพียงห้าสี ก็สามารถใช้ข้อโต้แย้งข้างต้น (โดยเปลี่ยนเพียงว่าตัวอย่างค้านขั้นต่ำต้องการ 6 สี) และใช้ลูกโซ่ของ Kempe ในสถานการณ์ดีกรี 5 เพื่อพิสูจน์ทฤษฎีบทห้าสีได้

ไม่ว่าในกรณีใด การจัดการกับกรณีของจุดยอดที่มีดีกรี 5 นั้น จำเป็นต้องใช้แนวคิดที่ซับซ้อนกว่าการลบจุดยอดออกไป แต่รูปแบบของข้อโต้แย้งจะถูกขยายไปสู่การพิจารณาโครงสร้างซึ่งเป็นกราฟย่อยที่เชื่อมต่อกันของGโดยระบุดีกรีของแต่ละจุดยอด (ใน G) ตัวอย่างเช่น กรณีที่อธิบายไว้ในสถานการณ์จุดยอดที่มีดีกรี 4 คือโครงสร้างที่ประกอบด้วยจุดยอดเดียวที่มีดีกรี 4 ในGดังที่กล่าวมาข้างต้น เพียงพอที่จะแสดงให้เห็นว่า หากลบโครงสร้างออกและระบายสีกราฟที่เหลือด้วยสี่สีแล้ว การระบายสีสามารถปรับเปลี่ยนได้ในลักษณะที่ว่า เมื่อเพิ่มโครงสร้างกลับเข้าไปใหม่ การระบายสีด้วยสี่สีก็สามารถขยายไปยังโครงสร้างนั้นได้เช่นกัน โครงสร้างที่ทำเช่นนี้ได้เรียกว่าโครงสร้างที่ลดรูปได้หากอย่างน้อยหนึ่งในชุดของโครงสร้างต้องเกิดขึ้นที่ใดที่หนึ่งใน G ชุดนั้นเรียกว่า โครงสร้างที่หลีกเลี่ยงไม่ได้ ข้อโต้แย้งข้างต้นเริ่มต้นด้วยการยกตัวอย่างชุดการจัดเรียงที่ไม่สามารถหลีกเลี่ยงได้ 5 แบบ (จุดยอดเดี่ยวที่มีดีกรี 1, จุดยอดเดี่ยวที่มีดีกรี 2, ..., จุดยอดเดี่ยวที่มีดีกรี 5) จากนั้นจึงแสดงให้เห็นว่า 4 แบบแรกสามารถลดรูปได้ การแสดงให้เห็นชุดการจัดเรียงที่ไม่สามารถหลีกเลี่ยงได้ซึ่งทุกการจัดเรียงในชุดนั้นสามารถลดรูปได้ จะเป็นการพิสูจน์ทฤษฎีบท

เนื่องจากGเป็นกราฟสามเหลี่ยม จึงทราบดีกรีของแต่ละจุดยอดในโครงสร้าง และทราบขอบทั้งหมดภายในโครงสร้าง จำนวนจุดยอดในGที่อยู่ติดกับโครงสร้างที่กำหนดจึงคงที่ และจุดยอดเหล่านั้นจะเชื่อมต่อกันเป็นวงจร จุดยอดเหล่านี้ก่อตัวเป็นวงแหวนของโครงสร้าง โครงสร้างที่มีkจุดยอดในวงแหวนเรียกว่า โครงสร้าง k-วงแหวน และโครงสร้างพร้อมกับวงแหวนเรียกว่าโครงสร้างวงแหวน เช่นเดียวกับ ในกรณีง่ายๆ ข้างต้น เราสามารถแจงนับการระบายสีสี่สีที่แตกต่างกันทั้งหมดของวงแหวนได้ การระบายสีใดๆ ที่สามารถขยายได้โดยไม่ต้องแก้ไขการระบายสีของโครงสร้างเรียกว่าดีในเบื้องต้นตัวอย่างเช่น โครงสร้างจุดยอดเดียวข้างต้นที่มีเพื่อนบ้าน 3 จุดหรือน้อยกว่านั้นดีในเบื้องต้น โดยทั่วไปแล้ว กราฟโดยรอบจะต้องถูกระบายสีใหม่อย่างเป็นระบบเพื่อให้การระบายสีของวงแหวนดีขึ้น ดังที่ทำในกรณีข้างต้นที่มีเพื่อนบ้าน 4 จุด สำหรับโครงสร้างทั่วไปที่มีวงแหวนขนาดใหญ่กว่านั้น ต้องใช้เทคนิคที่ซับซ้อนกว่า เนื่องจากแหวนมีสีสี่สีที่แตกต่างกันจำนวนมาก ขั้นตอนนี้จึงเป็นขั้นตอนหลักที่ต้องอาศัยความช่วยเหลือจากคอมพิวเตอร์

สุดท้ายแล้ว ยังคงต้องระบุชุดการกำหนดค่าที่หลีกเลี่ยงไม่ได้ซึ่งสามารถลดทอนได้ด้วยกระบวนการนี้ วิธีหลักที่ใช้ในการค้นหาชุดดังกล่าวคือวิธีการคายประจุแนวคิดพื้นฐานที่อยู่เบื้องหลังการคายประจุคือการพิจารณากราฟระนาบเป็นเครือข่ายไฟฟ้า ในขั้นต้น "ประจุไฟฟ้า" บวกและลบจะกระจายอยู่ระหว่างจุดยอดต่างๆ เพื่อให้ผลรวมเป็นบวก

โปรดจำสูตรข้างต้น:

∑ฉัน=1ดี(6−ฉัน)วีฉัน=12.{\displaystyle \sum _{i=1}^{D}(6-i)v_{i}=12.}

แต่ละจุดยอดที่มีดีกรีฉัน{\displaystyle i}ได้รับการกำหนดค่าธรรมเนียมเริ่มต้นที่6−ฉัน{\displaystyle 6-i}จากนั้นจึง "ปล่อย" ประจุโดยการกระจายประจุจากจุดยอดหนึ่งไปยังจุดยอดข้างเคียงอย่างเป็นระบบตามชุดของกฎ ซึ่งเป็นขั้นตอนการคายประจุเนื่องจากประจุรวมเริ่มต้นเป็นบวก (12) และประจุยังคงอยู่ จุดยอดบางจุดจึงยังคงมีประจุบวก กฎจะจำกัดความเป็นไปได้ของการกำหนดค่าของจุดยอดที่มีประจุบวก ดังนั้นการแจงนับการกำหนดค่าที่เป็นไปได้ทั้งหมดดังกล่าวจึงได้เซตที่ไม่สามารถหลีกเลี่ยงได้

ตราบใดที่สมาชิกบางส่วนในชุดที่ไม่สามารถหลีกเลี่ยงได้นั้นไม่สามารถลดทอนได้ ขั้นตอนการปลดปล่อยก็จะถูกปรับเปลี่ยนเพื่อกำจัดสมาชิกนั้น (พร้อมกับการนำเสนอโครงสร้างอื่นๆ) ขั้นตอนการปลดปล่อยขั้นสุดท้ายของ Appel และ Haken นั้นซับซ้อนอย่างยิ่ง และเมื่อรวมกับคำอธิบายของชุดโครงสร้างที่ไม่สามารถหลีกเลี่ยงได้ที่เกิดขึ้นแล้ว ก็ได้บรรจุอยู่ในหนังสือขนาด 400 หน้า แต่โครงสร้างที่สร้างขึ้นนั้นสามารถตรวจสอบได้ด้วยกลไกว่าสามารถลดทอนได้ การตรวจสอบความถูกต้องของหนังสือที่อธิบายชุดโครงสร้างที่ไม่สามารถหลีกเลี่ยงได้นั้น ดำเนินการโดยการตรวจสอบโดยผู้เชี่ยวชาญในระยะเวลาหลายปี

รายละเอียดทางเทคนิคที่ไม่ได้กล่าวถึงในที่นี้ แต่จำเป็นต่อการพิสูจน์ให้เสร็จสมบูรณ์ คือ การลดรูป โดยการจุ่ม (immersion reducibility )

การหักล้างที่ผิดพลาด

ทฤษฎีบทสี่สีเป็นที่รู้จักกันดีในเรื่องการดึงดูดการพิสูจน์ที่ผิดพลาดและการพิสูจน์หักล้างจำนวนมากในประวัติศาสตร์อันยาวนาน ในตอนแรกThe New York Timesปฏิเสธที่จะรายงานเกี่ยวกับการพิสูจน์ของ Appel–Haken ตามนโยบาย โดยเกรงว่าการพิสูจน์จะถูกเปิดเผยว่าเป็นเท็จเหมือนกับการพิสูจน์ก่อนหน้านี้[ 21 ]การพิสูจน์ที่อ้างว่าถูกต้องบางรายการ เช่น การพิสูจน์ของ Kempe และ Tait ที่กล่าวถึงข้างต้น อยู่ภายใต้การตรวจสอบของสาธารณชนมานานกว่าทศวรรษก่อนที่จะถูกหักล้าง แต่การพิสูจน์อีกมากมายที่เขียนโดยมือสมัครเล่นไม่เคยได้รับการตีพิมพ์

ในแผนที่แรกซึ่งมีสีมากกว่าสี่สี การแทนที่บริเวณสีแดงด้วยสีอื่นอีกสี่สีจะไม่ประสบผลสำเร็จ และตัวอย่างนี้อาจดูเหมือนขัดแย้งกับทฤษฎีบทในตอนแรก อย่างไรก็ตาม สามารถจัดเรียงสีใหม่ได้ ดังเช่นในแผนที่ที่สอง

โดยทั่วไป ตัวอย่างค้านที่ง่ายที่สุด แต่ไม่ถูกต้อง พยายามสร้างพื้นที่หนึ่งที่สัมผัสกับพื้นที่อื่นๆ ทั้งหมด ซึ่งจะบังคับให้พื้นที่ที่เหลือถูกระบายสีด้วยสีเพียงสามสีเท่านั้น เนื่องจากทฤษฎีบทสี่สีเป็นจริง สิ่งนี้จึงเป็นไปได้เสมอ อย่างไรก็ตาม เนื่องจากผู้ที่วาดแผนที่มุ่งเน้นไปที่พื้นที่ขนาดใหญ่เพียงแห่งเดียว พวกเขาจึงมองข้ามไปว่าพื้นที่ที่เหลือสามารถระบายสีด้วยสีสามสีได้เช่นกัน

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

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

การพิสูจน์หักล้างที่ผิดพลาดอื่นๆ ขัดแย้งกับข้อสมมติของทฤษฎีบท เช่น การใช้บริเวณที่ประกอบด้วยส่วนที่ไม่เชื่อมต่อกันหลายส่วน หรือการไม่อนุญาตให้บริเวณที่มีสีเดียวกันสัมผัสกัน ณ จุดใดจุดหนึ่ง

สามสี

พิสูจน์ได้โดยไม่ต้องใช้คำพูดว่า แผนที่แสดงรัฐต่างๆ ของสหรัฐอเมริกาควรใช้สีอย่างน้อยสี่สี

แม้ว่าแผนที่ระนาบทุกแผนที่สามารถระบายสีด้วยสีสี่สีได้ แต่การตัดสินใจว่าแผนที่ระนาบใดๆ สามารถระบายสีด้วยสีเพียงสามสีได้หรือไม่นั้นมีความซับซ้อนระดับ NP -complete [ 30 ]

แผนที่ทรงลูกบาศก์สามารถระบายสีได้ด้วยสีเพียงสามสีก็ต่อเมื่อแต่ละพื้นที่ภายในมีจำนวนพื้นที่ข้างเคียงเป็นเลขคู่เท่านั้น[ 31 ]ในตัวอย่างแผนที่รัฐของสหรัฐอเมริการัฐมิสซูรี (MO) ซึ่งไม่มีทางออกสู่ทะเลมีเพื่อนบ้านแปดแห่ง (เลขคู่): ต้องมีสีที่แตกต่างจากเพื่อนบ้านทั้งหมด แต่เพื่อนบ้านสามารถสลับสีกันได้ ดังนั้นส่วนนี้ของแผนที่จึงต้องการเพียงสามสี อย่างไรก็ตามรัฐเนวาดา (NV) ซึ่งไม่มีทางออกสู่ทะเลมีเพื่อนบ้านห้าแห่ง (เลขคี่): เพื่อนบ้านเหล่านี้ต้องการสามสี และต้องมีสีที่แตกต่างจากเพื่อนบ้าน ดังนั้นจึงต้องใช้สี่สีในส่วนนี้

การสรุปโดยทั่วไป

กราฟอนันต์

โดยการเชื่อมลูกศรเดี่ยวเข้าด้วยกันและเชื่อมลูกศรคู่เข้าด้วยกัน จะได้ทรงโดนัทที่มีเจ็ดส่วนที่สัมผัสกัน ดังนั้นจึงต้องใช้เจ็ดสี
โครงสร้างนี้แสดงให้เห็นว่าทรงโดนัทถูกแบ่งออกเป็นเจ็ดส่วนมากที่สุด โดยแต่ละส่วนจะสัมผัสกันทั้งหมด

ทฤษฎีบทสี่สีไม่เพียงแต่ใช้ได้กับกราฟระนาบจำกัดเท่านั้น แต่ยังใช้ได้กับกราฟอนันต์ที่สามารถวาดได้โดยไม่มีจุดตัดในระนาบ และโดยทั่วไปแล้วยังใช้ได้กับกราฟอนันต์ (อาจมีจำนวนจุดยอดนับไม่ถ้วน) ซึ่งกราฟย่อยจำกัดทุกกราฟเป็นกราฟระนาบ ในการพิสูจน์สิ่งนี้ เราสามารถรวมการพิสูจน์ทฤษฎีบทสำหรับกราฟระนาบจำกัดเข้ากับทฤษฎีบทของเดอ บรูอิน-เออร์โดสที่ระบุว่า ถ้ากราฟย่อยจำกัดทุกกราฟของกราฟอนันต์สามารถ ระบายสีได้ด้วย kสี แล้วกราฟทั้งหมดก็สามารถระบายสีได้ ด้วย k สีเช่นกัน ( แนช-วิลเลียมส์ 1967 )สิ่งนี้ยังสามารถมองได้ว่าเป็นผลลัพธ์โดยตรงจากทฤษฎีบทความกะทัดรัดของเคิร์ท เกอเดลสำหรับตรรกศาสตร์อันดับหนึ่งโดยการแสดงความสามารถในการระบายสีของกราฟอนันต์ด้วยชุดของสูตรทางตรรกศาสตร์

พื้นผิวที่สูงกว่า

นอกจากนี้ยังสามารถพิจารณาปัญหาการระบายสีบนพื้นผิวอื่นที่ไม่ใช่ระนาบได้อีกด้วย[ 32 ]ปัญหาบนทรงกลมหรือทรงกระบอกเทียบเท่ากับปัญหาบนระนาบ สำหรับพื้นผิวปิด (ที่สามารถกำหนดทิศทางได้หรือไม่สามารถกำหนดทิศทางได้) ที่มีจีนัส เป็นบวก จำนวน สีสูงสุดp ที่ต้องการจะขึ้นอยู่กับ ลักษณะเฉพาะของออยเลอร์χของพื้นผิว ยกเว้นขวดไคลน์ สูตรจะเป็นดังนี้: พี=⌊7+49−24χ2⌋,{\displaystyle p=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor ,} โดยวงเล็บนอกสุดหมายถึงฟังก์ชันพื้น (floor function )

สำหรับ พื้นผิว ที่สามารถกำหนดทิศทางได้นั่นหมายความว่าpสามารถระบุได้ในรูปของจีนัสgของพื้นผิว: พี=⌊7+1+48จี2⌋.{\displaystyle p=\left\lfloor {\frac {7+{\sqrt {1+48g}}}{2}}\right\rfloor .}

สูตรสูงสุด หรือ สมมติฐานของ ฮีวูด (Heawood conjecture ) ถูกเสนอโดยพี.เจ. ฮีวูดในปี 1890 และหลังจากได้รับการสนับสนุนจากหลายๆ คน ก็ได้รับการพิสูจน์โดยเกอร์ฮาร์ด ริงเกลและเจ.ดับบลิว.ที. ยังส์ในปี 1968 ข้อยกเว้นเพียงอย่างเดียวของสูตรนี้คือขวดไคลน์ (Klein bottle ) ซึ่งมีลักษณะเฉพาะของออยเลอร์χ = 0 (ดังนั้นสูตรจึงให้ค่าp = 7 ) แต่ต้องการเพียงหกสีเท่านั้น ดังที่ฟิลิป แฟรงคลิน ได้แสดงให้เห็น ในปี 1934

ตัวอย่างเช่นทอรัสมีลักษณะเฉพาะของออยเลอร์χ = 0 (และจีนัสg = 1 ) ดังนั้นp = 7จึงไม่จำเป็นต้องใช้สีมากกว่าเจ็ดสีในการระบายสีแผนที่ใดๆ บนทอรัส ขีดจำกัดบนที่7 นี้ เป็นค่าที่แม่นยำ : รูปทรงหลายเหลี่ยมทอรัส บางชนิด เช่นรูปทรงหลายเหลี่ยมซิลาสซีจำเป็นต้องใช้สีเจ็ดสี

แถบโมเบียสต้องใช้สีหกสี( Tietze 1910 )เช่นเดียวกับกราฟระนาบ 1 มิติ (กราฟที่วาดโดยมีจุดตัดอย่างง่ายไม่เกินหนึ่งจุดต่อขอบ) ( Borodin 1984 ) หากทั้งจุดยอดและหน้าของกราฟระนาบถูกระบายสีในลักษณะที่ไม่มีจุดยอด หน้า หรือคู่จุดยอด-หน้าสองคู่ที่อยู่ติดกันมีสีเดียวกัน ก็จะใช้สีไม่เกินหกสีเช่นกัน( Borodin 1984 )

ระนาบเชิงฉายจริงมีลักษณะเฉพาะของออยเลอร์χ = 1และสูตรให้ค่าp = 6ดังนั้นจึงไม่จำเป็นต้องใช้สีมากกว่าหกสี

สำหรับกราฟที่มีจุดยอดแทนด้วยคู่ของจุดบนพื้นผิวที่แตกต่างกันสองพื้นผิว โดยมีขอบวาดเป็นเส้นโค้งที่ไม่ตัดกันบนพื้นผิวใดพื้นผิวหนึ่งในสองพื้นผิวนั้น จำนวนสีสามารถมีค่าอย่างน้อย9และอย่างมาก12แต่ยังไม่ทราบขอบเขตที่แม่นยำกว่านี้ นี่คือปัญหาโลก-ดวงจันทร์ของGerhard Ringel [ 33 ]

บริเวณที่เป็นของแข็ง

พิสูจน์โดยไม่ต้องใช้คำพูดว่าจำนวนสีที่ต้องการนั้นไม่มีขีดจำกัดในสามมิติหรือมากกว่านั้น

ไม่มีการขยายผลลัพธ์การระบายสีที่ชัดเจนไปยังบริเวณของแข็งสามมิติ โดยการใช้แท่งพับจำนวนnแท่ง เราสามารถจัดเรียงให้แท่งทุกแท่งสัมผัสกับแท่งอื่น ๆ ได้ ชุดดังกล่าวจะต้องใช้ สี nสี หรือn + 1 สีหากรวมพื้นที่ว่าง (ซึ่งสัมผัสกับแท่งทุกแท่งเช่นกัน) จำนวนnสามารถกำหนดให้เป็นจำนวนเต็มใดก็ได้ มากเท่าที่ต้องการ ตัวอย่างเช่นนี้เป็นที่รู้จักของ Frederick Guthrie ในปี 1880 [ 34 ]แม้แต่สำหรับทรงสี่เหลี่ยมลูกบาศก์ ที่ขนานกับแกน (ทรงสี่เหลี่ยมลูกบาศก์สองอันถือว่าอยู่ติดกันหากมีพื้นผิวขอบเขตสองมิติร่วมกัน) ก็อาจจำเป็นต้องใช้สีจำนวนไม่จำกัด[ 35 ]

ความสัมพันธ์กับสาขาอื่นๆ ของคณิตศาสตร์

Dror Bar-Natanได้ให้คำแถลงเกี่ยวกับพีชคณิต Lieและตัวแปร Vassilievซึ่งเทียบเท่ากับทฤษฎีบทสี่สี[ 36 ]

นำไปใช้ในบริบทอื่นนอกเหนือจากคณิตศาสตร์

เกาะแซงต์มาร์ติน ซึ่งตั้งอยู่ทางตะวันออกเฉียงเหนือ ของทะเลแคริบเบียนถูกแบ่งออกเป็นสองส่วนระหว่างฝรั่งเศสและเนเธอร์แลนด์

แม้ว่าแรงจูงใจมาจากการระบายสีแผนที่การเมืองของประเทศต่างๆแต่ทฤษฎีบทนี้ก็ไม่ได้น่าสนใจเป็นพิเศษสำหรับนักทำแผนที่ตามบทความของนักประวัติศาสตร์คณิตศาสตร์Kenneth Mayกล่าวว่า "แผนที่ที่ใช้เพียงสี่สีนั้นหายาก และแผนที่ที่ใช้สี่สีมักจะใช้เพียงสามสีเท่านั้น หนังสือเกี่ยวกับการทำแผนที่และประวัติศาสตร์การทำแผนที่ไม่ได้กล่าวถึงคุณสมบัติสี่สี" [ 37 ]ทฤษฎีบทนี้ยังไม่รับประกันข้อกำหนดทางแผนที่ทั่วไปที่ว่าภูมิภาคที่ไม่ต่อเนื่องกันของประเทศเดียวกัน (เช่น ดินแดนส่วนแยกอะแลสกาและส่วนที่เหลือของสหรัฐอเมริกา ) จะต้องมีสีเหมือนกัน[ 38 ]เนื่องจากทฤษฎีบทสี่สีใช้ไม่ได้เมื่อภูมิภาคบนแผนที่ไม่ต่อเนื่องกัน จึงใช้ไม่ได้กับแผนที่โลกเช่นกัน บนแผนที่โลก มหาสมุทร เบลเยียม เยอรมนี เนเธอร์แลนด์ และฝรั่งเศส ล้วนมีพรมแดนติดกัน เนื่องจากเนเธอร์แลนด์มีพรมแดนติดกับฝรั่งเศสบนเกาะแซงต์มาร์ติน

ทฤษฎีบทนี้ใช้ไม่ได้ผลเช่นกัน หากกำหนดให้แหล่งน้ำทั้งหมดมีสีเดียวกัน ซึ่งไม่สามารถใช้สำหรับประเทศได้ (เช่น สีน้ำเงิน) ในกรณีนั้น แผนที่ของยุโรปเองก็ไม่สามารถระบายสีได้สี่สี ฝรั่งเศส เยอรมนี และเบลเยียมต้องกำหนดสีที่แตกต่างกันสามสี เนื่องจากประเทศเหล่านี้มีพรมแดนติดกัน จึงต้องใช้สีทั้งหมดสี่สี ฝรั่งเศสและเนเธอร์แลนด์สามารถกำหนดสีเดียวกันได้ แต่ลักเซมเบิร์กต้องใช้สีที่ห้า[ 39 ]

ดูเพิ่มเติม

หมายเหตุ

  1. ↑จาก Gonthier (2008) : "คำจำกัดความ: แผนที่ระนาบคือเซตของเซตย่อยที่ไม่ทับซ้อนกันเป็นคู่ๆ บนระนาบ เรียกว่า บริเวณ แผนที่เชิงเดี่ยวคือแผนที่ที่มีบริเวณเป็นเซตเปิดที่เชื่อมต่อกัน บริเวณสองบริเวณของแผนที่อยู่ติดกัน ถ้าส่วนปิดของบริเวณทั้งสองมีจุดร่วมกันที่ไม่ใช่จุดมุมของแผนที่ จุดจะเป็นจุดมุมของแผนที่ก็ต่อเมื่อจุดนั้นอยู่ในส่วนปิดของอย่างน้อยสามบริเวณ ทฤษฎีบท: บริเวณของแผนที่ระนาบเชิงเดี่ยวใดๆ สามารถระบายสีได้ด้วยสีเพียงสี่สี โดยที่บริเวณที่อยู่ติดกันสองบริเวณใดๆ จะมีสีต่างกัน"
  2. ↑สวาร์ต (1980 )
  3. ↑วิลสัน (2014) , 216–222.
  4. ↑ฮัดสัน (2003 )
  5. ↑โทมัส (1998 , หน้า849) ;วิลสัน (2014) ) 
  6. ↑มีความเชื่อทางคณิตศาสตร์บางอย่างที่กล่าวว่าโมเบียสเป็นผู้คิดค้นทฤษฎีบทสี่สี แต่ดูเหมือนว่าความคิดนี้จะผิดพลาด ดู Biggs, Norman ; Lloyd, E. Keith; Wilson, Robin J. (1986), Graph Theory, 1736–1936 , Oxford University Press, หน้า 116 , ISBN 0-19-853916-9& Maddison, Isabel (1897), "หมายเหตุเกี่ยวกับประวัติของปัญหาการระบายสีแผนที่", Bull. Amer. Math. Soc. , 3 (7): 257, doi : 10.1090/S0002-9904-1897-00421-9
  7. ↑ Donald MacKenzie, Mechanizing Proof: Computing, Risk, and Trust (MIT Press, 2004) หน้า 103
  8. ↑วิลสัน (2014)หน้า 12
  9. ↑ FG (1854) ; McKay (2012)
  10. 1 2 เดอ มอร์แกน (ไม่ระบุชื่อผู้เขียน) ออกัสตัส (14 เมษายน 1860) "ปรัชญาแห่งการค้นพบ บทประวัติศาสตร์และวิจารณ์ โดย ดับเบิลยู. เวเวลล์" ดิ เอเธเนียม : 501– 503
  11. ↑ WW Rouse Ball (1960)ทฤษฎีบทสี่สีใน Mathematical Recreations and Essays, Macmillan, New York, หน้า 222–232
  12. ↑โทมัส (1998)หน้า 848
  13. ↑ฮีวูด (1890 )
  14. ↑เทต (1880 )
  15. ↑ Hadwiger (1943)
  16. ↑วิลสัน (2014)หน้า 139–142
  17. ↑ Gary Chartrand และ Linda Lesniak, Graphs & Digraphs (CRC Press, 2005) หน้า. 221
  18. ↑วิลสัน (2014)หน้า 145–146
  19. ↑วิลสัน (2014 , หน้า105–107) ;แอปเปลแอนด์ฮาเกน (1989) ;โธมัส (1998 , หน้า852–853)  
  20. 1 2 Appel & Haken (1989) .
  21. 1 2วิลสัน (2014)หน้า 153
  22. ↑วิลสัน (2014)หน้า 150
  23. ↑วิลสัน (2014)หน้า 157
  24. ↑วิลสัน (2014)หน้า 161–162
  25. 1 2วิลสัน (2014)หน้า 165
  26. ↑โทมัส (1995) ;โรเบิร์ตสันและคณะ (1996 )
  27. ↑โทมัส (1998)หน้า 852–853
  28. ↑โทมัส (1999) ;เพ็กก์และคณะ (2002) .
  29. ↑ กอนเทีย ร์ (2008)
  30. ↑ Dailey, DP (1980), "ความเป็นเอกลักษณ์ของความสามารถในการระบายสีและความสามารถในการระบายสีของกราฟระนาบ 4-ปกติเป็น NP-สมบูรณ์", Discrete Mathematics , 30 (3): 289– 293, doi : 10.1016/0012-365X(80)90236-8
  31. ↑ Steinberg, Richard (1993), "สถานะของปัญหาสามสี", ใน Gimbel, John; Kennedy, John W.; Quintas, Louis V. (บรรณาธิการ), Quo Vadis, Graph Theory? , Annals of Discrete Mathematics, เล่มที่55, อัมสเตอร์ดัม: North-Holland, หน้า211–248 , doi : 10.1016/S0167-5060(08)70391-1 , ISBN   978-0-444-89441-0, MR 1217995 
  32. ↑ ริงเก ล (1974)
  33. ↑ Gethner, Ellen (2018), "To the Moon and beyond", ในGera, Ralucca ; Haynes, Teresa W. ; Hedetniemi, Stephen T. (บรรณาธิการ), ทฤษฎีกราฟ: ข้อสันนิษฐานที่ชื่นชอบและปัญหาที่ยังเปิดอยู่, เล่ม 2 , หนังสือปัญหาคณิตศาสตร์, สำนักพิมพ์ Springer International Publishing, หน้า115–133 , doi : 10.1007/978-3-319-97686-0_11 , ISBN  978-3-319-97684-6, MR 3930641 
  34. ↑วิลสัน (2014)หน้า 15
  35. ↑ Reed & Allwright 2008 ; Magnant & Martin (2011)
  36. ↑บาร์-นาตัน (1997 )
  37. ↑วิลสัน (2014) , 2.
  38. ↑วิลสัน (2014) , 6.
  39. ↑ Coxeter, HSM (ฤดูร้อน 1971), "คณิตศาสตร์ของการระบายสีแผนที่", Leonardo , 4 (3): 273– 277, doi : 10.2307/1572306 , JSTOR 1572306 
  • "ปัญหาสี่สี" , สารานุกรมคณิตศาสตร์ , EMS Press , 2001 [1994]
  • วิลสัน, โรบิน (มีนาคม 2026). "ทฤษฎีบทสี่สี: 1852–1976" (PDF) . ประกาศของสมาคมคณิตศาสตร์อเมริกัน . 73 (3): 216– 228. doi : 10.1090/noti3305 .
  • รายชื่อการสรุปทั่วไปของทฤษฎีบทสี่สีบนMathOverflow
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Four_color_theorem&oldid=1360672187 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ทฤษฎีสี่สี

ในทางคณิตศาสตร์ทฤษฎีบทสี่สีหรือทฤษฎีบทแผนที่สี่สีระบุว่าไม่จำเป็นต้องใช้สีมากกว่าสี่สีในการระบายสีบริเวณต่างๆ ของแผนที่เพื่อไม่ให้บริเวณที่อยู่ติดกันสองบริเวณมีสีเดียวกัน คำ

สูตร

การระบายสีแผนที่สามารถอธิบายได้ในแง่ของ ทฤษฎีกราฟ โดยพิจารณาในแง่ของการสร้าง การระบายสีกราฟ ของ กราฟระนาบ ของความสัมพันธ์ระหว่างภูมิภาค ในแง่ของทฤษฎีกราฟ ทฤษฎีบทกล่าวว่าสำหรับกราฟระนาบ ที่ไม่มีวงวน จี {\displaystyle G} โดยแสดงด้วย χ ( จี ) {\displaystyle \chi...

ความพยายามพิสูจน์เบื้องต้น

เท่าที่ทราบ [ 6 ] ข้อสันนิษฐานนี้ได้รับการเสนอครั้งแรกเมื่อวันที่ 23 ตุลาคม พ.ศ.

พิสูจน์โดยคอมพิวเตอร์

ในช่วงทศวรรษ 1960 และ 1970 นักคณิตศาสตร์ชาวเยอรมัน Heinrich Heesch ได้พัฒนาวิธีการใช้คอมพิวเตอร์เพื่อค้นหาการพิสูจน์ ที่น่าสังเกตคือ เขาเป็นคนแรกที่ใช้ การปล่อยประจุ เพื่อพิสูจน์ทฤษฎีบท ซึ่งกลายเป็นสิ่งสำคัญในส่วนของความไม่สามารถหลีกเลี่ยงได้ของการพิสูจน์...