离散数学

第七章 图

邻域、顶点的度

• 邻域$N_G(v)$：与$v$相邻的点的集合，$N_G(v)=\{u|u\in V(G)\wedge (u,v)\in E(G)\wedge u\ne v\}$

从定义来看，有自环的点的邻域不算自身

• 关联集$I_G(v)$：与$v$关联的边的集合，$I_G(v)=\{e|e\mathrm{与}v\mathrm{关}\mathrm{联}\}$
• 度$d_G(v)$：与$v$关联的边的次数之和
• 出度、入度

注意：环对于结点度的贡献是 2，孤立顶点的度为 0

• 最大度$\mathrm{\Delta }(G)$，$\mathrm{\Delta }$；最小度$\delta (G)$，$\delta$

周长与围长

• 周长$c(G)$：含圈的无向简单图$G$中，$G$中最长圈的长度。
• 围长$g(G)$：$G$中最短圈的长度。

握手定理

1. 每个图中，结点度数的总和等于边数的两倍。

   $$\sum _{v\in V}\mathrm{deg}(v)=2|E|$$

2. 有向图中，出度和与入度和相等且等于边数。

   $$\sum _{i=1}^n{d}^{+}(v_i)=\sum _{i=1}^n{d}^{-}(v_i)=m$$

3. 推论：在任何图中，奇数度顶点的个数是偶数。

简单图、零图、$k$-正则图

• 简单图：无环、无平行边
• 零图：无边

辨别：平凡图：$1$阶零图；空图：无点

• $k$-正则图：无向简单图且各个点的度数均为$k$

可简单图化、同构

前提：可图化（度数总和为偶数）

• Havel 定理：每次删去图上度数最大的一个点，若删去后的图仍为可图化的且未出现负数度顶点，则继续，否则不可简单图化。

• Erdös 定理：

  

• 同构：

Havel 定理中能选择点的时候就可以出不同构的图了吧。

极大路径

原路径${\mathrm{\Gamma }}_l$使用扩大路径法扩大后的极大路径${\mathrm{\Gamma }}_{l+k}$的两个端点不与路径外的顶点相邻。

割点、桥、点连通度、边连通度

• 割点：$v\mathrm{是}\mathrm{割}\mathrm{点}\iff \{v\}\mathrm{是}\mathrm{点}\mathrm{割}\mathrm{集}$
• 桥：$(u,v)\mathrm{是}\mathrm{桥}\iff \{(u,v)\}\mathrm{是}\mathrm{边}\mathrm{割}\mathrm{集}$
• 点连通度$\kappa$：最小的点割集中的点数，规定$\kappa (K_n)=n-1$，而如果$G$非连通，则$\kappa (G)=0$。
• 边连通度$\lambda$：最小的边割集中的边数，如果$G$非连通，则$\lambda (G)=0$。
• Whitney 定理：$\kappa \le \lambda \le \delta$

很好理解，边割集最差情况是一个点的所有关联边，最好的情况是桥；点割集（除了割点之外）最差的就是拿掉某个边割集中的边某侧所关联的所有的点。

二部图、完全二部图

• 二部图：（定理 7.8）一个无向图$\ast G＝<V,E>\ast$是二部图当且仅当$\ast G\ast$中无奇圈。
• 完全二部图：完全二部图 $\ast K_{n,n}\ast$的周长是$2n$，围长是$4$。

重点习题

邻域、顶点的度 握手定理

由边数得总度数为$2\times 16=32$，$32-3\times 4-4\times 3=8$，而其余顶点度数均小于$3$，则至少还有$8÷(3-1)=4$个顶点。图$G$中至少有$4+3+4=11$个顶点。

对多面体建模，设图共有$n$个面，各个面编号为$1,2,...,n$。令图$G=<V,W>$，其中点集$V=\{v_i|i\mathrm{是}\mathrm{一}\mathrm{个}\mathrm{面}\}$，边集$E=\{(v_i,v_j)|i\mathrm{与}j\mathrm{有}\mathrm{公}\mathrm{共}\mathrm{棱}\}$。则多面体编号为$i$的面的棱的数量就是点$v_i$的度数$d(v_i)$。如果空间中存在有奇数个面且每个面均有奇数条棱的多面体，则$G$的总度数$\sum _{i=1}^{n}d(v_i)$为奇数。由握手定理，总度数必为偶数，则空间中不可能存在有奇数个面且每个面均有奇数条棱的多面体。

