# 图 **无向图** **有向图** 混合图 **邻接点** **邻接边** **自回路/环** **孤立点** **零图**：由若干个孤立点构成的图 **平凡图**：仅由单个孤立点构成的图 平行边 多重图：含有平行边 **简单图**：不含有平行边和环 **结点的度数** $\Delta(G)$: 一个图最大的结点度数 $\delta(G)$: 一个图最小的结点度数 **握手定理（握手引理、度数和公式；Handshaking Lemma）**：对有限无向图 $G=(V,E)$，结点度数的总和等于边数的两倍。 $\sum\limits_{v\in V}deg(v) = 2 |E|$ 不要求图连通，也不要求是简单图；允许平行边和环，环在其端点的度数中计两次。 因此结点度数之和一定为偶数；结点总数本身不一定为偶数。 **握手定理的推论（奇度顶点个数为偶数）**：有限无向图中，度数为**奇数**的结点必为**偶数**个。 **入度 出度** 入度与出度之和是该结点的度数 **有向图度数和定理（入度和等于出度和）**: 在*有向图*中，所有结点出度之和等于所有结点入度之和 **完全图**（$K_n$）：每对结点之间均有边相连的简单图 **完全图边数公式**: 无向完全图的边数 = $\frac{n(n-1)}{2}$ **补图**：由图$G$的所有结点和所有能使图$G$成为完全图的添加边组成的图，称为图G相对于完全图的补图，记为$\overline{G}$ **子图**：包含一部分或全部的点和边 **生成子图**：包含全部点，包含部分或全部的边 相对于子图的补图 **同构** 1. 结点数相同 2. 边数相同 3. 对应结点的度数相等 **路** **回路** **迹**：路中各边均不相同 **通路**：路中各结点各不相同 **圈**：闭合路中，各个结点均不相同 **最短路长度上界**: 在具有$n$个结点的图中，如果从结点$v_j$到$v_k$存在一条路，则从结点$v_j$到$v_k$必存在一条不多于$n-1$条边的路 **连通**：在*无向图*$G$中，如果从结点$u$到$v$存在一条路，则称结点$u$和$v$是相通的 **连通分支** **连通分支数** W(G) **连通图**：若图$G$只有一个连通分支，则称图$G$为连通图 **点割集**：若有一个结点集$V_1\subseteq V$，删除该结点集合中的所有结点后，所得的子图是不连通的，而删除这个集合的任一真子集后，所得的子图仍然是连通的，这样的集合叫做点割集 **割点**：一个结点构成点割集，称该结点为割点 *非完全图*$G$的**点连通度**$k(G)$：产生一个不连通图所要删除结点的最少数目 > 非连通图的连通度为0 > 存在割点的连通图的连通度为1 > 完全图$K_n$的点连通度：$k(K_n) = n-1$ **边割集**：若有一个边集$E_1\subseteq E$，删除该边集合中的所有边后，所得的子图是不连通的，而删除这个集合的任一真子集后，所得的子图仍然是连通的，这样的集合叫做边割集 **割边**：一条边构成边割集，称该边为割边 *非平凡图*$G$的**边连通度**$\lambda(G)$：产生一个不连通图所要删除边的最少数目 > 平凡图的边连通度为0 > 非连通图的边连通度为0 **点连通度、边连通度与最小度数不等式**: $G$为*无向图*，则 $ k(G)\leqslant \lambda(G)\leqslant \delta(G)$ **割点判定定理**: 一个连通*无向图*$G$中的结点$v$是割点的充分必要条件是存在两个结点$u$和$w$，使得连接结点$u$和$w$的每一条路都经过$v$ **有向图的连通性** **可达性**：*有向图*$G$中，如果从结点$u$到$v$有一条路，则称$u$可达$v$ **距离**：如果$u$可达$v$，则$u,v$之间的**最短路的长度**，称为$u, v$之间的距离$d$ $u$不可达$v$，则$d = \infty$ 一般情况下， $d \neq d$ **直径**：距离的最大值称为图$G$的直径 **可达性**是有向图结点集上的二元关系，它是**自反**和**传递**的，一般是不对称的 *简单有向图*$G$中， **单侧连通**：如果图$G$任何一对结点间，至少从一个结点到另一个结点间可达，则称该图是单侧连通的 **强连通**：如果图$G$中任何一对结点间相互可达，则称图$G$是强连通的 **弱连通**：如果图$G$中略去边的方向，视为无向图是连通的，则称图$G$是弱连通的 **强连通有向图的闭合路判定**: 一个*有向图*是强连通的，当且仅当$G$中有一个回路，它至少包含每个结点各一次 *简单有向图*$G$中， **强分图**：具有强连通性的极大子图（如果G’是强分图，G’具有强连通性，则任何包含G’的子图都不再具备强连通性） **单侧分图**：具有单侧连通性的极大子图 **弱分图**：具有弱连通性的极大子图 **强连通分量的唯一性**: 在*有向图*$G$中，它的每一个结点位于且只位于一个强分图中 **邻接矩阵** > 无向图的邻接矩阵对称 **邻接矩阵的应用：** $计算结点v_i与v_j之间长度为l的路的数目$ 设邻接矩阵为$A(G)$ **邻接矩阵幂的路计数定理**: 计算$[A(G)]^l$，则元素$a_{ij}$为$v_i$与$v_j$之间长度为$l$的路的数目 **可达性矩阵-简单有向图** $v_i与v_j之间存在路 = 1$ $v_i与v_j之间不存在路 = 0$ 由图的邻接矩阵可以通过三种方法算出它的可达性矩阵 **Warshall算法** **关联矩阵-无向图** $v_i与e_j关联 = 1$ $v_i与e_j不关联 = 0$ **完全关联矩阵-简单有向图** $v_i是e_j的起点 = 1$ $v_i是e_j的终点 = -1$ $v_i与e_j不关联 = 0$ **结点的合并** 在关联矩阵里，记$v_i$对应的行为$\vec{v_i}$，规定运算： $\vec{v_i}\oplus\vec{v_j}$ 1. 对于*有向图*，$\oplus$是普通加法 2. 对于*无向图*，$\oplus$是对应分量的**模2加法** 运算目的是把$v_i$与$v_j$合并，而且如果合并后得到了自回路，则要删去 **完全关联矩阵秩定理**: 设连通图$G$有$r$个结点，则其完全关联矩阵的秩为$r-1$，即$\mathbb{rank} M(G) = r-1$ > 秩是矩阵非零子式的最高阶阶数 > **推论**：设图$G$有$r$个结点，$w$个最大连通子图，则图G的完全关联矩阵的秩为$r-w$ 图$G$*无孤立结点* **欧拉路**：若存在一条路，经过图中每**边**一次且仅一次，则称该路为欧拉路 **欧拉回路**：若存在一条回路，经过图中每**边**一次仅一次 **欧拉图**：具有欧拉回路的图叫做欧拉图 **无向图欧拉路判定定理**: *无向图*$G$有一条**欧拉路**，当且仅当$G$连通，且有零个或两个**奇数度**结点 **无向图欧拉回路判定定理**：*无向图*$G$具有一条**欧拉回路**，当且仅当$G$连通，且所有结点度数皆为**偶数** **单向欧拉路（回路）**：经过有向图中每边一次仅一次的单向路（回路），称为单向欧拉路（回路） **Theorem**: 1. *有向图*$G$具有一条**单向欧拉回路**，当且仅当$G$连通，且每个结点的入度 = 出度 2. *有向图*$G$具有一条**单向欧拉路**，当且仅当$G$连通，且除两个结点之外，每个结点的入度 = 出度，而这两个结点，一个结点的入度比出度大1，另一个结点的入度比出度小1 给定图$G$ **汉密尔顿路**：经过图中每个**结点**一次仅一次的路，称为汉密尔顿路 **汉密尔顿回路**：经过图中每个**结点**一次仅一次的回路，称为汉密尔顿回路 **汉密尔顿图**：具有汉密尔顿路的图叫做汉密尔顿图 **Theorem**： 若无向图$G = $是汉密尔顿图，任意$S\subseteq V$, 则 $W(G-S)\leqslant |S|$ 其中$W(G-S)$表示$G$中删除$S$后所得子图$G-S$的连通分支数 > 这只是汉密尔顿图的一个**必要条件** > 图$G$是汉密尔顿图，则$G$满足这个条件 > 满足这个条件的图**不一定**是汉密尔顿图 > 彼得森图(Peterson)满足这个条件，但它不是汉密尔顿图 **判断一个图不是汉密尔顿图** > 若图$G$不满足此定理，则$G$不是汉密尔顿图 **Theorem**: 设$G$是具有$n$个结点的简单图，如果图中每对结点度数之和大于或等于$n-1$，则$G$中存在一条汉密尔顿路 **Theorem(Dirac)**: 设$G$是具有$n$个结点的无向简单图，$n\geqslant 3$，如果$G$中每个结点的度都至少为$\frac{n}{2}$，则在G中存在一条汉密尔顿回路，即G是汉密尔顿图 **Theorem(Ore)**: 设$G$是具有$n$个结点的无向简单图，$n\geqslant 3$，如果$G$中任一一对结点度数之和大于等于n，则在G中存在一条汉密尔顿回路，即G是汉密尔顿图 > 这只是汉密尔顿图的一个充分条件，不满足此定理的图也可能是汉密尔顿图 > ![]() --- **平面图**：能画在一个平面上且任何两边除端点外互不相交的图，称为平面图 **平面表示**：将平面图$G$的每个边不交叉的图画在一个平面上，称为图$G$的一个平面表示 **面**：平面图$G$的某个平面表示，将$G$所在的平面划分成若干区域，每个区域叫图G的一个面 **边界**：包围每个面的边，称为该面的边界 **面的次数**：边界上边的条数，叫做该面的次数，面$r$的次数记作$deg(r)$ **平面图面次数求和公式**: 一个有限平面图，面的次数之和等于其边数的两倍 $\sum\limits_r deg(r_i) = 2|E|$ **欧拉公式（Euler Formula）**: 设$G$是连通平面图，有$v$个顶点，$e$条边，$r$个面，则$v-e+r = 2$ **简单平面图边数上界定理**: 设$G$是有$v$个结点，$e$条边的连通简单平面图，且$v\geqslant 3$，则$e\leqslant 3v-6$ > 定理给出了结点数大于等于3的连通简单平面图应满足的必要条件，可以用来判断某些图不是平面图 **面次数至少为4的平面图边数上界**: 设$G$是有$v$个结点，$e$条边的连通平面图，且$G$的各面的次数大于等于4，则$e\leqslant 2v-4$ > 定理给出了各面次数大于等于4的连通平面图应满足的必要条件，可以用来判断某些图不是平面图 ** 对偶图** ![Screenshot 2025-01-09 at 20.58.15]() **自对偶图** ![]() **着色** 图$G$的正常着色是指对$G$的每个结点指定一种颜色，使邻接的结点具有不同的颜色 > 如果图$G$着色用了$n$种颜色，则称图$G$是$n-$色的 > 图$G$着色所需的最少颜色数称为$G$的着色数，记作$\chi(G)$ **Welch Powell 着色法** ![]() **完全图色数公式**: 有$n$个结点的完全图$K_n$，$\chi(K_n) = n$ **Theorem(五色定理)**: 任意平面图最多是5-色的 **Theorem(四色定理)**: 任意平面图最多是4-色的