《图论及其应用》
知识大纲总结
基础与前沿研究院
谭兵
任课教师:Prof.王也洲

• ​五、匹配与因子分解

  • ​(Hall): $| N ( S ) | \geq | S |$ 

  • ​ $K_{2n}$ 完美匹配个数： $( 2 n - 1 ) ! !$  
    $K_{n,n}$ 完美匹配个数： $n!$ 
    

  • ​每个没有割边的 $3$ 正则图都有完美匹配。

  • ​有割边的 $3$ 正则图不一定就没有完美匹配。

  • ​ $3$ 正则图有割边，则不可 $1$ 因子分解

  • ​无割边的 $3$ 正则图可能也没有 $1$ 因子分解

  • ​奇数阶图不能有 $1$ 因子

  • ​一个连通图是 $2$ 可因子化的当且仅当它是偶数度正则图

  • ​具有H圈的 $3$ 正则图是 $1$ 可因子化的(反之不一定成立)

• ​一、图的基本概念

  • ​ $3$ ( $4$ )点非同构简单图 $4$ ( $11$ )个 $4$$4$

  • ​自补图除以 $4$ 的余数只能为 $0$ 或 $1$ 

  •  $G _ { 1 } \vee G _ { 2 },\text{点}:n _ { 1 } + n _ { 2 },\text{边}:m _ { 1 } + m _ { 2 } + n _ { 1 } n _ { 2 }$ 

  • ​ ${ G } _ { 1 } \times { G } _ { 2 },\text{点}:n _ { 1 } n _ { 2 },\text{边}:n _ { 1 } m _ { 2 } + n _ { 2 } m _ { 1 }$ 

  • ​ ${ G } _ { 1 } \left[ { G } _ { 2 } \right],\text{点}:n _ { 1 } n _ { 2 },\text{边}:n _ { 1 } m _ { 2 } + n _ { 2 }^2 m _ { 1 }$ 

  • ​ $A^2$ 的元素 $a_{ii}^{(2)}$ 是 $v_i$ 的度数

  • ​ $A^3$ 的元素 $a_{ii}^{(3)}$ 是含 $v_i$ 的三角形的数目的两倍

  • ​ $v_{i}$ 到 $v_{j}$ 长度为 $k$ 的通道的数目是 $a_{ij}^{(k)}$ 

  • ​矩阵 $A$ 的所有特征值的平方和等于该图边数的 $2$ 倍

  • ​ $K_n$ 的最大特征值为 $n-1$ 

  • ​ $n$ 阶完全偶图

• ​二、树

  • ​非同构的 $4,5,6$ 阶树的个数分别为 $2,3,6$ 

  • ​由 $k$ 颗树组成的森林满足 $m = n-k$ 

  • ​ $\tau \left( K _ { n } \right) = n ^ { n - 2 },\tau(k_{m,n})=n^{m-1}m^{n-1}$ 

• ​六、平面图

  • ​ $\sum \operatorname { deg } ( f ) = 2 m.$ 

  • ​ $欧拉公式：n-m+\varphi=2$ 

  • ​简单平面图满足 $m \leq 3 n - 6$ 

  • ​至少有 $9$ 个点的简单可平面图的补图是不可平面的

  • ​可平面的当且仅当它不含与 $K_{5}$ 或 $K_{3,3}$ 同胚的子图

  • ​极大平面图必连通，且 $n\ge 3$ 则无割边，三角形特征

  • ​极大平面图满足： $m=3n–6,\varphi=2n–4$ 

  • ​极大外平面图当且仅当其外部面的边界是圈，内部面是三角形

  • ​极大外平面图有 $n-2$ 个内部面

  • ​至少有 $7$ 个顶点的外可平面图的补图不是外可平面图

  • ​ $G^*的点数 = G 的面数;\\ G^* 的边数 = G 的边数；\\ G^* 的面数 = G 的点数 (G 连通)；$ 

  • ​同构的平面图可以有不同构的对偶图

• ​三、图的连通度

  • ​阶数 $\ge 3$ 的无环连通图，有割边 $\Rightarrow$ 有割点

  • ​ $(1){ \kappa} \left( { K } _ { { n } } \right) = { n } - { 1 },(2) { \kappa } \left( { C } _ { n } \right) = { 2 }，\text{ 其中 }C_n \text{为} n \text{圈 },n\ge 3.$ 

  • ​ $(1) { \lambda } \left( { K } _ { { n } } \right) = { n } - { 1 },(2) { \lambda } \left( { C } _ { n } \right) = { 2 }，\text{ 其中 }C_n \text{为} n \text{圈 },n\ge 2.$ 

  • ​ $k$ 连通一定是 $k$ 边连通的

  • ​ $\kappa ( G ) \leq \lambda ( G ) \leq \delta ( G )$ ， $\kappa ( G ) \leq \lfloor 2 m / n \rfloor.$ 

  • ​图 $G$ 的顶点数为 $n$ 且 $7$ 连通，则其边数至少为 $\lceil 7n/2 \rceil$ 

• ​四、Euler图与Hamilton图

  • ​Euler图没有割边，有可能有割点

  • ​一必要( $\omega ( G - S ) \leq | S |$ )
    四充分( $\delta ( G ) \geq \frac { n } { 2 }$ , $d ( u ) + d ( v ) \geq n$ ，
    闭包是完全图， $| E ( G ) | > \left( \begin{array} { c } { n - 1 } \\ { 2 } \end{array} \right) + 1$ )
    一充要(闭包是 H图)$H$图)

  • ​ $\forall m<n/2$ ，或有 $d_m>m$ ，或有 $d_{n-m}\ge n-m$ ，则H图

  • ​具有 $5$ 个点的度极大非哈密尔顿图族为 $C_1^5$ 和 $C_2^5$ 

  • ​ $n$ 阶完全图中H圈的个数为 $(n-1)!$ 

• ​七、图的着色

  • ​ $\chi ^ { \prime } \left( K_{m,n} \right) = \Delta$ ， $偶图的边色数$  $\chi ^ { \prime } = \Delta$ 

  • ​ $n=2k+1$ 且边数 $m > k \Delta$ ，则 $\chi ^ { \prime } = \Delta + 1$ 

  • ​奇阶 $\chi$ 正则简单图，则 $\chi ^ { \prime } = \Delta + 1$ 

  •  $n 为奇数，\chi ^ { \prime } \left( K _ { n } \right) = ( n - 1 ) + 1 = n，\chi ^ { \prime } \left( C _ { n } \right) = 2 + 1 = 3\\ n 为偶数，\chi ^ { \prime } \left( K _ { n } \right) = n - 1，\chi ^ { \prime } \left( C _ { n } \right) = 2$ 

  • ​完全图和奇圈的 $\chi =\Delta +1$ 

  • ​彼得森图的点色数为 $3$ ，边色数为 $4$ 

  • ​ $n$ 个点的树，则 $P_k(G) = k(k-1)^{n-1}$ 

  • ​ $h ( G , x ) = \prod _ { i = 1 } ^ { t } h \left( H _ { i } , x \right).$ 

  • ​同构的图有相同的色多项式，但其逆不真

• ​八、有向图

  • ​ $m$ 元完全树： $m i = t + i - 1$ 

  • ​二元完全树： $m(T) = 2(t-1)$ 

  • ​ $高度为h的二元完全树最少有 h+1片叶子$