设共有$n$个选手，若下过则连边。如果找不到两名下过盘数是相同的选手，说明所有选手的盘数各不相同。而一个选手至多下$n-1$盘，至少下$1$盘，此时至多只能满足$n-1$个选手的盘数各不相同。因此总能找到两名选手下过的盘数是相同的。

若$G$中两个奇数度顶点不连通，则$G$中的两个奇数度顶点分属两个连通分支$G_1$和$G_2$。此时$G_1$或$G_2$中都只有一个奇数度顶点，度数和为奇数，矛盾。

可简单图化、同构

极大路径

第八章 欧拉图与哈密顿图

欧拉图

• 欧拉回路：通过所有边一次的简单回路
• 欧拉路，欧拉通路：通过所有边一次的简单通路
• 欧拉图：有欧拉回路的图
• 半欧拉图：有欧拉通路，无欧拉回路的图

规定平凡图为欧拉图 辨别：平凡图：$1$阶零图；空图：无点 环不影响图的欧拉性

• 定理 1：设$G$是无向连通图，则

  $$\begin{gathered} G\mathrm{是}\mathrm{欧}\mathrm{拉}\mathrm{图} \\ \iff G\mathrm{中}\mathrm{所}\mathrm{有}\mathrm{顶}\mathrm{点}\mathrm{都}\mathrm{是}\mathrm{偶}\mathrm{数}\mathrm{度} \\ \iff G\mathrm{是}\mathrm{若}\mathrm{干}\mathrm{个}\mathrm{边}\mathrm{不}\mathrm{交}\mathrm{的}\mathrm{圈}\mathrm{的}\mathrm{并} \end{gathered}$$

• 定理 2：设$G$是无向连通图，则

  $$\begin{gathered} G\mathrm{是}\mathrm{半}\mathrm{欧}\mathrm{拉}\mathrm{图} \\ \iff G\mathrm{中}\mathrm{恰}\mathrm{有}2\mathrm{个}\mathrm{奇}\mathrm{度}\mathrm{顶}\mathrm{点} \end{gathered}$$

• 定理 3：设$G$是有向连通图，则

$$\begin{gathered} G\mathrm{是}\mathrm{欧}\mathrm{拉}\mathrm{图} \\ \iff \mathrm{\forall }v\in V(G),d^{+}(v)=d^{-}(v) \\ \iff G\mathrm{是}\mathrm{若}\mathrm{干}\mathrm{个}\mathrm{边}\mathrm{不}\mathrm{交}\mathrm{的}\mathrm{有}\mathrm{向}\mathrm{圈}\mathrm{的}\mathrm{并} \end{gathered}$$

• 定理 4：设$G$是有向连通图，则

$$\begin{gathered} G\mathrm{是}\mathrm{半}\mathrm{欧}\mathrm{拉}\mathrm{图} \\ \iff G\mathrm{中}\mathrm{恰}\mathrm{有}2\mathrm{个}\mathrm{奇}\mathrm{度}\mathrm{顶}\mathrm{点}，\mathrm{其}\mathrm{中}1\mathrm{个}\mathrm{入}\mathrm{度}\mathrm{比}\mathrm{出}\mathrm{度}\mathrm{大}1，\mathrm{另}1\mathrm{个}\mathrm{出}\mathrm{度}\mathrm{比}\mathrm{入}\mathrm{度}\mathrm{大}1，\mathrm{其}\mathrm{余}\mathrm{顶}\mathrm{点}\mathrm{入}\mathrm{度}\mathrm{等}\mathrm{于}\mathrm{出}\mathrm{度} \end{gathered}$$

哈密顿图

• 哈密顿回路：经过所有顶点一次的初级回路
• 哈密顿通路：经过所有顶点一次的初级通路

初级意味着点不重

• 哈密顿图：有哈密顿回路的图
• 半哈密顿图：有哈密顿通路，无哈密顿回路的图

平凡图是哈密顿图

• 定理 6（哈密顿图性质）：设无向图$G$是哈密顿图，则对任意$V_1\in V$有$p(G-V_1)\le |V_1|$。
• 定理 6 推论：设无向图$G$是半哈密顿图，则对任意$V_1\in V$有$p(G-V_1)\le |V_1|+1$。

挺好理解的，哈密顿回路就是一个大圈，拿掉一个点就可以变成哈密顿通路

• 定理 7：若$n(\ge 2)$阶无向简单图$G$中，任意不相邻的顶点$u$和$v$有$d(u)+d(v)\ge n-1$，则$G$中存在哈密顿通路。

  

