图的完美对集的计数问题的研究有重要的理论价值和现实意义^[1-3].此问题已经被证实是NP-困难问题.分类嵌套递推的方法是求解许多类图完美对集数的一种非常有效的方法^[4-10].本文构造了2类新的N_mn和3-nK_3，3，用分类嵌套递推的方法求出了图N_mn和3-nK_3，3不同完美对集的计数公式.

定义1   如果图G有1-正则生成子图P，那么就称这个生成子图P为图G的完美对集.

定义2   设图G是有完美对集的图，如果图G的两个完美对集P₁和P₂中有一条边不同，那么就称P₁和P₂是G的两个不同的完美对集.

定义3   设长度为2m的圈C_mⁱ的顶点集合为V(C_mⁱ)={u_i1，u_i2，…，u_im，v_i1，v_i2，…，v_im}(i=1，2，…，n)，把圈C_mⁱ的顶点v_i1，v_i2，…，v_im与圈C_mⁱ⁺¹的顶点u_i+1，1，u_i+1，2，…，u_i+1，m(i=1，2，…，n－1)连接成圈v_i1u_i+1，2v_i3u_i+1，4v_i5…v_i，m－1u_i+1，mv_imu_i+1，m－1v_i，m－2…u_i+1，3v_i2u_i+1，1v_i1(i=1，2，…，n－1)，这样产生的图记为N_mn，见图 1.

定义4   设完全偶图K_3，3ⁱ的顶点集合为V(K_3，3ⁱ)={u_i1，u_i2，u_i3，v_i1，v_i2，v_i3}(i=1，2，…，n)，把圈K_3，3ⁱ的顶点v_i1，v_i2，v_i3分别与圈K_3，3ⁱ⁺¹的顶点u_i+1，1，u_i+1，2，u_i+1，3 (i=1，2，…，n－1)各连接一条边，这样产生的图记为3-nK_3，3，见图 2.

定理1   设图N_mn的完美对集数为δ(m，n)，则δ(n)=2ⁿ.

证   因为图N_mn的每个圈C_mⁱ:v_i1u_i2v_i3u_i4v_i5…v_i，m－1u_imv_imu_i，m－1v_i，m－2…u_i3v_i2u_i1v_i1恰有2个完美对集(i=1，2，…，n)，每个圈取定一个完美对集，就形成图N_mn的一个完美对集.因此，由乘法原理可知，图N_mn至少有2ⁿ个不同的完美对集.下面证明图N_mn只有2ⁿ个不同的完美对集.

设P是图N_mn的完美对集的集合，对于集合P中的任何一个完美匹配P_i，P_i一定要饱和顶点u₁₁.与顶点u₁₁关联的边只有2条，所以集合P可划分为2类:P₁，P₂.设u₁₁v₁₁∈P₁，u₁₁v₁₂∈P₂，则$ P_{1} \cap P_{2}=\emptyset, P=P_{1} \cup P_{2}$，故δ(m，n)=|P|=|P₁|+|P₂|.

因为u₁₁v₁₁∈P₁，所以当m是偶数时，边u₁₁v₁₁，u₁₂v₁₃，v₁₂u₁₃，u₁₄v₁₅，v₁₄u₁₅，…，u_1，m－2v_1，m－1，v_1，m－2u_1，m－1，u_1mv_1m都属于P₁; 当m是奇数时，边u₁₁v₁₁，u₁₂v₁₃，v₁₂u₁₃，u₁₄v₁₅，v₁₄u₁₅，…，u_1，m－1v_1m，v_1，m－1u_1m都属于P₁.由δ(m，n)的定义可知，|P₁|=δ(m，n－1).

因为u₁₁v₁₂∈P₂，所以当m是偶数时，边v₁₁u₁₂，u₁₃v₁₄，v₁₃u₁₄，u₁₅v₁₆，v₁₅u₁₆，…，u_1，m－2v_1，m，v_1，m－1u_1，m都属于P₂; 当m是奇数时，边v₁₁u₁₂，u₁₃v₁₄，v₁₃u₁₄，u₁₅v₁₆，v₁₅u₁₆，…，u_1，m－2v_1，m－1，v_1，m－2u_1，m－1，u_1mv_1m都属于P₂.由δ(m，n)的定义可知，|P₂|=δ(m，n－1).

因此，δ(m，n)=|P|=2δ(m，n－1)=…=2^n－1δ(m，1)=2ⁿ.

定理2   设图 3-nK_3，3的完美对集数为γ(n)，则γ(n)=6ⁿ.

证  图 3-nK_3，3存在完美对集是明显的.设图 3-nK_3，3的完美对集的集合为S，对于集合S中的任何一个完美匹配S_i，S_i一定要饱和顶点u₁₁.与顶点u₁₁关联的边有3条，所以集合S可划分为3类:S₁，S₂，S₃.设u₁₁v₁₁∈S₁，u₁₁v₁₂∈S₂，u₁₁v₁₃∈S₃，则S_i∩S_j=(1≤i < j≤3)，S=S₁∪S₂∪S₃.故γ(n)=|S|=|S₁|+|S₂|+|S₃|.

S₁划分为两类. S₁中含边u₁₁v₁₁，u₁₂v₁₂，u₁₃v₁₃的完美对集集合记为S₁¹; S₁中含边u₁₁v₁₁，u₁₂v₁₃，v₁₂u₁₃的完美对集集合记为S₁².由γ(n)的定义可知

因此，有

S₂划分为两类. S₂中含边u₁₁v₁₂，v₁₁u₁₂，u₁₃v₁₃的完美对集集合记为S₂¹; S₂中含边u₁₁v₁₂，v₁₁u₁₃，u₁₂v₁₃的完美对集集合记为S₂².由γ(n)的定义可知

因此，有

S₃划分为两类. S₃中含边u₁₁v₁₃，v₁₁u₁₂，u₁₃v₁₂的完美对集集合记为S₃¹; S₃中含边u₁₁v₁₃，v₁₁u₁₃，u₁₂v₁₂的完美对集集合记为S₃².由γ(n)的定义可知

因此，有

由(1)式和(2)，(3)式，得

由图 3知，γ(1)=6，故图 3－nK_3，3的完美对集数为γ(n)=6ⁿ