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

ทฤษฎีบท ของเมนเกอร์ในรูปแบบ การเชื่อมต่อขอบมีดังนี้:

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

ความหมายสำหรับกราฟGคือเวอร์ชันต่อไปนี้:

กราฟจะเรียกว่าเชื่อมต่อด้วยขอบk เส้น (กราฟยังคงเชื่อมต่อกันอยู่แม้จะลบขอบออกไปน้อยกว่าkเส้น) ก็ต่อเมื่อทุกคู่ของจุดยอดมี เส้นทางที่ไม่ทับซ้อนกันด้วยขอบ kเส้นเชื่อมระหว่างกัน

ข้อความแสดงการเชื่อมต่อจุดยอดของทฤษฎีบทของเมนเกอร์มีดังนี้:

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

ผลที่ตามมาสำหรับกราฟ Gทั้งหมดคือเวอร์ชันนี้:

กราฟจะเรียกว่าเป็นกราฟที่เชื่อมต่อกันด้วยk จุดยอด (มีจุดยอดมากกว่าkจุด และยังคงเชื่อมต่อกันอยู่แม้จะลบจุดยอดออกไปน้อยกว่าkจุด) ก็ต่อเมื่อทุกคู่ของจุดยอดมีเส้นทางที่ไม่ทับซ้อนกันภายในอย่างน้อยkเส้นทางระหว่างกัน

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

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

สำหรับเซตของจุดยอดA, B ⊂ G (ไม่จำเป็นต้องเป็นจุดยอดที่ตัดกัน) เส้นทาง ABคือเส้นทางในGที่มีจุดเริ่มต้นอยู่ในAจุดสิ้นสุดอยู่ในBและไม่มีจุดยอดภายในใดๆ อยู่ในAหรือBเราอนุญาตให้มีเส้นทางที่มีจุดยอดเพียงจุดเดียวในA ∩ Bและไม่มีขอบใดๆ ตัวแยก ABขนาดkคือเซตSของ จุดยอด kจุด (ซึ่งอาจตัดกับAและB ) โดยที่G−Sไม่มีเส้นทางAB ตัวเชื่อม ABขนาดkคือการรวมกันของเส้นทาง AB k เส้นทาง ที่ไม่มีจุดยอดตัดกัน

ทฤษฎีบท:ขนาดต่ำสุดของ ตัวคั่น ABเท่ากับขนาดสูงสุดของตัวเชื่อมต่อAB

กล่าวอีกนัยหนึ่ง หากไม่มี จุดยอด k −1 จุดที่ตัดการเชื่อมต่อAจากBแล้ว จะมีเส้นทางที่ไม่ซ้ำกันk เส้นทางจาก AไปยังBรูปแบบนี้บ่งบอกถึงข้อความการเชื่อมต่อจุดยอดข้างต้น: สำหรับx,y ∈ Gในส่วนก่อนหน้า ให้ใช้ทฤษฎีบทปัจจุบันกับG −{ x,y } โดยที่A = N(x) , B = N(y)ซึ่งเป็นจุดยอดข้างเคียงของx,yจากนั้นเซตของจุดยอดที่ตัดการเชื่อมต่อxและyจะเหมือนกับ ตัวแยก ABและการลบจุดยอดปลายในเซตของ เส้นทาง xy ที่เป็นอิสระ จะให้ตัวเชื่อมต่อ AB

พิสูจน์ทฤษฎีบท: ^{[ 1 ]} การเหนี่ยวนำบนจำนวนขอบในGสำหรับGที่ไม่มีขอบ ตัวแยก AB ขั้นต่ำ คือA ∩ Bซึ่งเป็น ตัวเชื่อมต่อ ABที่ประกอบด้วยเส้นทางจุดยอดเดียว

สำหรับGที่มีขอบeเราอาจสันนิษฐานโดยการอุปมานว่าทฤษฎีบทนี้ใช้ได้กับG−eถ้าG−eมี ตัวคั่น AB ขั้นต่ำ ที่มีขนาดkแล้วจะมี ตัวเชื่อมต่อ ABที่มีขนาดkในG−eและด้วยเหตุนี้จึงมีในGด้วย

