【图论】重庆大学图论与应用课程期末复习资料2-各章考点（填空证明部分）（私人复习资料）

一、图与网络的基本概念

1. 生成子图：生成子图$G’$中顶点个数V’必须和原图G中V的数量相同，而$E’\in E$即可。
2. 顶点集导出子图：$V1\subseteq V$，以$V1$为顶点集，两个端点都在$V$中的边为边集的$G$的子图。
3. 边集导出子图：$E1\subseteq E$，以$E1$为边集，$E1$的端点集为顶点集的图$G$的子图。
4. 简单图：既无环又无重边的图为简单图
5. 完备图：任二顶点相邻的简单图,称为完备图,记为 $K_n$其中n 为顶点的数目
6. 二部图：一个图是偶图（二部图）当且当它不包含奇圈
7. 握手定理：图$G=(V,E)$中所有顶点的度的和等于边数m的2倍
8. 同构：顶点集之间存在一一对应关系，边也有一一对应的关系,则称图 $G$与$H$同构，有向图的同构对应边的方向要相同。必要条件 (1) 顶点数相同(2) 边数相同(3) 关联边数相同的顶点个数相同。

二、树

1. 树：无圈连通图称为树
2. 树充要条件：$G$无环且任何两个顶点之间有唯一的路径
3. 树充要条件：$G$连通,且 $e(G)=V(G)-1$
4. 树充要条件：$G$连通，且对$G$的任一边$e,G-e$不连通
5. 生成树：$G$的边数最少的连通生成子图

三、连通性

1. 点连通度：设$G$连通,$V\subset V(G),G[V-V]$不连通,则称$V$为$G$的点断集。最小点断集中顶点的个数称为 $G$的连通度记为 $K(G)$，若$G$无点断集,则规定$K(G)=n-1$，$平凡图、不连通图=0$
2. 边连通度：设$G$连通,$E\subset E(G)$, $G-E$(从$G$中删除$E$中的边)不连通,则称$E$是$G$的边断集。最小边断集所含的边数称为 $G$的边连通度记为$K‘(G)$，当$|E^{\prime }|=1$时,称E中的边$e$为割边，$平凡图、不连通图=0$
3. k连通图：若一个图的连通度至少为$k$，则称该图是$k$连通的。于是，非平凡连通图均是$1$连通的；图$G$是2连通的当且仅当$G$连通、无割点且至少含有$3$个点。
4. 点连通度、边连通度、最小度：$K(G)<=K^{\prime }(G)<=\delta （G）$
5. 割边：设e是图G的一条边，若$\omega (G-e)＞\omega (G)$, 则称$e$为$G$的割边。$e$是图$G$的割边，当且仅当$e$不在$G$的任何圈中。
6. 割点：$v$是$G$的割点当且仅当$V(G-v)$可划分为两个非空顶点子集$V_1$与$V_2$，使$x\in V_1，y\in V_2$，点v都在每一条 $(x,y)$ 路上。
7. 割集：$[S,S^{\prime }]$表示一个端点在$S$,另一个端点在$S$的全体边组成的集合，设$G$连通,若$[S,S’]$只把$G$断成两个分支,则称$[S,S^{\prime }]$为$G$的一个割集。
8. 树和图：设$v$是树的顶点，则$v$是$G$的割点当且仅当度 $d(v)>=2$

习题15：去掉$e=(u,v)$ ，在$G-e$中$u$所在的分支仅有一个奇度顶点，与握手定理矛盾

习题16：反证法，$e=(u,v)$ ，$G-e$中$u$所在的分支$G_1$，$G_1$为二部图，因为二部图所有子图均为二部图，则$\Sigma （G_1）=k|X_1|=k|Y_1|-1=>k$，$（|X_1|-|Y_1|）=1（k>=2）$，不成立

四、路径算法

1. Floyd：复杂度$O（n^3）$

五、匹配

1. 边独立集（匹配）：如果$M$是图$G$的边子集(不含环），且$M$中的任意两条边没有共同顶点，则称$M$是$G$的一个匹配
2. 最大匹配：如果$M$是图$G$的包含边数最多的匹配，称$M$是$G$的一个最大匹配。特别是，若最大匹配饱和了$G$的所有顶点，称它为$G$的一个完美匹配（理想匹配）
3. 二部图理想匹配：若$G$是$k(k>0)$正则偶图，则$G$存在完美匹配
4. 贝尔热定理：$G$的匹配$M$是最大匹配，当且仅当$G$不包含M可扩路
5. Hall定理：二分图存在完美匹配当且仅当 $\forall S\subseteq A$，都有$|N(S)|⩾|S|$
6. 哥尼定理：在偶图中，最大匹配的边数等于最小覆盖的顶点数
7. 托特定理：图$G$有完美匹配当且仅当对V的任意非空真子集S, 有：$（奇分支数目)|o(G-S)|⩽|S|$

六、行遍性问题

1. 欧拉巡回：经过$G$的每边正好一次的巡回称为欧拉巡回
2. 欧拉图：存在欧拉巡回的图称为欧拉图或E图
3. 欧拉图的充要条件：连通、无奇度顶点
4. 欧拉道路的充要条件：连通、最多只有两个奇度顶点
5. 哈米尔顿路径：经过图$G$每个顶点正好一次的路径，简称$H$路径。
6. 哈米尔顿图：经过$G$的每个顶点正好一次的圈为H圈。含H圈的图称为哈米尔顿图或$H$图。
7. H图的必要条件：$$\begin{gathered} 其\forall S\subset V，S\ne \varnothing \\ \omega (G-S)\le |S| \end{gathered}$$

七、平面图

1. 平面图：一个图若能在曲面$S$上画出,使任两边在非顶点处不相交,则称此图可以在曲面$S$上嵌人。可嵌入平面的图称为可嵌平面图,否则称为非平面图。可嵌平面图 $G$嵌人平面形成的图,称为 $G$的平面嵌入。
2. 欧拉公式：设$G=(n,m)$是连通平面图，$\varphi$是G的面数，$$n-m+\varphi =2$$
3. 平面图推论：$G$是$v>=3$的简单平面图，$$\epsilon \le 3v-6$$，$$\delta (G)\le 5$$
4. 库拉托夫斯基定理：图$G$是非可平面的，当且仅当它含有$K_5$或$K_{3,3}$细分的子图