• 定理 7 推论（哈密顿图判定）：若$n(\ge 3)$阶无向简单图$G$中，任意不相邻的顶点$u$和$v$有$d(u)+d(v)\ge n$，则$G$是哈密顿图。

完全图$K_n$中边不重的哈密顿回路的数量

• 定理 11：完全图$K_{2k+1}(k\ge 1)$中含$k$条边不重的哈密顿回路，且这些回路中含$K_{2k+1}$中的全部边。
• 定理 11 推论：完全图$K_{2k}(k\ge 2)$中含$k-1$条边不重的哈密顿回路，删除这些边之后得到的是一个匹配。

重点习题

欧拉图

欧拉图是若干个边不交的圈的并，至少拿掉 2 条边才能破坏其连通性。

哈密顿图

用这个定理定理 6（哈密顿图性质）：设无向图$G$是哈密顿图，则对任意$V_1\in V$有$p(G-V_1)\le |V_1|$。 ，对于$(a)$拿掉$5$个$4$度顶点，此时产生了$7$个连通分支，不满足定理 6。

构造哈密顿回路，保证每个点都能有边。

第九章 树

树

• 定理 1（六个等价定义）：

  $$\begin{gathered} G\mathrm{是}\mathrm{树}（G\mathrm{连}\mathrm{通}\mathrm{且}\mathrm{无}\mathrm{回}\mathrm{路}） \\ \iff G\mathrm{中}\mathrm{任}\mathrm{二}\mathrm{顶}\mathrm{点}\mathrm{之}\mathrm{间}\mathrm{存}\mathrm{在}\mathrm{唯}\mathrm{一}\mathrm{路}\mathrm{径} \\ \iff G\mathrm{中}\mathrm{无}\mathrm{圈}，m=n-1 \\ \iff G\mathrm{连}\mathrm{通}，m=n-1 \\ \iff G\mathrm{连}\mathrm{通}，\mathrm{每}\mathrm{条}\mathrm{边}\mathrm{均}\mathrm{为}\mathrm{桥} \\ \iff G\mathrm{中}\mathrm{无}\mathrm{圈}，\mathrm{但}\mathrm{在}\mathrm{任}\mathrm{二}\mathrm{不}\mathrm{同}\mathrm{顶}\mathrm{点}\mathrm{之}\mathrm{间}\mathrm{增}\mathrm{加}\mathrm{新}\mathrm{边}\mathrm{可}\mathrm{构}\mathrm{造}\mathrm{唯}\mathrm{一}\mathrm{的}\mathrm{圈} \end{gathered}$$

生成树

• 生成子图：包含所有顶点的子图

导出子图：选边，再往点集加关联的点

• 生成树$T$：$T$是$G$的生成子图且是树。
• 定理 3（存在定理）：无向图$G$具有生成树当且仅当$G$是连通的。
• 生成树的求法：

  • 破圈法：若图中无圈，则图本身就是生成树。否则删去圈上的任一条边，这不破坏连通性，重复进行直到无圈为止，剩下的图是一棵生成树。

  • 定理 6（求生成树的个数$\tau (G)$）：$\tau (G)=\tau (G-e)+\tau (G\setminus e)$

  • 定理 3：记$M_f^{\prime }$是$M_f(G)$中任意$n-1$列组成的方阵，则$T\mathrm{是}G\mathrm{的}\mathrm{生}\mathrm{成}\mathrm{树}\iff M_f^{\prime }\mathrm{的}\mathrm{行}\mathrm{列}\mathrm{式}|M_f^{\prime }|\ne 0$。

    1. 忽略环，求关联矩阵
    2. 任选参考点，求基本关联矩阵
    3. 求所有$n-1$阶子方阵，计算行列式，行列式非$0$的是生成树

基本回路系统、环路空间

1. 通过弦确定基本回路，给出基本回路系统
2. 利用基本回路系统中的元素进行环合运算（参与运算的元素从$0$个开始到所有元素一起参与）

• 维数：$m-n+1$

基本割集系统、断集空间

割集是断集，断集不一定是割集（可满足连通分支数目增加，但不一定满足极小性）

1. 通过树枝确定割集，给出基本割集系统
2. 利用基本割集系统中的元素进行对称差运算

• 维数：$n-1$

根树

• 根树是有向树，其为平凡树或只有一个顶点入度为$0$而其他顶点的入度均为$1$。
• 顶点$v$的层数$L(v)$：从树根到$v$路径长度
• 树高$h(T)$：顶点的最大层数

