s匹配

s匹配(s-matching)是匹配的推廣，設H=(E₁，E₂，…，E_m)為X={x₁，x₂，…，x_n}上的一個超圖，它的關聯矩陣為A=(a_ij)_n×m，n和m分別為H的階和度，給定一個向量s=(s₁，s₂，…，s_n)∈Nⁿ，即s_i(1≤i≤n)均為非負整數，H的一個s匹配就是指多面體Q(s)上的一個所有分量均為整數的向量y=(y₁，y₂，…，y_m)，其中，Q(s)={y|y∈R^m，y≥0，Ay^T≤s^T}，而y^T表示向量y的轉置。

基本介紹

• 中文名：s匹配
• 外文名：s-matching
• 所屬學科：數學
• 所屬問題：組合學(圖與超圖)
• 簡介：匹配的推廣

基本介紹

設為上的一個超圖，它的關聯矩陣為，n和m分別為H的階和度，給定一個向量，即均為非負整數，H的一個s匹配就是指多面體Q(s)上的一個所有分量均為整數的向量，其中，，而y表示向量y的轉置，當時，即，y的分量只能取0或1，也就是說，任何一個節點至多包含在一條相應y的分量為1的邊中，所有相應1_n匹配y的分量為1的邊的集合就是H的一個匹配，對應超圖的每一條邊E_j給定一個整數，稱d_j為邊E_j的權，記，H上s匹配的最大權定義為

相關介紹

對於向量，H的一個d橫截是指多面體P(d)上的一個分量為整數的向量，其中，，而A*是H的對偶超圖的關聯矩陣，在H的每一個節點x_i處給定一個整數，稱c_i為節點x_i的費用，設，H的d橫截的最小費用定義為

特別地，

是H的匹配數，

是H的橫截數，一個超圖H，若對任何均有

則稱H為門傑超圖，任何一個平衡超圖都是門傑超圖；但反之不然，一個超圖H稱為整極超圖，若滿足如下三個等價條件之一：

1.多面體上的所有極點都是整向量，即所有分量皆為整數；

2.對任何皆為整數；

3.對任何，均有

由於門傑超圖總滿足條件3，所以它是整極的；但是，反之不然。