ในทฤษฎีกราฟโพลีโทปการจับคู่ของกราฟที่กำหนดคือวัตถุทางเรขาคณิตที่แสดงถึงการจับคู่ที่เป็นไปได้ในกราฟมันคือโพลีโทปนูนซึ่งแต่ละมุมสอดคล้องกับการจับคู่ มันมีความสำคัญทางทฤษฎีอย่างมากในทฤษฎีการจับคู่^{[ 1 ] : 273–285}

ให้G = ( V , E ) เป็นกราฟที่มี โหนด n = | V | โหนด และ เส้นเชื่อม m = | E | เส้น

สำหรับเซตย่อย Uของจุดยอดแต่ละเซตเวกเตอร์ความสัมพันธ์1 _Uคือเวกเตอร์ขนาดnโดยที่สมาชิกvมีค่าเป็น 1 ถ้าจุดยอด v อยู่ในUและมีค่าเป็น 0 ถ้าไม่อยู่ใน U ในทำนองเดียวกัน สำหรับเซตย่อยFของขอบแต่ละเซต เวกเตอร์ความสัมพันธ์1 _Fคือเวกเตอร์ขนาดmโดยที่สมาชิกeมีค่าเป็น 1 ถ้าขอบeอยู่ในFและมีค่าเป็น 0 ถ้าไม่ อยู่ใน F

สำหรับทุกโหนดvในVเซตของขอบในEที่อยู่ติดกับvจะถูกแทนด้วยE ( v ) ดังนั้น เวกเตอร์1 _E(v) แต่ละตัวจึง เป็นเวกเตอร์ขนาด 1 x mโดยที่องค์ประกอบeมีค่าเป็น 1 ถ้าขอบeอยู่ติดกับvและมีค่าเป็น 0 ถ้าไม่อยู่ ติดกับ v เมทริกซ์เหตุการณ์ของกราฟ ซึ่งแทนด้วยA _Gเป็น เมทริกซ์ขนาด n x mโดยที่แต่ละแถว v คือเวกเตอร์เหตุการณ์1 _E(V)กล่าวอีกนัยหนึ่ง องค์ประกอบv , e แต่ละตัว ในเมทริกซ์จะมีค่าเป็น 1 ถ้าโหนดvอยู่ติดกับขอบeและมีค่าเป็น 0 ถ้าไม่ อยู่ติดกับ v

ด้านล่างนี้คือตัวอย่างเมทริกซ์เหตุการณ์สามแบบ ได้แก่กราฟสามเหลี่ยม (วงจรที่มีความยาว 3) กราฟสี่เหลี่ยม (วงจรที่มีความยาว 4) และกราฟสมบูรณ์บน 4 จุดยอด

${\displaystyle {\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\end{pmatrix}}~,~{\begin{pmatrix}1&1&0&0\\0&1&1&0\\0&0&1&1\\1&0&0&1\\\end{pmatrix}}~,~{\begin{pmatrix}1&1&0&0&1&0\\0&1&1&0&0&1\\0&0&1&1&1&0\\1&0&0&1&0&1\\\end{pmatrix}}}$

สำหรับเซตย่อยFของขอบ ทุกเซต ผลคูณดอท1 _E(v) · 1 _F แสดงถึงจำนวนขอบในFที่อยู่ติดกับvดังนั้น ข้อความต่อไปนี้จึงเทียบเท่ากัน:

• เซตย่อยFของขอบแสดงถึงการจับคู่ในG;
• สำหรับทุกโหนดvในV : 1 _E(v) · 1 _F ≤ 1
• A _G · 1 _F ≤ 1 _V .

จำนวนสมาชิกของเซตFของขอบคือผลคูณดอท1 _E · 1 _F ดังนั้นการจับคู่ที่มีจำนวนสมาชิกสูงสุดในGจึงกำหนดโดย_{โปรแกรม}เชิงเส้นจำนวนเต็ม ต่อไปนี้ :

เพิ่มค่า 1 _E · xให้สูงสุด

ขึ้นอยู่กับ: xใน {0,1} ^ม.

__________ A _G · x ≤ 1 _V .

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

