เกมคณิตศาสตร์บอกอะไรเราเกี่ยวกับทฤษฎีกราฟ

BIG MOUTH สำหรับนิตยสาร Quanta

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

ท้าให้ทุกคนในกลุ่มของคุณจับมือกัน แต่กับคนจำนวนคี่เท่านั้น (อย่าลังเลที่จะไฮไฟว์อากาศแทนถ้าคุณต้องการระยะห่างทางสังคมมากกว่านี้อีกเล็กน้อย) สมมติว่าเป็นคุณและเพื่อนของคุณหกคน

ในตอนเริ่มต้น ทุกคนจับมือศูนย์ ดังนั้นคุณจึงเริ่มต้นที่เลขคู่ สมมติว่าแอนนาและไบรอนใช้ความคิดริเริ่มและจับมือกัน ตอนนี้พวกเขาจับมือกันคนละที่

fig_1.svg

Merrill Sherman/นิตยสาร Quanta

Caitlin ต้องการเข้าร่วม ดังนั้นเธอจึงจับมือของ Byron โดยให้การจับมือหนึ่งครั้งเป็นเลขคี่ แต่ตอนนี้ไบรอนมีการจับมือสองครั้ง ดังนั้นเขาจึงกลับมาเป็นเลขคู่

fig_2.svg

Demarr, Ernest และ Flora กระโดดเข้ามาและเริ่มจับมือกัน พลิกเลขคู่เป็นอัตราต่อรองและในทางกลับกัน

fig_3.svg

ในที่สุดเพื่อนทั้งหกของคุณก็คิดออกและมาถึงการกำหนดค่าที่ชนะ

fig_9-1.svg

แต่คุณยังคงต้องจับมือใครสักคน และการจับมืออีกหนึ่งครั้งนั้นสร้างความแตกต่างอย่างมาก เมื่อคุณจับมือกันแล้ว เพื่อนของคุณคนหนึ่งจะจับมือกันเป็นจำนวนเท่าๆ กัน และตอนนี้เกมต้องกลับมาเล่นต่อ

fig_4.svg

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

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

fig_5-1.svg

จุดยอดตัวอย่างและองศา

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

วิธีหนึ่งในการคำนวณผลรวมดีกรีของกราฟคือ แสดงรายการองศาทั้งหมดและบวกเข้าด้วยกัน แต่มีอีกวิธีหนึ่งที่ต้องอาศัยการบัญชีที่ชาญฉลาดของขอบ เนื่องจากขอบแต่ละด้านเชื่อมต่อกับจุดยอดสองจุด การมีส่วนร่วมของผลรวมของดีกรีโดยรวมคือสองจุด: หนึ่งจุดสำหรับแต่ละจุดยอดที่เชื่อมต่อ ดังนั้นการรวมองศาทั้งหมดในกราฟจึงเหมือนกับการนับทุกขอบสองครั้ง เนื่องจากผลรวมดีกรีเป็นสองเท่าของจำนวนขอบ สำหรับกราฟใดๆ มันต้องเป็นเลขคู่เสมอ

fig_6-1.svg

อันที่จริง เราเห็นเร็วกว่านั้นด้วยซ้ำ: ช่วงเวลาที่สองคนแรกจับมือกัน

fig_7.svg

ถ้าเล่นกันแค่สองคน ก็เป็นไปได้ที่แต่ละคนจะจับมือกันเป็นเลขคี่ คุณสามารถมองคู่นี้ว่าเป็น “กราฟย่อยคี่” ซึ่งเป็นกราฟที่เล็กกว่าภายในกราฟที่ใหญ่กว่าซึ่งมีจุดยอดทั้งหมดมีดีกรีคี่

เมื่อสร้างกราฟย่อย คุณจะต้องเลือกชุดของจุดยอดและพิจารณาเฉพาะขอบระหว่างจุดยอดเหล่านั้น ซึ่งหมายความว่าคุณไม่สนใจขอบที่เชื่อมต่อกับจุดยอดใดๆ นอกกราฟย่อยของคุณ

fig_8.svg

การสร้างกราฟย่อยโดยไม่สนใจขอบ

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

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

เป็นที่ทราบกันดีอยู่แล้วว่าทุกกราฟจะมีกราฟย่อยขนาดใหญ่ ในปี 1960 Tibor Gallai นักคณิตศาสตร์ชาวฮังการีได้พิสูจน์ว่าทุกกราฟสามารถแบ่งออกเป็นสองกราฟย่อยได้ การทำเช่นนี้จะแบ่งชุดของ n จุดยอดออกเป็นสองส่วนย่อย และหนึ่งในเซตย่อยเหล่านั้นจะต้องมีจุดยอดอย่างน้อยครึ่งหนึ่ง สิ่งนี้รับประกันได้ว่าทุกกราฟจะมีกราฟย่อยคู่ที่ใหญ่อย่างน้อยครึ่งหนึ่งของต้นฉบับ

แต่กราฟย่อยที่คี่จะใหญ่แค่ไหนนั้นเป็นคำถามการวิจัยแบบเปิดในทฤษฎีกราฟมานานกว่า 60 ปี ในกราฟเกมปาร์ตี้ที่ล้มเหลวของเรา มีกราฟย่อยแบบคี่ที่ใช้จุดยอดหกจุดจากเจ็ดจุด

fig_10.svg

ซึ่งค่อนข้างใหญ่เมื่อเทียบกับของเดิม แต่นี่คือความพยายามที่ล้มเหลวอีกครั้งในเกมด้วยกราฟย่อยสูงสุดคี่ที่เล็กกว่า ซึ่งใช้จุดยอดเดิมเพียงสี่จุด

