ในทฤษฎีกราฟ การจับคู่ที่มีจำนวนสมาชิกสูงสุด ( maximum -cardinality matching)เป็นกราฟย่อยชนิดพิเศษที่มีประโยชน์ในบริบทการคำนวณหลายอย่าง เมื่อกำหนดกราฟG มาให้ การจับคู่คือกราฟย่อยที่ไม่มีขอบสองขอบใดใช้จุดยอดร่วมกัน จำนวนสมาชิกของการจับคู่คือจำนวนขอบในกราฟย่อย และจำนวนสมาชิกสูงสุดคือจำนวนขอบที่มากที่สุดที่การจับคู่สามารถมีได้ การจับคู่สำหรับกราฟที่กำหนดจะเป็นการจับคู่ที่มีจำนวนสมาชิกสูงสุดก็ต่อเมื่อจำนวนสมาชิกของการจับคู่เท่ากับจำนวนสมาชิกสูงสุดนี้ ถ้าเราคิดว่าแต่ละขอบ "ครอบคลุม" จุดยอดที่เชื่อมต่อกันเพียงครั้งเดียว การจับคู่สูงสุดก็คือการครอบคลุมที่ไม่ทับซ้อนกันที่ใหญ่ที่สุดของกราฟเช่นกัน ถ้าจุดยอดทั้งหมดถูกครอบคลุม เราเรียกว่าการจับคู่สมบูรณ์ (perfect matching ) สำหรับกราฟจำกัด การจับคู่ที่มีจำนวนสมาชิกสูงสุดจะมีอยู่เสมอ แต่โดยปกติแล้วจะไม่เป็นเอกลักษณ์ จำนวนสมาชิกของการจับคู่จะไม่เกินครึ่งหนึ่งของจำนวนจุดยอดและจะไม่เกินจำนวนขอบ

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

การคำนวณการจับคู่สูงสุดสำหรับกราฟที่กำหนดเป็นงานพื้นฐานในทฤษฎีกราฟ เชิง คำนวณ^{[ 1 ]} มีทฤษฎีบทลักษณะเฉพาะ ที่ไม่สร้างสรรค์ สำหรับขนาดของการจับคู่สูงสุด บทความนี้เกี่ยวกับการคำนวณการจับคู่สูงสุด

วิธีที่ง่ายที่สุดในการคำนวณการจับคู่ที่มีจำนวนสมาชิกสูงสุดคือการใช้อัลกอริทึมของฟอร์ด-ฟุลเคอร์สันอัลกอริทึมนี้แก้ปัญหาทั่วไปของการคำนวณการไหลสูงสุดกราฟสองส่วน( X + Y , E )สามารถแปลงเป็นเครือข่ายการไหลได้ดังนี้

• เพิ่มจุดเริ่มต้นs ; เพิ่มเส้นเชื่อมจากsไปยังแต่ละจุดยอดในX
• เพิ่มจุดรับข้อมูลt ; เพิ่มเส้นเชื่อมจากแต่ละจุดยอดในแกนYไปยังt
• กำหนดความจุ 1 ให้กับขอบแต่ละด้าน

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

• ปริมาณการไหลเข้าสู่แต่ละจุดยอดในX มีค่าไม่เกิน 1 ดังนั้นปริมาณการไหลออกก็มีค่าไม่เกิน 1 เช่นกัน ดังนั้นจึง มี เส้นเชื่อมที่อยู่ติดกับแต่ละจุดยอดใน Xไม่เกินหนึ่งเส้น
• ปริมาณการไหลออกของแต่ละจุดยอดในY มีค่าไม่เกิน 1 ดังนั้นปริมาณการไหลเข้าก็มีค่าไม่เกิน 1 เช่นกัน ดังนั้นจึง มี เส้นเชื่อมที่อยู่ติดกับแต่ละจุดยอดใน Yไม่เกินหนึ่งเส้น

อัลกอริทึม Ford–Fulkerson ดำเนินการโดยการค้นหาเส้นทางเสริมจากx ∈ Xไปยังy ∈ Y ซ้ำๆ และอัปเดตการจับคู่Mโดยการหาผลต่างสมมาตรของเส้นทางนั้นกับM (โดยสมมติว่ามีเส้นทางดังกล่าวอยู่) เนื่องจากแต่ละเส้นทางสามารถค้นหาได้ใน เวลา O ( E )ดังนั้นเวลาในการทำงานจึงเป็นO ( VE )และการจับคู่สูงสุดประกอบด้วยขอบของEที่นำพาการไหลจากXไปยัง Y

อัลกอริทึมที่ได้รับการปรับปรุงนี้คืออัลกอริทึม Hopcroft–Karp ที่ซับซ้อนกว่า ซึ่งค้นหาเส้นทางเสริมหลายเส้นทางพร้อมกัน อัลกอริทึมนี้ใช้เวลาในการทำงาน ${\displaystyle O({\sqrt {V}}E)}$