เพิ่มค่า 1 _E · xให้สูงสุด

ขึ้นอยู่กับ: x ≥ 0 _E

__________ A _G · x ≤ 1 _V .

นี่คือโปรแกรมเชิงเส้นมีข้อจำกัด "อย่างน้อย 0" จำนวน m ข้อ และข้อจำกัด "น้อยกว่า 1" จำนวนn ข้อ เซตของคำตอบที่เป็นไปได้คือ รูปหลายเหลี่ยมนูนแต่ละจุดในรูปหลายเหลี่ยมนี้คือการจับคู่แบบเศษส่วนตัวอย่างเช่น ในกราฟรูปสามเหลี่ยมมีขอบ 3 ขอบ และโปรแกรมเชิงเส้นที่สอดคล้องกันมีข้อจำกัด 6 ข้อดังต่อไปนี้:

เพิ่มค่าสูงสุดของ x ₁ +x ₂ +x ₃

ภายใต้เงื่อนไข: x _{1 ≥0} , x ₂ ≥0, x ₃ ≥0

__________ x ₁ +x ₂ ≤1 , x ₂ +x ₃ ≤1, x ₃ +x ₁ ≤1.

ชุดอสมการนี้แสดงถึงรูปทรงหลายเหลี่ยมในR ³ ซึ่ง เป็น ปริภูมิยุคลิดสามมิติ

โพลีโทปมีมุมห้ามุม ( จุดสุดขั้ว ) เหล่านี้คือจุดที่บรรลุความเท่าเทียมกันใน 3 จาก 6 อสมการที่กำหนด มุมเหล่านั้นคือ (0,0,0), (1,0,0), (0,1,0), (0,0,1) และ (1/2,1/2,1/2) ^{[ 2 ]}มุมแรก (0,0,0) แสดงถึงการจับคู่ที่ไม่สำคัญ (ว่างเปล่า) มุมสามมุมถัดไป (1,0,0), (0,1,0), (0,0,1) แสดงถึงการจับคู่สามคู่ที่มีขนาด 1 มุมที่ห้า (1/2,1/2,1/2) ไม่ได้แสดงถึงการจับคู่ แต่แสดงถึงการจับคู่แบบเศษส่วนซึ่งแต่ละขอบเป็น "เข้าครึ่งหนึ่ง ออกครึ่งหนึ่ง" โปรดทราบว่านี่คือการจับคู่แบบเศษส่วนที่ใหญ่ที่สุดในกราฟนี้ น้ำหนักของมันคือ 3/2 ตรงกันข้ามกับการจับคู่แบบจำนวนเต็มสามคู่ที่มีขนาดเพียง 1

อีกตัวอย่างหนึ่ง ในวงจร 4 วง มีขอบ 4 เส้น LP ที่เกี่ยวข้องมีข้อจำกัด 4+4=8 ข้อ FMP เป็นโพลีโทปนูนในR⁴ มุมของโพลีโทปนี้คือ (0,0,0,0), (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1), (1,0,1,0), (0,1,0,1) มุมสองมุมสุดท้ายแสดงถึง ^การจับคู่ขนาด 2 ซึ่งเป็นการจับคู่สูงสุด โปรดสังเกตว่าในกรณีนี้ มุมทั้งหมดมีพิกัดเป็นจำนวนเต็ม

โพลีโทปการจับคู่แบบอินทิกรัล (โดยทั่วไปเรียกว่าโพลีโทปการจับคู่ ) ของกราฟGซึ่งเขียนแทนด้วย MP( G ) คือโพลีโทปที่มีมุมเป็นเวกเตอร์เหตุการณ์ของการจับคู่แบบอินทิกรัลในG

MP( G ) จะถูกบรรจุอยู่ใน FMP( G ) เสมอ ในตัวอย่างข้างต้น:

• จุด MP ของกราฟรูปสามเหลี่ยมนั้นอยู่ภายในจุด FMP ของมันอย่างเคร่งครัด เนื่องจากจุด MP นั้นไม่มีมุมที่ไม่ใช่จำนวนเต็ม (1/2, 1/2, 1/2)
• จุด MP ของกราฟ 4 ไซเคิลนั้นเหมือนกับจุด FMP เนื่องจากมุมทั้งหมดของจุด FMP เป็นจำนวนเต็ม