fig_11-1.svg

กราฟที่มีกราฟย่อยคี่สูงสุดที่ใช้จุดยอดเพียงสี่จุดจากเจ็ดจุด

ในการค้นหากราฟย่อยคี่ที่รับประกันที่ใหญ่ที่สุด บางความสำเร็จในช่วงต้นแสดงเศษส่วนของจุดยอดที่ใช้ในแง่ของขนาดของกราฟเดิมเอง ตัวอย่างเช่น ในปี 1990 นักคณิตศาสตร์ ยาอีร์ คาโร แสดงให้เห็นว่ากราฟใดๆ ที่มีจุดยอด n จุดต้องมีกราฟย่อยคี่ที่มีอย่างน้อย png.ลาเท็กซ์?%5Cfrac%7B1%7D%7B%5Csqrt%7Bn%7 ของยอดรวม นี่หมายความว่ากราฟที่มีจุดยอด 25 จุดต้องมีกราฟย่อยคี่ที่มีอย่างน้อย png.ลาเท็กซ์?%5Cfrac%7B1%7D%7B5%7D ของจุดยอด 25 จุด และกราฟที่มีจุดยอด 100 จุด จะมีกราฟย่อยคี่ที่มีอย่างน้อย png.ลาเท็กซ์?%5Cfrac%7B1%7D%7B10%7D ของจุดยอด 100 จุด ผลลัพธ์ที่คล้ายกันตามมา แต่นักคณิตศาสตร์กำลังมองหาสิ่งที่ Gallai พบ: เศษส่วนเดียวที่ใช้กับ subgraphs คี่ได้ png.ลาเท็กซ์?%5Cfrac%7B1%7D%7B2%7D ทำงานได้แม้กระทั่ง subgraphs

ในที่สุดผลลัพธ์ดังกล่าวก็มาถึงในปี 2021 เมื่อ Asaf Ferber และ Michael Krivelevich พิสูจน์ว่าทุกกราฟมี subgraph ที่แปลกซึ่งใช้อย่างน้อย png.ลาเท็กซ์?%5Cfrac%7B1%7D%7B10,000%7D ของจุดยอดของกราฟเดิม นี่อาจดูเหมือนแท่งต่ำที่จะตั้งค่า โดยเฉพาะอย่างยิ่งเมื่อบางคนคาดการณ์ว่าเศษส่วนจริงนั้นอยู่ใกล้ png.ลาเท็กซ์?%5Cfrac%7B2%7D%7B7%7D แต่การหาเศษส่วนเดียวที่ใช้ได้ผลทำให้นักคณิตศาสตร์เปลี่ยนจากการพิสูจน์ว่าเศษส่วนนั้นมีอยู่แล้วเพื่อปรับปรุงเศษส่วนที่มีอยู่แล้ว หมายเลขหนึ่ง เช่นเดียวกับการจับมือหนึ่งครั้ง สามารถสร้างความแตกต่างได้มาก

การออกกำลังกาย

  1. ค้นหากราฟย่อยคี่ที่ใหญ่ที่สุดของกราฟที่แสดงด้านล่าง

fig_12.svg

  1. แสดงวิธีแยกลูปด้านล่างออกเป็นกราฟย่อยคี่และกราฟย่อยคู่

fig_13.svg

  1. กราฟที่สมบูรณ์บนจุดยอด n จุด คือกราฟที่จุดยอด n จุดแต่ละจุดเชื่อมต่อกันด้วยขอบไปยังจุดยอดอื่นทุกจุด กราฟที่สมบูรณ์อาจเป็นกราฟคี่ได้หรือไม่
  1. ในทศวรรษที่ 1960 Tibor Gallai ได้พิสูจน์ว่าสามารถแบ่งกราฟออกเป็นสองกราฟย่อยได้เสมอ จากสิ่งที่คุณได้อ่านในคอลัมน์นี้ คุณสามารถพิสูจน์ได้ว่าไม่สามารถแยกกราฟออกเป็นสองกราฟย่อยที่คี่ เหตุผลคืออะไร?

คลิกเพื่อตอบ 1:

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

fig_14.svg

คลิกเพื่อตอบ 2:

ทางออกหนึ่งคือใส่ A และ D ลงในกราฟย่อยของตัวเอง เนื่องจากไม่เชื่อมต่อถึงกัน องศาในกราฟย่อยนี้จึงเป็นศูนย์ทั้งคู่ ทำให้เป็นกราฟย่อยคู่ องศาในกราฟย่อยอื่นเป็น 1 ทั้งหมด ดังนั้นนี่คือกราฟย่อยคี่ หมายเหตุ: นี่เป็นตัวอย่างของกราฟที่ “ขาดการเชื่อมต่อ”

fig_15.svg

คลิกเพื่อตอบ 3:

ใช่. เมื่อ n เป็นเลขคู่ กราฟที่สมบูรณ์บนจุดยอด n จุดจะเป็นกราฟคี่เสมอ จุดยอดแต่ละจุดจะเชื่อมกับจุดยอด n − 1 จุด อีกจุด ทำให้ดีกรีของจุดยอดทุกจุด n − 1 เป็นจำนวนคี่ เนื่องจาก n เป็นจำนวนคู่ ดังนั้นนี่คือกราฟคี่ และเมื่อ n เป็นเลขคี่ กราฟที่สมบูรณ์บนจุดยอด n จุดจะเป็นกราฟคู่

คลิกเพื่อตอบ 4:

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

ใส่ความเห็น