2014年A

第1题

求下图 $G$的色多项式 $P_k(G)$

解析如下：

对图做运算，如下图所示。

$f(G,k)=f(K_5,k)+3\times f(K_4,k)+f(K_3,k)$

$=k(k-1)(k-2)(k-3)(k-4)$

$+3k(k-1)(k-2)(k-3)$

$+k(k-1)(k-2)$

$=k^5-7k^4+18k^3-20k^2+8k$

令解：

对图做减运算，如下图所示。 注意括号运算，容易计算出错 单独的点是一个 $k$

$f(G,k)=[(k^{2}f(K_3,k)-kf(K_3,k))-kf(K_3,k))-((kf(K_3,k)-f(K_3,k))-f(K_3,k))]-[(kf(K_3,k)-f(K_3,k))-f(K_3,k))]$

$=[((k^3(k-1)(k-2)-k^2(k-1)(k-2))-k^2(k-1)(k-2))$

$-((k^2(k-1)(k-2)-k(k-1)(k-2))-k(k-1)(k-2))]$

$-[((k^2(k-1)(k-2)-k(k-1)(k-2))-k(k-1)(k-2))]$

$=k^5-7k^4+18k^3-20k^2+8k$

第2题

设 $G$是至少有三个面的平面图。证明若 $G$的对偶图 $G^{\ast }$是简单图，则 $G^{\ast }$中至少存在三个度数小于 $6$的点。

证明如下：

设 $V^{\ast },E^{\ast },R^{\ast }$分别表示对偶图 $G^{\ast }$的点边面， $G$的点边面分别用 $V,E,R$表示，故 $|V^{\ast }|=|R|,|E^{\ast }|=|E|,|R^{\ast }|=|V|$,由于 $G$至少有三个面，故 $|V^{\ast }|=|R|\ge 3$

由于 $G^{\ast }$是简单图， $G^{\ast }$中每个面的边界至少包含 $3$条边。

设 $G^{\ast }$中各面的度数之和为 ${\sum }_{r^{\ast }\in R^{\ast }}d(r^{\ast })=2|E^{\ast }|$

又由于每个面至少有 $3$条边， ${\sum }_{r^{\ast }\in R^{\ast }}d(r^{\ast })\ge 3|R^{\ast }|$

故 $2|E^{\ast }|\ge 3|R^{\ast }|$

由欧拉公式得到对偶图 $|V^{\ast }|-|E^{\ast }|+|R^{\ast }|=2$

代入 $2|R^{\ast }|\le \frac{2}{3}|E^{\ast }|$，可得 $|E^{\ast }|\le 3|V^{\ast }|-6$

故 ${\sum }_{v^{\ast }\in V^{\ast }}d(v^{\ast })=2|E^{\ast }|\le 2(3|V^{\ast }|-6)=6|V^{\ast }|-12$

故 ${\sum }_{v^{\ast }\in V^{\ast }}(6-d(v^{\ast }))\ge 12$

假设 $G^{\ast }$中至多有两个点的度数小于 $6$。

$G^{\ast }$是对偶图， 故$G^{\ast }$连通，又因$|V^{\ast }|\ge 3$，每个顶点至少有一个邻点，即 $d(v^{\ast })\ge 1$

对于度数小于 $6$的顶点， $6-d(v^{\ast })\le 5$；对于度数大于等于 $6$的顶点 $6-d(v^{\ast })\le 0$

故 ${\sum }_{v^{\ast }\in V^{\ast }}(6-d(v^{\ast }))\le 5+5=10$

与 ${\sum }_{v^{\ast }\in V^{\ast }}(6-d(v^{\ast }))\ge 12$矛盾

故 $G^{\ast }$中至少存在三个度数小于 $6$的点。

2018年

第1题

求下图 $G$的色多项式 $f(G,k)$，并求出其色数。

解析如下： 见2011年的引入

递推式公式： $f(P_K,k)=k\times f(P_{K-1},k)-f(P_{k-1},k)=(k-1)\times f(P_{K-1},k)$

$f(P_K,k)=k\times (k-1{)}^{K-1}$

故 $f(G,k)=k\times (k-1{)}^6=k^7-6k^6+15k^5-20k^4+15k^3-6k^2+k$