$r$叉树

• $r$叉树：$\mathrm{\forall }v\in V(T),d^{+}(v)\le r$
• 正则$r$叉树：每个分支点恰好有$r$个儿子
• 完全正则$r$叉树：树叶的层数均为树高的$r$叉正则树
• 定理 14.13：设正则$\ast r(\ge 2)\ast$叉树$T$有$\ast i\ast$个分支点和$\ast t\ast$个树叶，则$(r-1)i=t-1$。
  • 证明：握手定理，有向图的出度和和入度和相等且等于边数。

重点习题

树 根树

$$\begin{gathered} \sum d=9+3\times 3+(n-9-3)\times 4=2\times (n-1) \\ \Rightarrow n=14,n-9-3=2 \end{gathered}$$

生成树

基本回路系统、环路空间 基本割集系统、断集空间

$r$叉树

第十章 图的矩阵表示

关联矩阵

行为点，列为边。

• 有向图：

  

• 无向图：

  

• 性质：

  • 平行边对应的列相同
  • 不能表示自环
  • 无向图关联矩阵中，每行所有$1$对应的边构成断集

• 基本关联矩阵：选取一个参考点，从关联矩阵$M(G)$中删除参考点对应的行，记作$M_f(G)$。

邻接矩阵、相邻矩阵

可以表示环，$a_{ij}$表示从$v_i$到$v_j$的边数。

• 有向图邻接矩阵：

  

  • 每行和为出度，每列和为入度，主对角元表示环

• 邻接矩阵求通路数：$a_{it}\cdot a_{tj}$即$v_i$经过$v_t$到$v_j$的边数

  

  

  

  

  • 对每个非$0$元和主对角元置$1$，即可得到可达矩阵。

• 无向图相邻矩阵：是对称矩阵。

  • 使用相邻矩阵求通路数、连通矩阵，和邻接矩阵相似。

重点习题

使用基本关联矩阵法。

第十一章 平面图

平面图

• 可平面图/平面图：可以画在平面上，使得边与边不在非顶点处相交的图
• 平面嵌入（平面表示）：画在平面上使得边与边不在非顶点处相交的图

可平面图主要表明图具有平面性质，平面嵌入是平面图的一种表示形式，平面图的平面嵌入不唯一

• 性质

  • 定理 2：所有面的次数和为边数的两倍。（其实就是握手定理）

  • 定理 8、定理 9：

    

  • 定理10：

    

  • 定理11：

    

  • 定理12：简单平面图$G$，$\delta (G)\le 5$。

• Kuratowski 定理（平面图判定定理）

  $$\begin{gathered} \mathrm{图}G\mathrm{是}\mathrm{平}\mathrm{面}\mathrm{图}\iff G\mathrm{没}\mathrm{有}\mathrm{与}{K}_5\mathrm{同}\mathrm{胚}\mathrm{的}\mathrm{子}\mathrm{图}，\mathrm{也}\mathrm{没}\mathrm{有}\mathrm{与}{K}_{3,3}\mathrm{同}\mathrm{胚}\mathrm{的}\mathrm{子}\mathrm{图} \\ \iff G\mathrm{没}\mathrm{有}\mathrm{可}\mathrm{以}\mathrm{边}\mathrm{收}\mathrm{缩}\mathrm{到}{K}_5\mathrm{的}\mathrm{子}\mathrm{图}，\mathrm{也}\mathrm{没}\mathrm{有}\mathrm{可}\mathrm{以}\mathrm{边}\mathrm{收}\mathrm{缩}\mathrm{到}{K}_{3,3}\mathrm{的}\mathrm{子}\mathrm{图} \end{gathered}$$

  例题：

  

  

  这里为什么可以删除边呢？因为定理要求的是没有和$K_{3,3}$或$K_5$同胚的子图。

  

  

极大平面图

• 极大平面图：是平面图，但在任意两个不相邻顶点之间加边就是非平面图。
• 性质：

  • 一定连通，否则不极大

  • 不含有割点和桥。如果含有割点，则一定可以加边。

  • 定理 4：$n(\ge 3)\mathrm{阶}\mathrm{简}\mathrm{单}\mathrm{连}\mathrm{通}\mathrm{平}\mathrm{面}\mathrm{图}\mathrm{是}\mathrm{极}\mathrm{大}\mathrm{平}\mathrm{面}\mathrm{图}\iff \mathrm{\forall }R,\mathrm{deg}(R)=3$

    

    

    不能同时把$(v_1,v_3)$和$(v_2,v_4)$在不经过该平面内的情况下都连起来

    

