คณิตศาสตร์เชิงผสม

การประยุกต์ทฤษฎีกราฟ

กราฟระนาบ

กราฟ G ถูกเรียกว่าระนาบถ้ามันสามารถแสดงบนระนาบในลักษณะที่ว่าจุดยอดเป็นจุดที่แตกต่างกันทั้งหมดขอบเป็นเส้นโค้งที่เรียบง่ายและไม่มีสองขอบพบกันยกเว้นที่ขั้วของพวกเขา ตัวอย่างเช่น K ₄กราฟที่สมบูรณ์ของสี่จุดยอดคือภาพถ่ายตามที่แสดงในรูปที่ 4A

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

กราฟK _{m, n}คือกราฟที่ชุดจุดสุดยอดสามารถแบ่งออกเป็นสองชุดย่อยหนึ่งชุดมีจุดยอด m และอีกชุดหนึ่งมีจุดยอด n จุดยอดสองจุดใด ๆ ของชุดย่อยเดียวกันนั้นอยู่ติดกันในขณะที่จุดยอดสองจุดของชุดย่อยต่างกันอยู่ติดกัน นักคณิตศาสตร์ชาวโปแลนด์ Kazimierz Kuratowski ในปี 1930 ได้พิสูจน์ทฤษฎีบทที่มีชื่อเสียงดังต่อไปนี้:

เงื่อนไขที่จำเป็นและเพียงพอสำหรับกราฟ G ที่จะเป็นภาพถ่ายคือมันไม่ได้มีกราฟย่อยโฮมโมมอร์ฟิคถึง K ₅หรือ K _{3,3 ที่}แสดงในรูปที่ 5

การหดตัวเบื้องต้นของกราฟ G คือการแปลง G เป็นกราฟใหม่ G ₁เช่นจุดยอดสองจุดที่อยู่ติดกัน u และυของ G จะถูกแทนที่ด้วยจุดยอดใหม่ w ใน G ₁และ w อยู่ใน G ₁กับจุดยอดทั้งหมดไป ซึ่งคุณหรือυอยู่ติดกันใน G กราฟ G * ถูกกล่าวว่าเป็นการหดตัวของ G ถ้า G * สามารถได้รับจาก G ตามลำดับของการหดตัวเบื้องต้น ต่อไปนี้เป็นลักษณะของกราฟระนาบอีกเนื่องจากนักคณิตศาสตร์ชาวเยอรมัน K. Wagner ในปี 1937

กราฟเป็นระนาบหากว่าไม่สามารถทำสัญญากับ K ₅หรือ K _3,3ได้

ปัญหาแผนที่สี่สี

เป็นเวลากว่าศตวรรษที่คำตอบของปัญหาแผนที่สี่สีทำให้นักวิเคราะห์ทุกคนที่พยายามลองดู ปัญหาอาจดึงดูดความสนใจของMöbius แต่การอ้างอิงเป็นลายลักษณ์อักษรครั้งแรกดูเหมือนว่าจะเป็นจดหมายจากฟรานซิสกูทรีถึงพี่ชายของเขานักเรียนของออกัสตัสเดอมอร์แกน 2395 ใน

ปัญหาเกี่ยวข้องกับแผนที่ระนาบ - นั่นคือการแบ่งย่อยของเครื่องบินในภูมิภาคที่ไม่มีการเหลื่อมกันล้อมรอบด้วยเส้นโค้งปิดแบบง่าย ในแผนที่ทางภูมิศาสตร์นั้นมีการสังเกตสังเกตุในกรณีพิเศษหลาย ๆ อย่างที่ได้มีการพยายามซึ่งส่วนใหญ่จำเป็นต้องมีสี่สีเพื่อให้สีของภูมิภาคเพื่อให้สองภูมิภาคที่ใช้ขอบเขตร่วมกันมีสีที่ต่างกันเสมอและใน บางกรณีที่จำเป็นต้องมีอย่างน้อยสี่สี (ภูมิภาคที่พบเฉพาะ ณ จุดหนึ่งเช่นรัฐโคโลราโดและแอริโซนาในสหรัฐอเมริกาจะไม่ถือว่ามีขอบเขตร่วมกัน) การทำให้เป็นทางการของการสังเกตเชิงประจักษ์นี้ถือเป็นสิ่งที่เรียกว่า "ทฤษฎีบทสี่สี" ปัญหาคือการพิสูจน์หรือหักล้างการยืนยันว่านี่เป็นกรณีสำหรับแผนที่ระนาบทุกครั้ง สามสีนั้นจะไม่เพียงพอที่จะแสดงให้เห็นได้ง่ายในขณะที่ความเพียงพอของห้าสีได้รับการพิสูจน์ในปี 1890 โดยนักคณิตศาสตร์ชาวอังกฤษ PJ Heawood