ตัวอย่างข้างต้นเป็นกรณีพิเศษของทฤษฎีบททั่วไปต่อไปนี้: ^{[ 1 ] : 274}

G เป็นกราฟสองส่วน ก็ต่อเมื่อ MP( G ) = FMP( G ) ก็ต่อเมื่อมุมทั้งหมดของ FMP( G ) มีพิกัดเป็นจำนวนเต็มเท่านั้น

ทฤษฎีบทนี้สามารถพิสูจน์ได้หลายวิธี

เมื่อGเป็นเมทริกซ์สองส่วน เมทริกซ์เหตุการณ์A _Gจะเป็น เมทริกซ์เอกรูปสมบูรณ์ ( totally unimodular ) กล่าวคือ เมทริกซ์ย่อยจัตุรัสทุกเมทริกซ์จะมีดีเทอร์มิแนนต์เป็น 0, +1 หรือ −1 การพิสูจน์ทำได้โดยการอุปมานบนkซึ่งเป็นขนาดของเมทริกซ์ย่อย (ที่เราใช้สัญลักษณ์K แทน ) ฐานk  = 1 มาจากนิยามของA _Gกล่าวคือ ทุกองค์ประกอบในเมทริกซ์ย่อยนี้มีค่าเป็น 0 หรือ 1 สำหรับk > 1 จะมีหลายกรณี:

• ถ้าKมีคอลัมน์ที่ประกอบด้วยเลขศูนย์ทั้งหมด แสดงว่า det K = 0
• ถ้าKมีคอลัมน์ที่มีเลข 1 เพียงตัวเดียว ดีเทอร์มิแนนต์ของKสามารถขยายรอบคอลัมน์นี้ได้ และจะเท่ากับ +1 หรือ -1 คูณกับดีเทอร์มิแนนต์ของเมทริกซ์ขนาด ( k  − 1) x ( k  − 1) ซึ่งตามสมมติฐานการอุปมานจะมีค่าเป็น 0 หรือ +1 หรือ −1
• มิฉะนั้น แต่ละคอลัมน์ในKจะมีเลข 1 สองตัว เนื่องจากกราฟเป็นกราฟสองส่วน แถวต่างๆ สามารถแบ่งออกเป็นสองเซตย่อยได้ โดยที่ในแต่ละคอลัมน์ เลข 1 ตัวหนึ่งอยู่ในเซตย่อยบน และเลข 1 อีกตัวหนึ่งอยู่ในเซตย่อยล่าง ซึ่งหมายความว่าผลรวมของเซตย่อยบนและผลรวมของเซตย่อยล่างมีค่าเท่ากับ1 _Eลบด้วยเวกเตอร์ของเลข 1 จำนวน | E | ตัว ซึ่งหมายความว่าแถวของKมีความสัมพันธ์เชิงเส้นต่อกัน ดังนั้น det  K  = 0

ตัวอย่างเช่น ในวัฏจักร 4 (ซึ่งเป็นวัฏจักรคู่) ค่า det  A _G = 1 ในทางตรงกันข้าม ในวัฏจักร 3 (ซึ่งไม่ใช่วัฏจักรคู่) ค่า det  A _G  = 2

แต่ละมุมของ FMP( G ) สอดคล้องกับชุดของอสมการเชิงเส้นอิสระm ชุดที่มีความเท่ากัน ดังนั้น ในการคำนวณพิกัดมุม เราต้องแก้ระบบสมการที่กำหนดโดยเมทริกซ์ย่อยจัตุรัสของ AGตามกฎของเครเมอร์_คำตอบคือจำนวนตรรกยะซึ่งตัวส่วนคือดีเทอร์มิแนนต์ของเมทริกซ์ย่อยนี้ ดีเทอร์มิแนนต์นี้ต้องเป็น +1 หรือ −1 ดังนั้นคำตอบจึงเป็นเวกเตอร์จำนวนเต็ม ดังนั้นพิกัดมุมทั้งหมดจึงเป็นจำนวนเต็ม