色数 $\chi (G)=2$（交替两种颜色，此处也可通过代入色多项式计算）

第2题

利用布尔运算，试求下图的所有极大独立集。

解析如下：

$\phi =(1\wedge 2)\vee (1\wedge 3)\vee (2\wedge 4)\vee (2\wedge 5)\vee (3\wedge 4)\vee (3\wedge 5)$

$\bar{\phi }=(\bar{1}\vee \bar{2})\wedge (\bar{1}\vee \bar{3})\wedge (\bar{2}\vee \bar{4})\wedge (\bar{2}\vee \bar{5})\wedge (\bar{3}\vee \bar{4})\wedge (\bar{3}\vee \bar{5})$

$=(\bar{1}\vee (\bar{2}\wedge \bar{3}))\wedge (\bar{2}\vee (\bar{4}\wedge \bar{5}))\wedge (\bar{3}\vee (\bar{4}\wedge \bar{5}))$

$=(\bar{1}\vee (\bar{2}\wedge \bar{3}))\wedge [(\bar{2}\wedge \bar{3})\vee (\bar{4}\wedge \bar{5})]$

$=(\bar{1}\wedge \bar{2}\wedge \bar{3})\vee (\bar{1}\wedge \bar{4}\wedge \bar{5})$ 消除第一项

$\vee (\bar{2}\wedge \bar{3})\vee (\bar{2}\wedge \bar{3}\wedge \bar{4}\wedge \bar{5})$ 消除第二项

$=(\bar{1}\wedge \bar{4}\wedge \bar{5})\vee (\bar{2}\wedge \bar{3})$

故极大独立集为 { v 2 , v 3 } , { v 1 , v 4 , v 5 } \{v_2,v_3\},\{v_1,v_4,v_5\} {v2​,v3​},{v1​,v4​,v5​}。 注意是两者取反得到的，不是直接取的，该题只是凑巧

第3题

求加权图 $(K_{5,5},\omega )$的权最大的完美匹配，其中

解析如下： 教材P157课后习题5.13 计算较繁琐

（1）取可行行标 $l$如下：

• $l(y_1)=l(y_2)=l(y_3)=l(y_4)=l(y_5)=0$；

• l ( x 1 ) = m a x { 9 , 8 , 5 , 3 , 2 } = 9 l(x_1)=max\{9,8,5,3,2\}=9 l(x1​)=max{9,8,5,3,2}=9；

• l ( x 2 ) = m a x { 6 , 7 , 8 , 6 , 9 } = 9 l(x_2)=max\{6,7,8,6,9\}=9 l(x2​)=max{6,7,8,6,9}=9；

• l ( x 3 ) = m a x { 5 , 8 , 1 , 4 , 7 } = 8 l(x_3)=max\{5,8,1,4,7\}=8 l(x3​)=max{5,8,1,4,7}=8；

• l ( x 4 ) = m a x { 7 , 7 , 0 , 3 , 6 } = 7 l(x_4)=max\{7,7,0,3,6\}=7 l(x4​)=max{7,7,0,3,6}=7；

• l ( x 5 ) = m a x { 9 , 8 , 6 , 4 , 5 } = 9 l(x_5)=max\{9,8,6,4,5\}=9 l(x5​)=max{9,8,6,4,5}=9

（2）取 $l$等子图标 $G_l$及初始匹配，执行匈牙利算法，匹配情况为 { x 1 y 1 , x 2 y 5 , x 3 y 2 } \{x_1y_1,x_2y_5,x_3y_2\} {x1​y1​,x2​y5​,x3​y2​}，这时， $x=x_4$，得 S = { x 1 , x 3 , x 4 } S=\{x_1,x_3,x_4\} S={x1​,x3​,x4​}， T = { y 1 , y 2 } T=\{y_1,y_2\} T={y1​,y2​}，$N_{G_l}(S)=T$。

（3）计算 $S$与 $V_2-T$的结果，得到 ${\alpha }_l$

