离散数学复习笔记

支配集：该图的除了支配集之外的点都与支配集相连，集合中的点将整个图支配了

极小支配集： V ∗ V^* V∗是支配集，其真子集不是

最小支配集：|V*|点数最小的支配集

支配数： γ 0 ( G ) = ∣ V ∗ ∣ \gamma_0(G)=|V^*| γ0​(G)=∣V∗∣最小支配集的点数

定理13.1：无向图G无孤立点,V1是极小支配集,则存在V2也是极小支配集,且V1∩V2= ∅ \varnothing ∅

独立集：集合中的点相互之间没有连线

极大独立集： V ∗ V^* V∗是独立集，其真母集不是

最大独立集：| V ∗ V^* V∗|最大的独立集

独立数： β 0 ( G ) = ∣ V ∗ ∣ \beta_0(G)=|V^*| β0​(G)=∣V∗∣最大独立集的点数

定理13.2：无向图G无孤立点， V ∗ V^* V∗是极大独立集，则 V ∗ V^* V∗也是极小支配集(逆命题不成立)

点覆盖：点集合与图中所有的边关联

极小点覆盖： V ∗ V^* V∗是点覆盖，其真子集不是

最小点覆盖: ∣ V ∗ ∣ |V^*| ∣V∗∣的顶点数最小

点覆盖数： α 0 ( G ) = ∣ V ∗ ∣ \alpha_0(G)=|V^*| α0​(G)=∣V∗∣最小点覆盖的顶点数

点覆盖是支配集

支配集不一定是点覆盖

极小点覆盖不一定是极小支配集

定理13.3： V ∗ 是 点 覆 盖 ⇔ V − V ∗ 是 独 立 集 V^*是点覆盖\Harr V-V^*是独立集 V∗是点覆盖⇔V−V∗是独立集

推论：无向图G无孤立点， V ∗ 是 极 小 点 覆 盖 ⇔ V − V ∗ 是 极 大 独 立 集 , 且 α 0 + β 0 = n V^*是极小点覆盖\Harr V-V^*是极大独立集,且\alpha_0+\beta_0=n V∗是极小点覆盖⇔V−V∗是极大独立集,且α0​+β0​=n

团: G[V*]是完全子图

极大团：V*是团，其真母集都不是

最大团：|V*|最大的团

团数： v 0 ( G ) = ∣ V ∗ ∣ v_0(G)=|V^*| v0​(G)=∣V∗∣，V*是最大团

定理13.4：无向图G， V ∗ 是 G 的 团 ⇔ V ∗ 是 G ‾ 的 独 立 集 V^*是G的团 \Harr V^*是\overline{G}的独立集 V∗是G的团⇔V∗是G的独立集

推论：无向图G， V ∗ 是 G 的 极 ( 最 ) 大 团 ⇔ V ∗ 是 G ‾ 的 极 ( 最 ) 大 独 立 集 ， v 0 ( G ) = β 0 ( G ‾ ) V^*是G的极(最)大团 \Harr V^*是\overline{G}的极(最)大独立集，v_0(G)=\beta_0(\overline G) V∗是G的极(最)大团⇔V∗是G的极(最)大独立集，v0​(G)=β0​(G)

边覆盖:边将所有点覆盖了

极小边覆盖：真母集不是边覆盖

最小边覆盖：边数最小的边覆盖

边覆盖数： α 1 ( G ) = ∣ E ∗ ∣ \alpha_1(G)=|E^*| α1​(G)=∣E∗∣,最小边覆盖的边数

匹配：边独立集，匹配中任意两边不相邻

极大匹配：真母集不是匹配

最大匹配：边数最大的匹配

匹配数： β 1 ( G ) = ∣ E ∗ ∣ \beta_1(G)=|E^*| β1​(G)=∣E∗∣,最大匹配的边数

定理13.5

设M是G中匹配

饱和点：v与M中边关联

非饱和点：v不与M中边关联

交错路径(圈)：在M和E-M中交替取边的路径(圈)

可增广交错路径：两端都是非饱和点的交错路径