ด้วยข้อจำกัด "น้อยกว่าหนึ่ง" จำนวนn ข้อ พิกัดมุมจะเป็น 0 หรือ 1 เท่านั้น ดังนั้นแต่ละมุมจึงเป็นเวกเตอร์เหตุการณ์ของการจับคู่แบบอินทิกรัลใน Gดังนั้น FMP( G ) = MP( G )

ด้านของโพลีโทปคือเซตของจุดซึ่งสอดคล้องกับอสมการนิยามที่สำคัญของโพลีโทปที่มีความเท่าเทียมกัน ถ้าโพลีโทปมี มิติ dแล้ว ด้านของมันจะมีมิติ ( d − 1) สำหรับกราฟ G  ใดๆด้านของ MP( G ) จะกำหนดโดยอสมการต่อไปนี้: ^{[ 1 ] : 275–279}

• x ≥ 0 _E
• 1 _{E ( v )} · x ≤ 1 (โดยที่ v เป็นจุดยอดที่ไม่โดดเดี่ยว ซึ่งถ้าvมีเพื่อนบ้านเพียงจุดเดียวคือuแล้ว { u , v } จะเป็นส่วนประกอบที่เชื่อมต่อกันของ G และถ้าvมีเพื่อนบ้านสองจุดพอดี เพื่อนบ้านทั้งสองจุดนั้นจะไม่ติดกัน)
• 1 _{E ( S )} · x ≤ (| S | − 1)/2 (โดยที่Sครอบคลุม ซับกราฟ วิกฤตปัจจัย ที่เชื่อมต่อ 2 จุด )

โพลีโทปการจับคู่ที่สมบูรณ์แบบของกราฟGซึ่งแสดงด้วย PMP( G ) คือโพลีโทปที่มีมุมเป็นเวกเตอร์เหตุการณ์ของการจับคู่ที่สมบูรณ์แบบ จำนวนเต็ม ในG ^{[ 1 ] : 274} เห็นได้ชัดว่า PMP( G ) บรรจุอยู่ใน MP( G ) ในความเป็นจริง PMP(G) คือหน้าของ MP( G ) ที่กำหนดโดยความเท่าเทียมกัน:

1 _E · x = n /2.

Edmonds ^{[ 3 ]}พิสูจน์ว่าสำหรับกราฟ G ทุกกราฟ PMP(G) สามารถอธิบายได้ด้วยข้อจำกัดต่อไปนี้:

1 _E(v) · x = 1 สำหรับทุกvในV (-- มีเพียงขอบที่อยู่ติดกับv เพียงขอบเดียวเท่านั้น ที่อยู่ในการจับคู่)

1 _E(W) · x ≥ 1 สำหรับทุกเซตย่อยWของVที่ |W| เป็นจำนวนคี่ (-- อย่างน้อยหนึ่งขอบต้องเชื่อมต่อ W กับ V\W) ข้อจำกัดเหล่านี้เรียกว่าข้อจำกัดแบบตัดคี่ (odd cut constraints )

x ≥ 0 _E

การใช้ลักษณะเฉพาะนี้และเลมมาของ Farkasทำให้สามารถกำหนดลักษณะเฉพาะของกราฟที่มีการจับคู่ที่สมบูรณ์แบบได้ดี^{[ 4 ] : 206} โดยการแก้ปัญหาเชิงอัลกอริทึมบนเซตแบบนูนสามารถค้นหาการจับคู่ที่สมบูรณ์แบบที่มีน้ำหนักน้อยที่สุดได้^{[ 4 ] : 206--208}

• โพลีโทปที่จับคู่ได้อย่างเสถียร

• รูปทรงหลายเหลี่ยมที่เข้าคู่กัน โดย ไมเคิล โกเอมันส์
• รูปทรงหลายเหลี่ยมที่เข้ากันได้ โดย Jan Vondrak
• รูปทรงหลายเหลี่ยมที่เข้าคู่กัน โดย วินเซนต์ โจสต์