• $l(x_1)+l(y_3)-w(x_1,y_3)=9+0-5=4$
• $l(x_1)+l(y_4)-w(x_1,y_4)=9+0-3=6$
• $l(x_1)+l(y_5)-w(x_1,y_5)=9+0-2=7$
• $l(x_3)+l(y_3)-w(x_3,y_3)=8+0-1=7$
• $l(x_3)+l(y_4)-w(x_3,y_4)=8+0-4=4$
• $l(x_3)+l(y_5)-w(x_3,y_5)=8+0-7=1$
• $l(x_4)+l(y_3)-w(x_4,y_3)=7+0-0=7$
• $l(x_4)+l(y_4)-w(x_4,y_4)=7+0-3=4$
• $l(x_4)+l(y_5)-w(x_4,y_5)=7+0-6=1$

则 α l = m i n { l ( x ) + l ( y ) − w ( x , y ) ∣ x ∈ S , y ∈ V 2 − T } = 1 \alpha_l=min\{l(x)+l(y)-w(x,y) | x \in S,y \in V_2 -T\}=1 αl​=min{l(x)+l(y)−w(x,y)∣x∈S,y∈V2​−T}=1，更新 $S$顶标 $l(x_1)=9-1=8$， $l(x_3)=8-1=7$， $l(x_4)=7-1=6$，更新 $T$顶标 $l(y_1)=0+1=1$，$l(y_2)=0+1=1$。

（4）重新执行匈牙利算法，匹配情况为 { x 1 y 1 , x 2 y 5 , x 3 y 2 } \{x_1y_1,x_2y_5,x_3y_2\} {x1​y1​,x2​y5​,x3​y2​}，这时 $x=x_4$，得 S = { x 1 , x 2 , x 3 , x 4 } S=\{x_1,x_2,x_3,x_4\} S={x1​,x2​,x3​,x4​}， T = { y 1 , y 2 , y 5 } T=\{y_1,y_2,y_5\} T={y1​,y2​,y5​}，$N_{G_l}(S)=T$。

（5）计算 $S$与 $V_2-T$的结果，得到 ${\alpha }_l$

• $l(x_1)+l(y_3)-w(x_1,y_3)=8+0-5=3$
• $l(x_1)+l(y_4)-w(x_1,y_4)=8+0-3=5$
• $l(x_2)+l(y_3)-w(x_2,y_3)=9+0-8=1$
• $l(x_2)+l(y_4)-w(x_2,y_4)=9+0-6=3$
• $l(x_3)+l(y_3)-w(x_3,y_3)=7+0-1=6$
• $l(x_3)+l(y_4)-w(x_3,y_4)=7+0-4=3$
• $l(x_4)+l(y_3)-w(x_4,y_3)=6+0-0=6$
• $l(x_4)+l(y_4)-w(x_4,y_4)=6+0-3=3$

则 α l = m i n { l ( x ) + l ( y ) − w ( x , y ) ∣ x ∈ S , y ∈ V 2 − T } = 1 \alpha_l=min\{l(x)+l(y)-w(x,y) | x \in S,y \in V_2 -T\}=1 αl​=min{l(x)+l(y)−w(x,y)∣x∈S,y∈V2​−T}=1，更新 $S$顶标 $l(x_1)=8-1=7$， $l(x_2)=9-1=8$， $l(x_3)=7-1=6$，$l(x_4)=6-1=5$，更新 $T$顶标 $l(y_1)=1+1=2$，$l(y_2)=1+1=2$，$l(y_5)=0+1=1$。

（6）重新执行匈牙利算法，匹配情况为 { x 1 y 1 , x 2 y 3 , x 3 y 2 . x 4 y 5 } \{x_1y_1,x_2y_3,x_3y_2.x_4y_5\} {x1​y1​,x2​y3​,x3​y2​.x4​y5​}，这时 $x=x_5$，得 S = { x 5 } S=\{x_5\} S={x5​}， T = { ϕ } T=\{ \phi \} T={ϕ}，$N_{G_l}(S)=T$。

（7）计算 $S$与 $V_2-T$的结果，得到 ${\alpha }_l$

• $l(x_5)+l(y_1)-w(x_5,y_1)=9+2-9=2$
• $l(x_5)+l(y_2)-w(x_5,y_2)=9+2-8=3$
• $l(x_5)+l(y_3)-w(x_5,y_3)=9+0-6=3$
• $l(x_5)+l(y_4)-w(x_5,y_4)=9+0-4=5$
• $l(x_5)+l(y_5)-w(x_5,y_5)=9+1-5=5$