欧拉公式

• 欧拉公式：$n-m+r=2$
• 推广：$n-m+r=p+1$

对偶图、自对偶图

1. 在$G$的每个面内取一个点作为顶点
2. 如果两个面有公共边，则将两个面取的顶点过公共边连边。如果是悬挂边，那就是自环。

• 性质：

  • 无论原图如何，对偶图$G^{\ast }$是连通的。

  很好理解，因为一定有一个外部面的点

  • 定理 15：
  $$\begin{gathered} n^{\ast }=r \\ {m}^{\ast }=m \\ {r}^{\ast }=n \\ {d}_{G^{\ast }}(v^{\ast })=\mathrm{deg}(R) \end{gathered}$$
  • 定理 16 同欧拉公式推广。

• 自对偶图：$G\cong G^{\ast }$

• 轮图$W_n$：阶数$n$，外圈$C_{n-1}$

  • $n\ge 4$时，轮图$W_n$是自对偶图

  

重点习题

平面图

只需构造其平面嵌入。

证明非平面图时需要用Kuratowski 定理（平面图判定定理） 。

欧拉公式 对偶图、自对偶图

平面图有$n-m+r=2$。

（$\Rightarrow$）对偶图$G^{\ast }$为欧拉图，则所有点度数为偶数，由对偶图性质得$G$中每个面的次数均为偶数。

（$\Leftarrow$）差不多这么证明吧。

第十二章 图的着色

色数

• 点色数$\chi (G)$

  • 特殊的点色数

  

  • 定理 5：$\chi (G)\le \mathrm{\Delta }(G)+1$

  很好理解，这里的$+1$就是$d(v_k)=\mathrm{\Delta }(G)$的那个点。

  • 定理 6（Brooks 定理）：若连通图$G$不是完全图$K_n(n\ge 3)$，也不是奇圈，则$\chi (G)\le \mathrm{\Delta }(G)$。

  相邻点中有两个点着同色，只要这两点不相邻就行，不是完全图保证了这一点。而如果是奇圈，$d=2$，但$\chi =3$。