定理13.7： n 设 M 1 , M 2 是 G 中 2 个 不 同 匹 配 , 则 G [ M 1 ⊕ M 2 ] 的 每 个 连 通 分 支 是 M 1 , M 2 中 的 边 组 成 的 交 错 圈 或 交 错 路 径 n设M1,M2是G中2个不同匹配,则G[M1⊕M2]的每个连通分支是M1,M2中的边组成的交错圈或交错路径 n设M1,M2是G中2个不同匹配,则G[M1⊕M2]的每个连通分支是M1,M2中的边组成的交错圈或交错路径

定理13.8： 设 M 是 G 中 匹 配 , Γ 是 M 的 可 增 广 路 径 , 则 M ’ = M ⊕ E ( Γ ) 也 是 G 中 匹 配 , 且 ∣ M ’ ∣ = ∣ M ∣ + 1 设M是G中匹配, Γ是M的可增广路径, 则M’=M⊕E(Γ)也是G中匹配, 且|M’|=|M|+1 设M是G中匹配,Γ是M的可增广路径,则M’=M⊕E(Γ)也是G中匹配,且∣M’∣=∣M∣+1

定理13.9： M 是 G 中 最 大 匹 配 ⇔ G 中 无 M 可 增 广 路 径 M是G中最大匹配 \Harr G中无M可增广路径 M是G中最大匹配⇔G中无M可增广路径

完美匹配：图中没有非饱和点的匹配

定理13.10（完美匹配的充要条件）： G 有 完 美 匹 配 ⇔ ∀ V ′ ⊂ V ( G ) , p 奇 ( G − V ′ ) ≤ ∣ V ′ ∣ G有完美匹配 \Harr \forall V'\subset V(G),p_奇(G-V')\le|V'| G有完美匹配⇔∀V′⊂V(G),p奇​(G−V′)≤∣V′∣

p 奇 p_奇 p奇​是奇数阶连通分支数

推论：无桥3正则图有完美匹配

完备匹配：|M|=| V 1 V_1 V1​|

t条件（判断有无完备匹配）： ∀ v ∈ V 1 , d ( v ) ≥ t ; ∀ v ∈ V 2 , d ( v ) ≤ t \forall v\in V_1,d(v)\ge t;\forall v\in V_2,d(v)\le t ∀v∈V1​,d(v)≥t;∀v∈V2​,d(v)≤t

定理13.11(Hall定理)： n 二 部 图 G = < V 1 , V 2 , E > , ∣ V 1 ∣ ≤ ∣ V 2 ∣ , 二 部 图 G 有 完 备 匹 配 ⇔ G 满 足 H a l l 条 件 ( ∣ S ∣ ≤ ∣ N ( S ) ∣ ) n二部图G=, |V1|≤|V2|, 二部图G有完备匹配⇔ G满足Hall条件(|S|≤|N(S)|) n二部图G=,∣V1∣≤∣V2∣,二部图G有完备匹配⇔G满足Hall条件(∣S∣≤∣N(S)∣)

Hall条件: 从 二 部 图 中 点 少 的 一 方 V 1 中 任 取 一 些 点 ， V 2 中 与 这 部 分 相 连 的 点 的 数 量 总 是 大 于 等 于 这 些 V 1 中 点 的 数 量 从二部图中点少的一方V_1中任取一些点，V_2中与这部分相连的点的数量总是大于等于这些V_1中点的数量 从二部图中点少的一方V1​中任取一些点，V2​中与这部分相连的点的数量总是大于等于这些V1​中点的数量

定理13.13： 设 G = < V 1 , V 2 , E > 是 k 正 则 二 部 图 , 则 G 中 存 在 k 个 边 不 重 的 完 美 匹 配 设G=是k正则二部图,则G中存在k个边不重的完美匹配 设G=是k正则二部图,则G中存在k个边不重的完美匹配

定理13.14: 设 G = < V 1 , V 2 , E > 是 无 孤 立 点 二 部 图 , 则 α 0 = β 1 设G=是无孤立点二部图,则\alpha_0=\beta_1 设G=是无孤立点二部图,则α0​=β1​(点覆盖数等于匹配数)