ในทางกลับกัน ให้Sเป็น ตัวแยก ABของG−eที่มีขนาดเล็กกว่าkโดยที่ทุกเส้นทางAB ใน GจะมีจุดยอดของSหรือขอบeขนาดของSต้องเป็นk-1เพราะถ้ามีขนาดเล็กกว่านั้นSร่วมกับจุดปลายใดจุดหนึ่งของeจะเป็น ตัวแยก AB ที่ดีกว่า ของGในG−Sมี เส้นทาง ABผ่านeเนื่องจากSเพียงอย่างเดียวมีขนาดเล็กเกินไปที่จะเป็น ตัวแยก ABของGให้v เป็นจุดยอดก่อนหน้าและv เป็นจุดยอดหลังของeบนเส้นทางดังกล่าว แล้วv สามารถเข้าถึงได้จากAแต่ไม่สามารถเข้าถึงได้จากBในG−S−eในขณะที่v สามารถเข้าถึงได้จากBแต่ไม่ สามารถ เข้าถึง ได้จาก A

ทีนี้ ให้S = S ∪ {v }และพิจารณาตัวคั่นAS ขั้นต่ำ TในG−eเนื่องจากv ไม่สามารถเข้าถึงได้จากAในG−S ดังนั้นTจึงเป็น ตัวคั่น AS ในG ด้วย แล้วTก็เป็น ตัวคั่น ABในG ด้วย (เพราะทุกเส้นทางAB ตัดกับ S ) ดังนั้นจึงมีขนาดอย่างน้อยkโดยการอุปมานG−eประกอบด้วยตัวเชื่อมต่อAS C ที่มีขนาดkเนื่องจากขนาดของมัน จุดปลายของเส้นทางในนั้นจะต้องตรงกับS 1

ในทำนองเดียวกัน หากกำหนดให้S = S ∪ {v } ตัวคั่น S Bขั้นต่ำจะมีขนาดkและมีตัวเชื่อมต่อS B C ที่มีขนาดkโดยมีเส้นทางที่มีจุดเริ่มต้นอยู่ที่S พอดี

นอกจากนี้ เนื่องจากS ตัดการเชื่อมต่อGเส้นทางทุกเส้นในC จึงแยกออกจากเส้นทางทุกเส้นในC ภายใน และเราสามารถกำหนด ตัวเชื่อมต่อ ABขนาดkในG ได้ โดยการต่อเส้นทาง ( เส้นทาง k−1เส้นทางผ่านSและเส้นทางหนึ่งเส้นผ่านe=v v ) พิสูจน์เสร็จสิ้น

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

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

สูตรที่ใช้กับกราฟระบุทิศทางแบบจำกัดซึ่งเทียบเท่ากับสูตรข้างต้นมีดังนี้:

ให้AและBเป็นเซตของจุดยอดในกราฟระบุทิศทาง จำกัดGแล้วจะมีกลุ่มPของ เส้นทาง AB ที่ไม่ซ้ำกัน และ เซตแยก ABที่ประกอบด้วยจุดยอดเพียงจุดเดียวจากแต่ละเส้นทางในP

ในเวอร์ชันนี้ ทฤษฎีบทนี้ได้มาอย่างค่อนข้างง่ายดายจากทฤษฎีบทของ Kőnigกล่าวคือ ในกราฟสองส่วนขนาดขั้นต่ำของส่วนปกคลุมจะเท่ากับขนาดสูงสุดของการจับคู่

วิธีการนี้ทำได้ดังนี้: แทนที่จุดยอดv ทุกจุด ในกราฟระบุทิศทางD เดิม ด้วยจุดยอดสองจุดv'และv''และแทนที่ขอบuv ทุกเส้น ด้วยขอบu'v''นอกจากนี้ ให้เพิ่มขอบv'v''สำหรับทุกจุดยอดvที่ไม่ได้อยู่ในAหรือBผลลัพธ์ที่ได้คือกราฟสองส่วน ซึ่งด้านหนึ่งประกอบด้วยจุดยอดv'และอีกด้านหนึ่งประกอบด้วยจุดยอดv' '