• 边色数${\chi }^{\prime }(G)$

  • 特殊的边色数
    • 二部图$G$，${\chi }^{\prime }(G)=\mathrm{\Delta }(G)$
    • 完全图$K_n$：$n>1$时，${\chi }^{\prime }(K_n)=\{\begin{array}{l}n,n\mathrm{为}\mathrm{奇}\mathrm{数}\\ n-1,n\mathrm{为}\mathrm{偶}\mathrm{数}\end{array}$
  • 定理 17（Vizing 定理）：$\mathrm{\Delta }(G)\le {\chi }^{\prime }(G)\le \mathrm{\Delta }(G)+1$

• 面色数${\chi }^{\ast }(G)$

  • 定理 13、14：研究平面图面着色⇔研究平面图点着色

五色定理

• 定理 15：任何平面图都可$6$-着色。

  

• 定理 16：任何平面图都可$5$-着色。

  

  

  

色数多项式

• 递推公式：

$$\begin{gathered} f(G,k)=f(G\cup e,k)+f(G\setminus e,k),e\notin E \\ f(G,k)=f(G-e,k)-f(G\setminus e,k),e\in E \end{gathered}$$

加边约束了着色条件，所以加上收缩边的色数；减边放宽了着色条件，所以减去收缩边的色数。

• 特殊的色数多项式

  • 零图：$f(N_n,k)=k^n$

  各个点相互独立

  • 完全图：$\begin{array}{c}f(K_n,k)=\prod _{i=0}^{n-1}(k-i)\\ f(K_n,k)=f(K_{n-1},k)(k-(n-1))\end{array}$

  每加入一个点，就用掉一种颜色

  • 树：$f(T,k)=k(k-1{)}^{n-1}$

  树根有$k$种着色方式，对于每个后代只需要选择和父节点不同的颜色就可以，所以除了树根之外的$k-1$个顶点各有$n-1$种着色方式。

  • 圈：$f(C_n,k)=(k-1{)}^n+(-1{)}^n(k-1)$

应用

• 同色边构成“边独立集”, 或“匹配”

重点习题

色数 色数多项式

应用

第十三章 支配集、覆盖集、独立集与匹配集

支配集

• 支配集：是点集$V$的子集，满足任何在$V-V^{\ast }$中的点能和$V^{\ast }$中的某点相邻。
• 极小支配集：真子集都不是支配集的支配集。
• 最小支配集：$|V^{\ast }|$最小的支配集
• 支配数${\gamma }_0$：${\gamma }_0(G)=|V^{\ast }|$，$V^{\ast }$是最小支配集
• 定理 1：无向图$G$无孤立点，如果$V_1^{\ast }$是极小支配集，则在$V-V_1^{\ast }$中存在$V_2^{\ast }$也是极小支配集。

点覆盖

• 点覆盖：$\mathrm{\forall }e\in E,\text{exist}v\in V^{\ast },v\mathrm{关}\mathrm{联}e$
• 极小点覆盖：真子集都不是点覆盖的点覆盖。
• 最小点覆盖：$|V^{\ast }|$最小的点覆盖
• 点覆盖数${\alpha }_0$：${\alpha }_0(G)=|V^{\ast }|$，$|V^{\ast }|$是最小点覆盖

边覆盖

• 边覆盖：$\mathrm{\forall }v\in V,\text{exist}e\in E^{\ast },e\mathrm{关}\mathrm{联}v$
• 极小边覆盖：真子集都不是边覆盖的边覆盖。
• 最小边覆盖：$|E^{\ast }|$最小的边覆盖
• 点覆盖数${\alpha }_1$：${\alpha }_1(G)=|E^{\ast }|$，$|E^{\ast }|$是最小边覆盖

独立集

• 独立集：独立集中任意两点之间没有边
• 极大独立集：真母集都不是独立集的独立集
• 最大独立集：$|V^{\ast }|$最大的独立集
• 独立数${\beta }_0$：${\beta }_0(G)=|V^{\ast }|$$|V^{\ast }|$是最大独立集
• 定理 2：无向图$G$无孤立点，则图中的极大独立集是极小支配集。

逆命题不成立

• 定理 3：无向图$G$无孤立点，$V^{\ast }\mathrm{是}\mathrm{点}\mathrm{覆}\mathrm{盖}\iff V-V^{\ast }\mathrm{是}\mathrm{独}\mathrm{立}\mathrm{集}$。

• 定理 3 推论：$V^{\ast }\mathrm{是}\mathrm{极}(\mathrm{最})\mathrm{小}\mathrm{点}\mathrm{覆}\mathrm{盖}\iff V-V^{\ast }\mathrm{是}\mathrm{极}(\mathrm{最})\mathrm{大}\mathrm{独}\mathrm{立}\mathrm{集}$，${\alpha }_0+{\beta }_0=n$

  

匹配（边独立集）

• 匹配数${\beta }_1$：${\beta }_1(G)=|E^{\ast }|$，$E^{\ast }$是最大匹配

• 最大匹配：

  • 定理 9（Berge 定理）：$M\mathrm{是}G\mathrm{中}\mathrm{最}\mathrm{大}\mathrm{匹}\mathrm{配}\iff G\mathrm{中}\mathrm{无}M\mathrm{可}\mathrm{增}\mathrm{广}\mathrm{路}\mathrm{径}$

• 完美匹配：没有非饱和点的匹配。

  • 定理 10（Tutte 定理）：$G\mathrm{有}\mathrm{完}\mathrm{美}\mathrm{匹}\mathrm{配}\iff \forall V^{\prime }\subset V(G),p_{\mathrm{奇}}(G-V^{\prime })\le |V^{\prime }|$，$p_{\mathrm{奇}}$是奇数阶连通分支数

• 完备匹配：二部图小的那一部分均为饱和点的匹配。

  • 定理 11（Hall 条件）：$|V_1|\le |V_2|，\forall S\subseteq V_1,|S|\le |N(S)|$，相异性条件
  • 定理 12（t 条件）：设$G=<V_1,V_2,E>$是二部图，若$V_1$中每个顶点至少关联$t(t\ge 1)$条边，而$V_2$中每个顶点至多关联$t$条边，则$G$中存在完备匹配。
  • $t\mathrm{条}\mathrm{件}\Rightarrow \exists \mathrm{完}\mathrm{备}\mathrm{匹}\mathrm{配}\iff \text{Hall}\mathrm{条}\mathrm{件}$

  

团

• 团：$G[V^{\ast }]$是完全子图
• 极大团：$V^{\ast }$是团，其真母集都不是
• 最大团：$|V^{\ast }|$最大的团
• 团数：${\nu }_0(G)=|V^{\ast }|$，$V^{\ast }$是最大团

运算律（不知道有没有用）

重点习题