อัลกอริทึมของ Chandran และ Hochbaum ^{[ 2 ]}สำหรับกราฟสองส่วนจะทำงานในเวลาที่ขึ้นอยู่กับขนาดของการจับคู่สูงสุดkซึ่งสำหรับ| X | < | Y |คือ

${\displaystyle O\left(\min\{|X|k,E\}+{\sqrt {k}}\min\{k^{2},E\}\right).}$

การใช้การดำเนินการบูลีนกับคำที่มีขนาดความซับซ้อนจะได้รับการปรับปรุงเพิ่มเติมเป็น^{[ 2 ]}${\displaystyle \lambda }$

${\displaystyle O\left(\min \left\{|X|k,{\frac {|X||Y|}{\lambda }},E\right\}+k^{2}+{\frac {k^{2.5}}{\lambda }}\right).}$

มีอัลกอริทึมที่มีประสิทธิภาพมากกว่านี้สำหรับกราฟสองส่วนแบบพิเศษบางประเภท:

• สำหรับ กราฟสองส่วนแบบ เบาบางปัญหาการจับคู่สูงสุดสามารถแก้ไขได้ด้วยอัลกอริทึมของ Madry โดยอาศัยการไหลของกระแสไฟฟ้า^{[ 3 ]}${\displaystyle {\tilde {O}}(E^{10/7})}$
• สำหรับ กราฟสองส่วน ระนาบปัญหาสามารถแก้ไขได้ในเวลาO ( n log ³ n )โดยที่nคือจำนวนจุดยอด โดยการลดปัญหาให้เหลือเพียงการไหลสูงสุดที่มีแหล่งกำเนิดและจุดรับหลายจุด^{[ 4 ]}

อัลกอริทึม Blossomค้นหาการจับคู่ที่มีจำนวนสมาชิกสูงสุดในกราฟทั่วไป (ไม่จำเป็นต้องเป็นกราฟสองส่วน) โดยใช้เวลาในการทำงาน ประสิทธิภาพที่ดีกว่าO ( √ V E )สำหรับกราฟทั่วไป ซึ่งเทียบเท่ากับประสิทธิภาพของอัลกอริทึม Hopcroft–Karpบนกราฟสองส่วน สามารถทำได้ด้วยอัลกอริทึมที่ซับซ้อนกว่ามากของ Micali และ Vazirani ^{[ 5 ]}ขอบเขตเดียวกันนี้ทำได้ด้วยอัลกอริทึมของ^Blum [ ^{6 ] และ}อัลกอริทึมของGabowและTarjan [ ^{7 ]}${\displaystyle O(|V|^{2}\cdot |E|)}$

แนวทางทางเลือกใช้การสุ่มและอิงตาม อัลกอริธึม การคูณเมทริกซ์ แบบเร็ว วิธีนี้ให้อัลกอริธึมแบบสุ่มสำหรับกราฟทั่วไปที่มีความซับซ้อน[ ^{8 ] ใน} ทางทฤษฎีแล้ววิธีนี้ดีกว่าสำหรับ กราฟที่มีความหนาแน่นเพียงพอแต่ในทางปฏิบัติอัลกอริธึมจะช้ากว่า^{[ 2 ]}${\displaystyle O(V^{2.372})}$

อัลกอริทึมอื่นๆ สำหรับงานนี้ได้รับการตรวจสอบโดย Duan และ Pettie ^{[ 9 ]} (ดูตารางที่ I) ในแง่ของอัลกอริทึมการประมาณค่าพวกเขายังชี้ให้เห็นว่าอัลกอริทึม Blossomและอัลกอริทึมของ Micali และ Vazirani สามารถมองได้ว่าเป็นอัลกอริทึมการประมาณค่าที่ทำงานในเวลาเชิงเส้นสำหรับขอบเขตข้อผิดพลาดคงที่ใดๆ

• การค้นหาการจับคู่ที่มีจำนวนสมาชิกมากที่สุด จะช่วยให้สามารถตัดสินได้ว่ามีการจับคู่ที่สมบูรณ์แบบ อยู่หรือ ไม่
• ปัญหาการหาคู่ที่น้ำหนักสูงสุดในกราฟถ่วงน้ำหนักเรียกว่าปัญหาการจับคู่น้ำหนักสูงสุดและการจำกัดปัญหานี้ไปยังกราฟสองส่วนเรียกว่าปัญหาการกำหนดงานหากแต่ละจุดยอดสามารถจับคู่กับจุดยอดหลายจุดพร้อมกันได้ ปัญหานี้จะเป็น ปัญหาการกำหนดงาน แบบทั่วไป
• การจับคู่ตามลำดับความสำคัญคือการจับคู่ที่มีจำนวนสมาชิกสูงสุดแบบเฉพาะเจาะจง ซึ่งสมาชิกที่มีลำดับความสำคัญจะถูกจับคู่ก่อน
• ปัญหาของการค้นหาการจับคู่ที่มีจำนวนสมาชิกสูงสุดในไฮเปอร์กราฟเป็นปัญหา NP-complete แม้แต่สำหรับไฮเปอร์กราฟแบบ 3-uniform ก็ตาม^{[ 10 ]}