เมื่อใช้ทฤษฎีบทของ Kőnig เราจะได้การจับคู่MและการปกคลุมCที่มีขนาดเท่ากัน โดยเฉพาะอย่างยิ่ง จุดปลายเพียงจุดเดียวของแต่ละขอบของMจะอยู่ในCเพิ่ม จุดยอด a''ทั้งหมด ลงใน Cสำหรับaที่อยู่ในAและจุดยอดb' ทั้งหมด สำหรับbที่อยู่ในBให้Pเป็นเซตของเส้นทางAB ทั้งหมดที่ประกอบด้วยขอบ uvในDโดยที่u'v''อยู่ใน M ให้Qในกราฟดั้งเดิมประกอบด้วยจุดยอดv ทั้งหมด โดยที่ทั้งv'และv''อยู่ในCสามารถตรวจสอบได้อย่างง่ายดายว่าQเป็น เซตแยก ABเส้นทางทุกเส้นในตระกูลPมีจุดยอดจากQ เพียงจุดเดียว และจุดยอดทุกจุดในQอยู่บนเส้นทางจากPตามที่ต้องการ^{[ 2 ]}

ทฤษฎีบทของเมนเกอร์ใช้ได้กับกราฟอนันต์ และในบริบทนั้น ทฤษฎีบทนี้ใช้ได้กับการตัดขั้นต่ำระหว่างองค์ประกอบสองตัวใดๆ ที่เป็นจุดยอดหรือปลายของกราฟ ( Halin 1974 ) ผลลัพธ์ต่อไปนี้ของรอน อาฮาโรนีและอีไล เบอร์เกอร์เดิมทีเป็นข้อสันนิษฐานที่เสนอโดยพอล เออร์โดสและก่อนที่จะได้รับการพิสูจน์นั้นเป็นที่รู้จักกันในชื่อข้อสันนิษฐานเออร์โดส-เมนเกอร์มันเทียบเท่ากับทฤษฎีบทของเมนเกอร์เมื่อกราฟเป็นกราฟจำกัด

ให้AและBเป็นเซตของจุดยอดในกราฟระบุทิศทางG (ซึ่งอาจเป็นอนันต์) แล้วจะมีกลุ่มPของ เส้นทาง A - B ที่ไม่ซ้ำกัน และเซตคั่นซึ่งประกอบด้วยจุดยอดเพียงจุดเดียวจากแต่ละเส้นทางในP

• แกมโมอิด
• กราฟที่เชื่อมต่อจุดยอด k จุด
• กราฟที่เชื่อมต่อด้วยขอบ k
• ตัวคั่นจุดยอด

• เมนเกอร์, คาร์ล (1927) "ซูร์ อัลเกไมเนน คูร์เวนธีโอรี" . กองทุน. คณิตศาสตร์ . 10 : 96– 115. ดอย : 10.4064/fm-10-1-96-115 .
• อาฮาโรนี, รอน; เบอร์เกอร์, อีไล (2008) "ทฤษฎีบทของ Menger สำหรับกราฟอนันต์" สิ่งประดิษฐ์ทางคณิตศาสตร์ . 176 (1): 1– 62. arXiv : math/ 0509397 Bibcode : 2009InMat.176....1A . ดอย : 10.1007/s00222-008-0157-3 . S2CID  15355399 .
• ฮาลิน ร. (1974) "หมายเหตุเกี่ยวกับทฤษฎีบทของ Menger สำหรับกราฟจำกัดเฉพาะจุดอนันต์" Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 40 : 111– 114. ดอย : 10.1007/BF02993589 . S2CID  120915644 .

• การพิสูจน์ทฤษฎีบทของเมนเกอร์
• ทฤษฎีบทของเมนเกอร์และการไหลสูงสุด-การตัดต่ำสุด