ในปี 1879 AB Kempe ชาวอังกฤษเสนอวิธีการแก้ปัญหาสี่สี แม้ว่า Heawood แสดงให้เห็นว่าข้อโต้แย้งของ Kempe นั้นมีข้อบกพร่อง แต่แนวคิดสองข้อนั้นพิสูจน์แล้วว่ามีประโยชน์ในการสืบสวนในภายหลัง หนึ่งในสิ่งเหล่านี้เรียกว่าไม่สามารถหลีกเลี่ยงได้ระบุสถานะที่เป็นไปไม่ได้ในการสร้างแผนที่ที่ขาดการกำหนดค่าทุกอย่างในสี่ (การกำหนดค่าเหล่านี้ประกอบด้วยภูมิภาคที่มีเพื่อนบ้านสองคนหนึ่งกับสามหนึ่งกับสี่ แนวคิดที่สองที่ว่า reducibility ใช้ชื่อมาจากหลักฐานที่ถูกต้องของ Kempe ว่าหากมีแผนที่ที่ต้องการสีอย่างน้อยห้าสีและมีพื้นที่ที่มีเพื่อนบ้านสี่คน (หรือสามหรือสองคน) ต้องมีแผนที่ที่ต้องใช้ห้า สีสำหรับภูมิภาคจำนวนน้อย ความพยายามของ Kempe ในการพิสูจน์ความสามารถในการลดความผิดพลาดของแผนที่ที่มีพื้นที่ซึ่งมีห้าประเทศเพื่อนบ้านนั้นผิดพลาด แต่มันได้รับการแก้ไขในหลักฐานที่ตีพิมพ์ในปี 1976 โดย Kenneth Appel และ Wolfgang Haken ของสหรัฐอเมริกา ข้อพิสูจน์ของพวกเขาดึงดูดนักวิจารณ์บางคนเพราะมันจำเป็นต้องมีการประเมินกรณีที่แตกต่างกันถึง 1,936 กรณีโดยแต่ละคดีเกี่ยวข้องกับการปฏิบัติการเชิงตรรกะมากกว่า 500,000 ครั้ง Appel, Haken และผู้ทำงานร่วมกันคิดค้นโปรแกรมที่ทำให้คอมพิวเตอร์ดิจิตอลขนาดใหญ่สามารถจัดการรายละเอียดเหล่านี้ได้ คอมพิวเตอร์ต้องใช้เวลามากกว่า 1,000 ชั่วโมงในการปฏิบัติงานและการพิสูจน์อย่างเป็นทางการที่ได้นั้นมีความยาวหลายร้อยหน้า

วงจร Eulerian และปัญหาสะพานKönigsberg

Multigraph G ประกอบด้วยชุด V (G) ที่ไม่ว่างเปล่าและเซตย่อย E (G) ของชุดองค์ประกอบคู่ที่ไม่เรียงลำดับของ V (G) ที่มีความถี่ f ≥ 1 ติดอยู่กับแต่ละคู่ หากคู่ (x ₁, x ₂) ที่มีความถี่ f เป็นของ E (G) ดังนั้นจุดยอด x ₁และ x ₂จะถูกรวมเข้าด้วยกันโดยขอบ f

วัฏจักรของออยเลอรีของมัลติจิง G เป็นสายโซ่ปิดที่แต่ละขอบจะปรากฏขึ้นหนึ่งครั้ง ออยเลอร์แสดงให้เห็นว่าการประดิษฐ์ตัวอักษรมีวัฏจักรของออยเลอร์ต่อเมื่อมีการเชื่อมต่อ (นอกเหนือจากจุดที่แยกได้) และจำนวนจุดยอดที่มีระดับคี่เป็นศูนย์หรือสอง

ปัญหานี้เกิดขึ้นก่อนในลักษณะดังต่อไปนี้ แม่น้ำพรีเจลเกิดขึ้นจากการรวมกันของสองสาขาไหลผ่านเมืองKönigsbergและไหลผ่านทั้งสองด้านของเกาะ Kneiphof มีสะพานเจ็ดแห่งดังแสดงในรูปที่ 6A ชาวเมืองสงสัยว่าเป็นไปได้หรือไม่ที่จะเดินและข้ามสะพานแต่ละครั้ง สิ่งนี้เทียบเท่ากับการค้นหาวัฏจักรของออยเลอร์สำหรับการเขียนด้วยลายมือในรูปที่ 6B ออยเลอร์แสดงให้เห็นว่ามันเป็นไปไม่ได้เพราะมีจุดยอดสี่จุดที่แปลก