ในทฤษฎีกราฟการจับคู่ในไฮเปอร์กราฟคือเซตของไฮเปอร์เอดจ์ซึ่งไฮเปอร์เอดจ์สองอันใดๆ ก็ตามจะไม่ทับซ้อนกันถือเป็นการขยายแนวคิดของการจับคู่ในกราฟ^{[ 1 ] : 466–470 [ 2 ]}

โปรดจำไว้ว่าไฮเปอร์กราฟHคือคู่( V , E )โดยที่VคือเซตของจุดยอดและEคือเซตย่อยของVที่เรียกว่าไฮเปอร์เอดจ์แต่ละไฮเปอร์เอดจ์อาจประกอบด้วยจุดยอดหนึ่งจุดหรือมากกว่านั้น

การจับคู่ในHคือเซตย่อยMของEโดยที่ไฮเปอร์เอดจ์e ₁และe ₂ สองเส้น ในMจะมีจุดตัดว่างเปล่า (ไม่มีจุดยอดร่วมกัน)

จำนวนการจับคู่ของไฮเปอร์กราฟHคือขนาดที่ใหญ่ที่สุดของการจับคู่ในHมักจะแสดงด้วยν( H ) ^{[ 1 ]} : ^{466 [ 3 ]}

ยกตัวอย่างเช่น ให้Vเป็นเซต{1,2,3,4,5,6,7}พิจารณาไฮเปอร์กราฟแบบ 3-ยูนิฟอร์มบนV (ไฮเปอร์กราฟที่แต่ละไฮเปอร์เอดจ์มีจุดยอด 3 จุดพอดี) ให้Hเป็นไฮเปอร์กราฟแบบ 3-ยูนิฟอร์มที่มีไฮเปอร์เอดจ์ 4 เส้น:

{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} }

จากนั้นHยอมรับการจับคู่ที่มีขนาด 2 หลายแบบ ตัวอย่างเช่น:

{ {1,2,3}, {4,5,6} }

{ {1,4,5}, {2,3,6} }

อย่างไรก็ตาม ในกลุ่มย่อยใดๆ ที่มีไฮเปอร์เอดจ์ 3 เส้น อย่างน้อยสองเส้นจะตัดกัน ดังนั้นจึงไม่มีการจับคู่ที่มีขนาด 3 ดังนั้น จำนวนการจับคู่ของHจึงเป็น 2

ไฮเปอร์กราฟH = ( V , E )เรียกว่า ไฮเปอร์ กราฟตัดกันถ้าไฮเปอร์เอดจ์สองเส้นใดๆ ในEมีจุดยอดร่วมกัน ไฮเปอร์กราฟHจะตัดกันก็ต่อเมื่อไม่มีการจับคู่กับไฮเปอร์เอดจ์สองเส้นขึ้นไป ก็ต่อเมื่อν( H ) = 1 ^{[ 4 ]}

กราฟที่ไม่มีวงวนในตัวเองก็คือไฮเปอร์กราฟแบบ 2-ยูนิฟอร์ม: แต่ละขอบสามารถพิจารณาได้ว่าเป็นเซตของจุดยอดสองจุดที่เชื่อมต่อกัน ตัวอย่างเช่น ไฮเปอร์กราฟแบบ 2-ยูนิฟอร์มนี้แสดงถึงกราฟที่มีจุดยอด 4 จุด{1,2,3,4}และขอบ 3 เส้น:

{ {1,3}, {1,4}, {2,4} }

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

การจับคู่แบบเศษส่วนในไฮเปอร์กราฟ คือ ฟังก์ชันที่กำหนดค่าเศษส่วนในช่วง[0,1]ให้กับไฮเปอร์เอดจ์แต่ละตัว โดยที่สำหรับทุกจุดยอดvในVผลรวมของเศษส่วนของไฮเปอร์เอดจ์ที่ประกอบด้วยvจะมีค่าไม่เกิน 1 การจับคู่แบบเศษส่วนเป็นกรณีพิเศษของการจับคู่แบบเศษส่วน โดยที่เศษส่วนทั้งหมดมีค่าเป็น 0 หรือ 1 ขนาดของการจับคู่แบบเศษส่วนคือผลรวมของเศษส่วนของไฮเปอร์เอดจ์ทั้งหมด