则 α l = m i n { l ( x ) + l ( y ) − w ( x , y ) ∣ x ∈ S , y ∈ V 2 − T } = 2 \alpha_l=min\{l(x)+l(y)-w(x,y) | x \in S,y \in V_2 -T\}=2 αl​=min{l(x)+l(y)−w(x,y)∣x∈S,y∈V2​−T}=2，更新 $S$顶标 $l(x_1)=8-1=7$， $l(x_5)=9-2=7$，不更新 $T$顶标 。

（8）重新执行匈牙利算法，匹配情况为 { x 1 y 1 , x 2 y 3 , x 3 y 2 , x 4 y 5 } \{x_1y_1,x_2y_3,x_3y_2,x_4y_5\} {x1​y1​,x2​y3​,x3​y2​,x4​y5​}，这时 $x=x_5$，得 S = { x 1 , x 5 } S=\{x_1,x_5\} S={x1​,x5​}， T = { y 1 } T=\{ y_1 \} T={y1​}，$N_{G_l}(S)=T$。

（9）计算 $S$与 $V_2-T$的结果，得到 ${\alpha }_l$

• $l(x_1)+l(y_2)-w(x_1,y_2)=7+2-8=1$

• $l(x_1)+l(y_3)-w(x_1,y_3)=7+0-5=2$

• $l(x_1)+l(y_4)-w(x_1,y_4)=7+0-3=4$

• $l(x_1)+l(y_5)-w(x_1,y_5)=7+1-2=6$

• $l(x_5)+l(y_2)-w(x_5,y_2)=7+2-8=1$

• $l(x_5)+l(y_3)-w(x_5,y_3)=7+0-6=1$

• $l(x_5)+l(y_4)-w(x_5,y_4)=7+0-4=3$

• $l(x_5)+l(y_5)-w(x_5,y_5)=7+1-5=3$

则 α l = m i n { l ( x ) + l ( y ) − w ( x , y ) ∣ x ∈ S , y ∈ V 2 − T } = 1 \alpha_l=min\{l(x)+l(y)-w(x,y) | x \in S,y \in V_2 -T\}=1 αl​=min{l(x)+l(y)−w(x,y)∣x∈S,y∈V2​−T}=1，更新 $S$顶标 $l(x_1)=7-1=6$， $l(x_5)=7-1=6$，更新 $T$顶标 $l(y_1)=2+1=3$。

（10）重新执行匈牙利算法，匹配情况为 { x 1 y 1 , x 2 y 3 , x 3 y 3 , x 4 y 5 } \{x_1y_1,x_2y_3,x_3y_3,x_4y_5\} {x1​y1​,x2​y3​,x3​y3​,x4​y5​}，这时 $x=x_5$，得 S = { x 1 , x 2 , x 3 , x 4 , x 5 } S=\{x_1,x_2,x_3,x_4,x_5\} S={x1​,x2​,x3​,x4​,x5​}， T = { y 1 , y 2 , y 3 , y 5 } T=\{y_1,y_2,y_3,y_5\} T={y1​,y2​,y3​,y5​}，$N_{G_l}(S)=T$。

（11）计算 $S$与 $V_2-T$的结果，得到 ${\alpha }_l$

• $l(x_1)+l(y_4)-w(x_1,y_4)=6+0-3=3$
• $l(x_2)+l(y_4)-w(x_2,y_4)=8+0-6=2$
• $l(x_3)+l(y_4)-w(x_3,y_4)=6+0-4=2$
• $l(x_4)+l(y_4)-w(x_4,y_4)=5+0-3=2$
• $l(x_5)+l(y_4)-w(x_5,y_4)=6+0-4=2$

则 α l = m i n { l ( x ) + l ( y ) − w ( x , y ) ∣ x ∈ S , y ∈ V 2 − T } = 2 \alpha_l=min\{l(x)+l(y)-w(x,y) | x \in S,y \in V_2 -T\}=2 αl​=min{l(x)+l(y)−w(x,y)∣x∈S,y∈V2​−T}=2，更新 $S$顶标 $l(x_1)=6-2=4$， $l(x_2)=8-2=6$， $l(x_3)=6-2=4$， $l(x_4)=5-2=3$, $l(x_5)=6-2=4$，更新 $T$顶标 $l(y_1)=3+2=4$， $l(y_2)=2+2=4$， $l(y_3)=0+2=2$， $l(y_5)=1+2=3$。

（12）重新执行匈牙利算法，得到完美匹配，此匹配即 $K_{5,5}$的最优匹配，其总权为 $8+8+4+6+9=35$。

2021年

第1题

利用布尔运算求下图 $G$中的极大独立集。

解析如下：

$\phi =(1\wedge 2)\vee (1\wedge 4)\vee (1\wedge 5)\vee (2\wedge 3)\vee (2\wedge 5)\vee (3\wedge 4)\vee (3\wedge 5)\vee (4\wedge 5)$

$\bar{\phi }=(\bar{1}\vee \bar{2})\wedge (\bar{1}\vee \bar{4})\wedge (\bar{1}\vee \bar{5})\wedge (\bar{2}\vee \bar{3})\wedge (\bar{2}\vee \bar{5})\wedge (\bar{3}\vee \bar{4})\wedge (\bar{3}\vee \bar{5})\wedge (\bar{4}\vee \bar{5})$

$$=(\bar{1}\vee (\bar{2}\wedge \bar{4}\wedge \bar{5}))\wedge (\bar{3}\vee (\bar{2}\wedge \bar{4}\wedge \bar{5}))\wedge (\bar{5}\vee (\bar{2}\wedge \bar{4}))$$

$$=[(\bar{1}\wedge \bar{3})\vee (\bar{1}\wedge \bar{2}\wedge \bar{4}\wedge \bar{5})\vee (\bar{2}\wedge \bar{3}\wedge \bar{4}\wedge \bar{5})\vee (\bar{2}\wedge \bar{4}\wedge \bar{5})]$$ 消除第二项和第三项

$$\wedge [\bar{5}\vee (\bar{2}\wedge \bar{4})]$$

$=[(\bar{1}\wedge \bar{3})\vee (\bar{2}\wedge \bar{4}\wedge \bar{5})]\wedge [\bar{5}\vee (\bar{2}\wedge \bar{4})]$

$=(\bar{1}\wedge \bar{3}\wedge \bar{5})\vee (\bar{1}\wedge \bar{2}\wedge \bar{3}\wedge \bar{4})\vee (\bar{2}\wedge \bar{4}\wedge \bar{5})\vee (\bar{2}\wedge \bar{4}\wedge \bar{5})$ 消除最后一项

$=(\bar{1}\wedge \bar{3}\wedge \bar{5})\vee (\bar{1}\wedge \bar{2}\wedge \bar{3}\wedge \bar{4})\vee (\bar{2}\wedge \bar{4}\wedge \bar{5})$

故极大独立集为 { v 2 , v 4 } , { v 5 } , { v 1 , v 3 } \{v_2,v_4\},\{v_5\},\{v_1,v_3\} {v2​,v4​},{v5​},{v1​,v3​}。

第2题

设下图 $G$为具有二部划分 $(V_1,V_2)$的二部图，其中 V 1 = { x 1 , x 2 , x 3 , x 4 , x 5 , x 6 } V_1=\{x_1,x_2,x_3,x_4,x_5,x_6\} V1​={x1​,x2​,x3​,x4​,x5​,x6​}， V 2 = { y 1 , y 2 , y 3 , y 4 , y 5 , y 6 } V_2=\{y_1,y_2,y_3,y_4,y_5,y_6\} V2​={y1​,y2​,y3​,y4​,y5​,y6​}。给出初始匹配 M = { x 1 y 1 , x 2 , x 3 , x 4 , x 5 , x 6 } M=\{x_1y_1,x_2,x_3,x_4,x_5,x_6\} M={x1​y1​,x2​,x3​,x4​,x5​,x6​}，从该初始匹配开始，利用匈牙利算法求其最大匹配。要求写出求解过程。（图中虚实线均是该二部图的边）。

最终匹配 { x 1 y 3 , x 2 y 4 , x 3 y 1 , x 4 y 6 , x 5 y 2 , x 6 y 5 } \{x_1y_3,x_2y_4,x_3y_1,x_4y_6,x_5y_2,x_6y_5\} {x1​y3​,x2​y4​,x3​y1​,x4​y6​,x5​y2​,x6​y5​}，推导过程如下表所示。

、