จำนวนการจับคู่เศษส่วนของไฮเปอร์กราฟHคือขนาดที่ใหญ่ที่สุดของการจับคู่เศษส่วนใน^Hมักจะแสดงด้วยν *( H ) [ ^{3 ]}

เนื่องจากการจับคู่เป็นกรณีพิเศษของการจับคู่เศษส่วน ดังนั้นสำหรับทุกไฮเปอร์กราฟH :

จำนวนการจับคู่ ( H ) ≤ จำนวนการจับคู่เศษส่วน ( H )

หลักการนี้เขียนในเชิงสัญลักษณ์ได้ดังนี้:

${\displaystyle \nu (H)\leq \nu ^{*}(H)}$

โดยทั่วไป จำนวนการจับคู่เศษส่วนอาจมีขนาดใหญ่กว่าจำนวนการจับคู่ ทฤษฎีบทของZoltán Füredi ^{[ 4 ]}ให้ขอบเขตบนของอัตราส่วนจำนวนการจับคู่เศษส่วน( H ) /จำนวนการจับคู่ ( H ) ดังนี้:

• ถ้าไฮเปอร์เอดจ์แต่ละอันในHมีจุดยอดไม่เกินrจุดแล้ว

${\displaystyle {\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1+{\frac {1}{r}}.}$

โดยเฉพาะอย่างยิ่งในกราฟแบบง่าย: ^{[ 5 ]}

${\displaystyle {\frac {\nu ^{*}(H)}{\nu (H)}}\leq {\frac {3}{2}}.}$

• อสมการนี้ชัดเจน: ให้H _rเป็นระนาบเชิงโปรเจกทีฟจำกัดแบบเอกรูปrแล้ว ν ( H _r ) = 1เนื่องจากไฮเปอร์เอจสองเส้นทุกคู่ตัดกัน และν *( H _r ) = r – 1 + ⁠1/รโดยการจับคู่เศษส่วนที่กำหนดน้ำหนักเป็น1/รไป ยังไฮเปอร์เอดจ์แต่ละอัน (เป็นการจับคู่เนื่องจากแต่ละจุดยอดอยู่ใน ไฮเปอร์เอดจ์ r อันและขนาดของมันคือ r – 1 + ⁠1/รเนื่องจากมี ไฮเปอร์เอด จ์r² ^– r + 1 อัน ดังนั้นอัตราส่วนจึงเท่ากับ r – 1 + ⁠1/ร⁠ .
• ถ้าrเป็นค่าที่ทำให้ระนาบเชิงโปรเจกทีฟจำกัดแบบ เอกรูป rไม่มีอยู่จริง (ตัวอย่างเช่นr = 7 ) แล้วจะมีอสมการที่เข้มงวดกว่านั้นเกิดขึ้น:

${\displaystyle {\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.}$

• ถ้าHเป็น เมทริกซ์ r -partite (จุดยอดถูกแบ่งออกเป็นrส่วน และไฮเปอร์เอดจ์แต่ละอันมีจุดยอดจากแต่ละส่วน) แล้ว:

${\displaystyle {\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.}$

โดยเฉพาะอย่างยิ่งในกราฟสองส่วนν *( H ) = ν ( H )ซึ่งได้รับการพิสูจน์โดยAndrás Gyárfás ^{[ 4 ]}

• อสมการนี้ชัดเจน: ให้H _r-เป็นระนาบเชิงโปรเจกทีฟที่ถูกตัดทอนที่มีอันดับr – 1แล้วν ( H _{r -} ) = 1เนื่องจากไฮเปอร์เอจสองเส้นทุกคู่ตัดกัน และν *( H _{r -} ) = r – 1โดยการจับคู่เศษส่วนที่กำหนดน้ำหนักเป็น⁠1/รไปยังไฮเปอร์เอดจ์แต่ละอัน (มี ไฮเปอร์เอดจ์จำนวน r ² – rอัน)

การจับคู่Mเรียกว่าสมบูรณ์แบบหากทุกจุดยอดvในVอยู่ใน ไฮเปอร์เอดจ์ เพียงหนึ่งเดียวของM เท่านั้น นี่คือการขยายแนวคิดเรื่องการจับคู่สมบูรณ์แบบในกราฟ อย่างเป็นธรรมชาติ

การจับคู่เศษส่วนMเรียกว่าสมบูรณ์แบบถ้าสำหรับทุกจุดยอดvในVผลรวมของเศษส่วนของไฮเปอร์เอดจ์ในMที่ประกอบด้วยvมีค่าเท่ากับ 1 พอดี

พิจารณาไฮเปอร์กราฟHซึ่งแต่ละไฮเปอร์เอดจ์มีจุดยอดไม่เกินnจุด ถ้าHยอมรับการจับคู่เศษส่วนที่สมบูรณ์แบบ จำนวนการจับคู่เศษส่วนของ H จะมีค่าอย่างน้อย| V | ⁄ nถ้าแต่ละไฮเปอร์เอดจ์ในHมี จุดยอด n จุดพอดี จำนวนการจับคู่เศษส่วนของ H จะมีค่าเท่ากับ| V | ⁄ nพอดี^{[ 6 ] : sec.2} นี่เป็นการสรุปทั่วไปของข้อเท็จจริงที่ว่า ในกราฟ ขนาดของการจับคู่ที่สมบูรณ์แบบคือ | V | ⁄ 2

กำหนดให้เซตของจุดยอดV เป็นกลุ่มย่อย EของVเรียกว่าสมดุลถ้าไฮเปอร์กราฟ( V , E )ยอมรับการจับคู่เศษส่วนที่สมบูรณ์แบบ

ตัวอย่างเช่น ถ้าV = {1,2,3,a,b,c}และE = { {1,a}, {2,a}, {1,b}, {2,b}, {3,c} }แล้วEจะสมดุล โดยมีการจับคู่เศษส่วนที่สมบูรณ์แบบ{ 1/2, 1/2, 1/2, 1/2, 1 }

มีเงื่อนไขเพียงพอหลายประการสำหรับการมีอยู่ของการจับคู่ที่สมบูรณ์แบบในไฮเปอร์กราฟ:

• ทฤษฎีบทแบบฮอลล์สำหรับไฮเปอร์กราฟ - นำเสนอเงื่อนไขที่เพียงพอในลักษณะเดียวกับทฤษฎีบทการแต่งงานของฮอลล์โดยอิงจากเซตของเพื่อนบ้าน
• การจับคู่ที่สมบูรณ์แบบในไฮเปอร์กราฟระดับสูง - นำเสนอเงื่อนไขที่เพียงพอซึ่งคล้ายคลึงกับทฤษฎีบทของ Dirac เกี่ยวกับวัฏจักรแฮมิลโทเนียนโดยอิงจากระดับของจุดยอด
• Keevashและ Mycroft ได้พัฒนาทฤษฎีทางเรขาคณิตสำหรับการจับคู่ไฮเปอร์กราฟ^{[ 7 ]}

เซตแฟมิลีEบนเซตพื้นฐานVเรียกว่าสมดุล (เมื่อเทียบกับV ) ถ้าไฮเปอร์กราฟH = ( V , E )ยอมรับการจับคู่เศษส่วนที่สมบูรณ์แบบ^{[ 6 ] : sec.2}

ตัวอย่างเช่น พิจารณาเซตของจุดยอดV = {1,2,3,a,b,c}และเซตของขอบE = {1-a, 2-a, 1-b, 2-b, 3-c} เซตEมีความสมดุล เนื่องจากมีการจับคู่เศษส่วนที่สมบูรณ์แบบด้วยน้ำหนัก{1/2, 1/2, 1/2, 1/2, 1}

ปัญหาการหาการจับคู่ที่มีจำนวนสมาชิกมากที่สุดในไฮเปอร์กราฟ ซึ่งก็คือการคำนวณค่า นั้นเป็นปัญหา NP-hard แม้แต่สำหรับไฮเปอร์กราฟแบบ 3-uniform (ดูการจับคู่แบบ 3 มิติ ) ซึ่งแตกต่างจากกรณีของกราฟแบบง่าย (2-uniform) ที่การคำนวณการจับคู่ที่มีจำนวนสมาชิกมากที่สุดสามารถทำได้ในเวลาพหุนาม ${\displaystyle \nu (H)}$

กลุ่มปกคลุมจุดยอด (vertex-cover) ในไฮเปอร์กราฟH = ( V , E )คือเซตย่อยTของVซึ่งทุกไฮเปอร์เอดจ์ในEจะมีจุดยอดอย่างน้อยหนึ่งจุดจากT (เรียกอีกอย่างว่า เซตตัดขวาง (transversal set) หรือเซตกระทบ (hitting set ) และเทียบเท่ากับกลุ่มปกคลุมเซต (set cover )) มันเป็นการขยายแนวคิดของกลุ่มปกคลุมจุดยอดในกราฟ

จำนวนการปกคลุมจุดยอดของไฮเปอร์กราฟHคือขนาดที่เล็กที่สุดของการปกคลุมจุดยอดในHมักจะแสดงด้วยτ ( H ) , ^{[ 1 ] : 466} สำหรับทรานส์เวอร์ซัล

การ ครอบคลุม จุดยอดแบบเศษส่วน (Fractional Vertex-cover)คือฟังก์ชันที่กำหนดค่าน้ำหนักให้กับแต่ละจุดยอดในVโดยที่สำหรับทุกไฮเปอร์เอจeในEผลรวมของเศษส่วนของจุดยอดในeจะต้องมีค่าอย่างน้อย 1 การครอบคลุมจุดยอด (Vertex cover) เป็นกรณีพิเศษของการครอบคลุมจุดยอดแบบเศษส่วน ซึ่งค่าน้ำหนักทั้งหมดจะเป็น 0 หรือ 1 ขนาดของการครอบคลุมจุดยอดแบบเศษส่วนคือผลรวมของเศษส่วนของจุดยอดทั้งหมด

จำนวนการปกคลุมจุดยอดแบบเศษส่วนของไฮเปอร์กราฟHคือขนาดที่เล็กที่สุดของการปกคลุมจุดยอดแบบเศษส่วนในHโดยทั่วไปมักใช้สัญลักษณ์τ *( H )แทน

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

fractional-vertex-cover-number ( H ) ≤ vertex-cover-number ( H )

ทฤษฎีบทคู่ของการเขียนโปรแกรมเชิงเส้นบ่งชี้ว่า สำหรับไฮเปอร์กราฟH ทุกตัว :

fractional-matching-number ( H ) = fractional-vertex-cover-number( H ).

ดังนั้นสำหรับไฮเปอร์กราฟH ทุกตัว : ^{[ 4 ]}

${\displaystyle \nu (H)\leq \nu ^{*}(H)=\tau ^{*}(H)\leq \tau (H)}$

ถ้าขนาดของแต่ละไฮเปอร์เอดจ์ในHมีค่าไม่เกินrแล้ว การรวมกันของไฮเปอร์เอดจ์ทั้งหมดในการจับคู่สูงสุดจะเป็นการครอบคลุมจุดยอด (ถ้ามีไฮเปอร์เอดจ์ที่ยังไม่ถูกครอบคลุม เราสามารถเพิ่มเข้าไปในการจับคู่ได้) ดังนั้น:

${\displaystyle \tau (H)\leq r\cdot \nu (H).}$

อสมการนี้มีความแน่นหนา: ความเท่าเทียมกันเกิดขึ้นได้ เช่น เมื่อV ประกอบด้วย จุดยอด r ⋅ ν ( H ) + r – 1จุด และEประกอบด้วยเซตย่อยทั้งหมดของ จุดยอด rจุด

อย่างไรก็ตาม โดยทั่วไปτ *( H ) < r ⋅ ν ( H )เนื่องจากν *( H ) < r ⋅ ν ( H ) ; ดูการจับคู่เศษส่วนด้านบน

ข้อสันนิษฐานของไรเซอร์กล่าวว่า ใน ไฮเปอร์กราฟ r -partite r -uniform ทุกตัว:

${\displaystyle \tau (H)\leq (r-1)\nu (H).}$

มีการพิสูจน์กรณีพิเศษบางกรณีของข้อสันนิษฐานนี้แล้ว โปรดดูข้อสันนิษฐานของไรเซอร์

ไฮเปอร์กราฟมีคุณสมบัติ Kőnigถ้าจำนวนการจับคู่สูงสุดเท่ากับจำนวนการครอบคลุมจุดยอดต่ำสุด กล่าวคือ ถ้าν ( H ) = τ ( H )ทฤษฎีบทKőnig-Egerváry แสดงให้เห็นว่า กราฟสองส่วนทุก กราฟ มีคุณสมบัติ Kőnig ในการขยายทฤษฎีบทนี้ไปยังไฮเปอร์กราฟ เราจำเป็นต้องขยายแนวคิดของความเป็นกราฟสองส่วนไปยังไฮเปอร์กราฟ^{[ 1 ] : 468}

โดยทั่วไปแล้ว การสรุปแบบธรรมชาติมีดังนี้ ไฮเปอร์กราฟเรียกว่าสามารถระบายสีได้ 2 สีถ้าจุดยอดของมันสามารถระบายสีได้ 2 สี โดยที่ไฮเปอร์เอดจ์ทุกเส้น (ที่มีขนาดอย่างน้อย 2) จะต้องมีจุดยอดอย่างน้อยหนึ่งจุดในแต่ละสี คำศัพท์ทางเลือกคือคุณสมบัติ Bกราฟแบบง่ายเรียกว่ากราฟสองส่วนก็ต่อเมื่อมันสามารถระบายสีได้ 2 สี อย่างไรก็ตาม มีไฮเปอร์กราฟที่สามารถระบายสีได้ 2 สีโดยไม่มีคุณสมบัติของ Kőnig ตัวอย่างเช่น พิจารณาไฮเปอร์กราฟที่มีV = {1,2,3,4}และสามจุดE = { {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }มันสามารถระบายสีได้ 2 สี ตัวอย่างเช่น เราสามารถระบายสี{1,2}เป็นสีน้ำเงินและ{3,4}เป็นสีขาว อย่างไรก็ตาม จำนวนการจับคู่คือ 1 และจำนวนการครอบคลุมจุดยอดคือ 2

การสรุปทั่วไปที่แข็งแกร่งกว่ามีดังนี้ กำหนดให้ไฮเปอร์กราฟH = ( V , E )และเซตย่อยV'ของVการจำกัดของHไปยังV'คือไฮเปอร์กราฟที่มีจุดยอดเป็นVและสำหรับทุกไฮเปอร์เอจeในEที่ตัดกับV'จะมีไฮเปอร์เอจe'ที่เป็นจุดตัดของeและV'ไฮเปอร์กราฟเรียกว่าสมดุลหากการจำกัดทั้งหมดของมันสามารถระบายสีได้ 2 สีโดยพื้นฐานซึ่งหมายความว่าเราไม่สนใจไฮเปอร์เอจเดี่ยวในการจำกัด^{[ 8 ]}กราฟแบบง่ายเป็นกราฟสองส่วนก็ต่อเมื่อเป็นกราฟสมดุล

กราฟแบบง่ายจะเป็นกราฟสองส่วนก็ต่อเมื่อไม่มีวงจรที่มีความยาวเป็นเลขคี่ ในทำนองเดียวกัน ไฮเปอร์กราฟจะเป็นกราฟสมดุลก็ต่อเมื่อไม่มีวงจร ที่มีความยาวเป็นเลขคี่ วงจรที่มีความยาวkในไฮเปอร์กราฟคือลำดับสลับ( v ₁ , e ₁ , v ₂ , e ₂ , …, v _k , e _k , v _{k +1} = v ₁ )โดยที่v _iเป็นจุดยอดที่แตกต่างกัน และe _iเป็นไฮเปอร์เอดจ์ที่แตกต่างกัน และแต่ละไฮเปอร์เอดจ์ประกอบด้วยจุดยอดทางซ้ายและจุดยอดทางขวา วงจรจะเรียกว่าไม่สมดุลหากแต่ละไฮเปอร์เอดจ์ไม่มีจุดยอดอื่นในวงจรClaude Bergeพิสูจน์ว่าไฮเปอร์กราฟจะสมดุลก็ต่อเมื่อไม่มีวงจรที่ไม่สมดุลที่มีความยาวเป็นเลขคี่ ไฮเปอร์กราฟสมดุลทุกตัวมีคุณสมบัติของ Kőnig ^{[ 9 ] [ 1 ] : 468–470}

ต่อไปนี้เทียบเท่ากัน: ^{[ 1 ] : 470–471}

• ไฮเปอร์กราฟย่อยทุกอันของH (กล่าวคือ ไฮเปอร์กราฟที่ได้มาจากHโดยการลบไฮเปอร์เอดจ์บางส่วน) ล้วนมีคุณสมบัติของ Kőnig
• ไฮเปอร์กราฟย่อยทุกอันของHมีคุณสมบัติที่ว่าดีกรีสูงสุดของไฮเปอร์กราฟนั้นเท่ากับจำนวนการระบายสีขอบ ต่ำสุดของไฮเปอร์กราฟนั้น
• Hมีคุณสมบัติ HellyและกราฟจุดตัดของH (กราฟเชิงเดี่ยวที่จุดยอดคือEและสมาชิกสองตัวของEจะเชื่อมโยงกันก็ต่อเมื่อจุดตัดของสมาชิกทั้งสอง) เป็นกราฟสมบูรณ์

ปัญหาการจัดเรียงเซตเทียบเท่ากับการจับคู่ไฮเปอร์กราฟ

การจัดเรียง จุดยอดในกราฟ (แบบง่าย) คือเซตย่อยPของจุดยอดทั้งหมดในกราฟ โดยที่ไม่มีจุดยอดสองจุดใดในเซตPที่อยู่ติดกัน

ปัญหาของการค้นหาการบรรจุจุดยอดสูงสุดในกราฟเทียบเท่ากับปัญหาของการค้นหาการจับคู่สูงสุดในไฮเปอร์กราฟ: ^{[ 1 ] : 467}

• กำหนดให้ไฮเปอร์กราฟH = ( V , E )ให้นิยามกราฟจุดตัดInt( H )ว่าเป็นกราฟแบบง่ายที่มีจุดยอดเป็นEและมีขอบเป็นคู่( e ₁ , e ₂ )โดยที่e ₁ , e ₂มีจุดยอดร่วมกัน ดังนั้น การจับคู่ทุกคู่ในHเป็นการจัดเรียงจุดยอดในInt( H )และในทางกลับกัน
• กำหนดกราฟG = ( V' , E' )นิยามไฮเปอร์กราฟรูปดาวSt( G )ว่าเป็นไฮเปอร์กราฟที่มีจุดยอดเป็นE'และมีไฮเปอร์เอจเป็นรูปดาวของจุดยอดในG (กล่าวคือ สำหรับแต่ละจุดยอดv'ในV'จะมีไฮเปอร์เอจในSt( G )ที่ประกอบด้วยขอบทั้งหมดในE'ที่อยู่ติดกับv' ) ดังนั้น การจัดเรียงจุดยอดทุกแบบในGจะเป็นการจับคู่ในSt( G )และในทางกลับกัน
• อีกทางเลือกหนึ่ง กำหนดกราฟG = ( V' , E' )และนิยามไฮเปอร์กราฟคลิกCl( G )ว่าเป็นไฮเปอร์กราฟที่มีจุดยอดเป็นคลิกของGและสำหรับแต่ละจุดยอดv'ในV'จะมีไฮเปอร์เอดจ์ในCl( G )ที่ประกอบด้วยคลิกทั้งหมดในGที่มีv' อยู่ นอกจากนี้ การจัดเรียงจุดยอดทุกแบบในGก็เป็นการจับคู่ในCl( G )และในทางกลับกัน โปรดทราบว่าCl( G )ไม่สามารถสร้างจากG ได้ ในเวลาพหุนามดังนั้นจึงไม่สามารถใช้เป็นวิธีการลดรูปเพื่อพิสูจน์ความยากแบบ NP ได้ แต่ก็มีประโยชน์ในเชิงทฤษฎีอยู่บ้าง

• การจับคู่แบบ 3 มิติ – กรณีพิเศษของการจับคู่ไฮเปอร์กราฟกับไฮเปอร์กราฟแบบ 3 มิติสม่ำเสมอ
• การปกคลุมจุดยอดในไฮเปอร์กราฟ
• ไฮเปอร์กราฟแบบสองส่วน
• การจับคู่สีรุ้งในไฮเปอร์กราฟ
• ไฮเปอร์กราฟช่วง D - ไฮเปอร์กราฟอนันต์ที่มีความสัมพันธ์บางอย่างระหว่างจำนวนการจับคู่และจำนวนการครอบคลุม
• ทฤษฎีบท Erdős–Ko–Radoเกี่ยวกับขอบที่ไม่ตัดกันเป็นคู่ในไฮเปอร์กราฟ