原文筆記

第十二章总线索

Last Updated · 2026-07-14在 GitHub 編集 ↗

图论研究的是：

\boxed{\text{对象之间的连接关系}}

比如：

城市之间有没有路；
人和人之间是否认识；
程序是否等待某个资源；
任务之间谁必须先完成；
两个点之间最短路线是多少。

图的基本结构就是：

G=\langle V,E,\varphi\rangle

其中：

符号	含义
$V$	顶点集
$E$	边集
$\varphi$	关联函数，说明每条边连接哪些顶点

最直观一句话：

\boxed{\text{顶点表示对象，边表示对象之间的关系}}

12.1 图与子图

一、图的定义

图通常记作：

G=\langle V,E,\varphi\rangle

其中：

$V$ 是非空有限集合，元素叫顶点；
$E$ 是有限集合，元素叫边；
$\varphi$ 把每条边对应到某个顶点对。

如果边没有方向，叫无向图。

如果边有方向，叫有向图。

二、无向边与有向边

1. 无向边

无向边连接两个顶点，不分起点终点。

如果边 $e$ 连接 $u,v$ ，可以写作：

e=(u,v)

或者理解成无序对：

{u,v}

例如：

u-v

表示 $u$ 和 $v$ 相连。

2. 有向边

有向边有方向，有起点和终点。

如果边从 $u$ 指向 $v$ ，记作：

e=\langle u,v\rangle

其中：

$u$ ：起点；
$v$ ：终点。

画图时用箭头表示：

u\to v

三、图的基本术语

1. 顶点

图中的点叫顶点，也叫结点。

例如：

V={v_1,v_2,v_3}

表示图有三个顶点。

2. 边

图中连接顶点的线叫边。

无向图的边没有方向。

有向图的边有方向。

3. 关联

如果边 $e$ 连接顶点 $u$ 和 $v$ ，则称：

边 $e$ 与顶点 $u,v$ 关联。

也说 $u,v$ 是边 $e$ 的端点。

4. 邻接顶点

如果两个顶点之间有边相连，就称它们是邻接顶点。

例如：

(u,v)\in E

则 $u$ 和 $v$ 邻接。

5. 邻接边

如果两条边有公共端点，则称它们是邻接边。

比如：

e_1=(u,v),\quad e_2=(v,w)

它们都经过 $v$ ，所以 $e_1,e_2$ 邻接。

6. 自环

一条边的两个端点相同，叫自环。

形式：

e=(v,v)

画图时就是顶点上绕一圈的边。

7. 重边

如果两个顶点之间有多条边相连，这些边叫重边。

例如：

e_1=(u,v),\quad e_2=(u,v)

且 $e_1\neq e_2$ ，它们就是重边。

8. 孤立点

如果某个顶点没有任何边与它关联，则称它是孤立点。

孤立点的度为 0。

四、图的分类

1. 零图

只含一些孤立点、没有边的图，叫零图。

也就是：

E=\varnothing

2. 平凡图

只有一个孤立顶点的图，叫平凡图。

3. 多重图

含有重边的图叫多重图。

教材里含重边的图称为多重边图。

4. 简单图

不含自环，也不含重边的图，叫简单图。

\boxed{\text{简单图 = 无自环 + 无重边}}

这是后面讨论很多定理时最常用的图。

5. 完全图

如果一个简单图中任意两个不同顶点之间都有边相连，则叫完全图。

含 $n$ 个顶点的无向完全图记作：

K_n

无向完全图的边数是：

\boxed{\frac{n(n-1)}{2}}

因为 $n$ 个顶点中任意选两个顶点连一条边：

C_n^2=\frac{n(n-1)}{2}

如果是有向完全图，每一对不同顶点之间有两个相反方向的有向边，则边数是：

\boxed{n(n-1)}

五、顶点的度

1. 无向图中的度

在无向图中，一个顶点 $v$ 的度，记作：

d(v)

表示与 $v$ 关联的边数。

注意：

\boxed{\text{自环对度的贡献是 }2}

因为自环的两个端点都在同一个顶点上。

2. 有向图中的出度和入度

在有向图中：

出度

从顶点 $v$ 发出的边数叫出度，记作：

d^+(v)

入度

进入顶点 $v$ 的边数叫入度，记作：

d^-(v)

总度

d(v)=d^+(v)+d^-(v)

3. 奇顶点和偶顶点

如果：

d(v)

是奇数，则 $v$ 是奇顶点。

如果：

d(v)

是偶数，则 $v$ 是偶顶点。

4. 正则图

如果无向图中所有顶点的度都等于 $k$ ，则称它是 $k$ 正则图。

例如：

所有顶点度都是 2：2 正则图；
所有顶点度都是 3：3 正则图。

六、握手定理

这是本章最重要公式之一。

设无向图 $G=\langle V,E\rangle$ ，边数为 $m$ ，则：

\boxed{\sum_{v\in V}d(v)=2m}

意思是：

所有顶点度数之和 = 边数的 2 倍。

为什么？

因为每条普通边贡献两个端点，自环也贡献 2。

推论：奇度顶点个数一定为偶数

因为：

\sum_{v\in V}d(v)=2m

一定是偶数。

偶数度顶点加起来还是偶数，所以奇数度顶点的个数必须是偶数。

结论：

\boxed{\text{任意无向图中，奇顶点个数为偶数}}

这条非常常考。

七、子图

设：

G=\langle V,E\rangle,\quad G'=\langle V',E'\rangle

如果：

V'\subseteq V,\quad E'\subseteq E

则 $G'$ 是 $G$ 的子图。

1. 真子图

如果 $G'$ 是 $G$ 的子图，但：

V'\neq V

或：

E'\neq E

则称 $G'$ 是 $G$ 的真子图。

2. 生成子图 / 支撑子图

如果：

V'=V

但：

E'\subseteq E

则称 $G'$ 是 $G$ 的生成子图，也叫支撑子图。

意思是：

顶点全保留，只删一些边。

3. 顶点导出子图

如果取：

V'\subseteq V

并保留 $V'$ 中顶点之间在原图中所有的边，则得到的子图叫顶点导出子图，记作：

G[V']

通俗说：

选一些顶点，把这些顶点之间原来有的边全部保留。

4. 边导出子图

如果取：

E'\subseteq E

并把这些边及其端点组成子图，则叫边导出子图，记作：

G[E']

5. 删除顶点

从图 $G$ 中删去顶点 $v$ ，同时删去与 $v$ 关联的所有边，记作：

G-v

如果删去顶点集合 $V'$ ，记作：

G-V'

6. 删除边

从图中删去边 $e$ ，记作：

G-e

从图中删去边集 $E'$ ，记作：

G-E'

7. 加边

如果在图中加入边 $e$ ，记作：

G+e

八、补图

1. 一般补图思想

补图的意思是：

原图没有的边，在补图里有；原图有的边，在补图里没有。

2. 简单图的补图

设 $G$ 是含 $n$ 个顶点的简单图，则 $G$ 的补图记作：

\overline G

它的顶点集和 $G$ 相同。

并且：

uv\in E(\overline G)

当且仅当：

uv\notin E(G)

也就是说：

G+\overline G=K_n

九、图的同构

1. 定义

两个图 $G$ 和 $G'$ 如果只是“画法不同”，但结构完全一样，就叫同构。

严格说，如果存在一个顶点双射：

f:V(G)\to V(G')

并且保持邻接关系，则称 $G$ 与 $G'$ 同构，记作：

G\cong G'

2. 图同构要保持什么

如果两个图同构，必须保持：

顶点数相同；
边数相同；
度数序列相同；
邻接关系相同；
有向图还要保持方向；
自环、重边数量也要对应。

3. 注意：这些只是必要条件，不一定充分

也就是说：

\text{顶点数相同、边数相同、度数序列相同}

只能说明它们可能同构，不能保证一定同构。

判断不同构时，常用方法是找不变量不同。

例如：

一个有孤立点，另一个没有；
一个有三角形，另一个没有；
一个有自环，另一个没有；
一个连通，另一个不连通。

12.2 路径与循环

这一节研究“能不能从一个顶点走到另一个顶点”。

一、路径

设：

G=\langle V,E\rangle

一个路径可以写成：

\mu=v_0e_1v_1e_2v_2\cdots e_kv_k

意思是：

从 $v_0$ 出发，经过边 $e_1,e_2,\dots,e_k$ ，最后到达 $v_k$ 。

路径长度是边数：

\boxed{k}

1. 路径的起点和终点

在：

\mu=v_0e_1v_1\cdots e_kv_k

中：

$v_0$ ：起点；
$v_k$ ：终点；
$k$ ：路径长度。

2. 简单路径

如果路径中的边互不相同，则称为简单路径。

教材中“简单路径”重点看边不重复。

3. 基本路径 / 通路

如果路径中的顶点互不相同，则称为基本路径，也常叫通路。

顶点不重复自然边也不会重复，所以：

\boxed{\text{基本路径一定是简单路径}}

但简单路径不一定是基本路径。

二、循环 / 回路

如果路径的起点和终点相同：

v_0=v_k

则称为循环，也常叫回路。

1. 简单循环

如果循环中的边互不相同，则称为简单循环。

2. 基本循环

如果除了起点和终点相同之外，其余顶点互不相同，则称为基本循环。

3. 基本循环与简单循环关系

\boxed{\text{基本循环一定是简单循环}}

但简单循环不一定是基本循环。

三、路径长度定理

设 $G$ 是含 $n$ 个顶点的有向图。

1. 基本路径长度

任意基本路径的长度最多为：

\boxed{n-1}

因为基本路径不能重复顶点。

如果有 $n$ 个顶点，最多经过 $n$ 个顶点，因此最多有 $n-1$ 条边。

2. 基本循环长度

任意基本循环的长度最多为：

\boxed{n}

因为基本循环除了起点终点相同外，其他顶点不重复。

四、可达性

1. 可达

在有向图中，如果从顶点 $u$ 到顶点 $v$ 存在路径，则称：

v

从：

u

可达。

也可以说：

u\to v

可达。

2. 顶点到自身可达

规定任意顶点到自己都是可达的。

所以可达关系具有自反性。

3. 可达关系具有传递性

如果：

u

可达：

v

并且：

v

可达：

w

则：

u

可达：

w

所以可达关系是自反、传递的。

五、距离

在有向图中，两个顶点 $v_i,v_j$ 的距离记作：

d[v_i,v_j]

定义如下：

如果 $i=j$ ，则：

d[v_i,v_j]=0

如果 $v_j$ 从 $v_i$ 不可达，则：

d[v_i,v_j]=\infty

如果 $v_j$ 从 $v_i$ 可达，则：

d[v_i,v_j]

等于从 $v_i$ 到 $v_j$ 的最短路径长度。

注意：有向图距离不一定对称

一般：

d[v_i,v_j]\neq d[v_j,v_i]

因为有向边有方向。

六、无向图的连通性

1. 连通图

设 $G$ 是无向图。

如果任意两个顶点之间都有路径相连，则称 $G$ 是连通图。

2. 连通分支

如果无向图不连通，可以分成若干个极大连通子图。

这些极大连通子图叫连通分支。

连通分支个数记作：

\omega(G)

如果 $G$ 是连通图，则：

\omega(G)=1

3. 割边 / 桥

如果删去某条边后，图的连通分支数增加，则这条边叫割边，也叫桥。

即：

\omega(G-e)>\omega(G)

则 $e$ 是割边。

直观理解：

一删这条边，图就更散了。

4. 割点

如果删去某个顶点以及与它关联的边后，图的连通分支数增加，则这个顶点叫割点。

即：

\omega(G-v)>\omega(G)

则 $v$ 是割点。

七、有向图的连通性

有向图比无向图复杂，教材分三种：

1. 强连通

如果任意两个顶点 $u,v$ ，都有：

u\text{ 可达 }v

并且：

v\text{ 可达 }u

则称有向图是强连通图。

通俗说：

任意两个点之间都能双向到达。

2. 单向连通

如果任意两个顶点 $u,v$ ，至少有一个方向可达：

u\text{ 可达 }v

或：

v\text{ 可达 }u

则称为单向连通图。

3. 弱连通

如果把有向图中所有边的方向去掉后，得到的无向图是连通图，则称原有向图是弱连通图。

4. 三者关系

\boxed{\text{强连通} \Rightarrow \text{单向连通} \Rightarrow \text{弱连通}}

反过来一般不成立。

也就是说：

强连通最强；
单向连通居中；
弱连通最弱。

八、极大连通子图

1. 强分图

有向图中的极大强连通子图叫强分图。

2. 单向分图

有向图中的极大单向连通子图叫单向分图。

3. 弱分图

有向图中的极大弱连通子图叫弱分图。

4. 常见性质

对于有向图：

每个顶点恰好属于一个强分图；
每个顶点和每条边至少属于一个单向分图；
每个顶点和每条边恰好属于一个弱分图。

12.3 图的矩阵表示

这一节很重要，因为它把图变成矩阵，方便计算机处理。

主要有：

关联矩阵；
邻接矩阵；
可达矩阵；
距离矩阵。

一、关联矩阵

关联矩阵描述的是：

\boxed{\text{顶点和边之间的关系}}

设：

V={v_1,v_2,\dots,v_n}

E={e_1,e_2,\dots,e_m}

关联矩阵是一个：

n\times m

矩阵。

行对应顶点，列对应边。

1. 无向图关联矩阵

无向图中：

F=(f_{ij})_{n\times m}

其中：

f_{ij}= \begin{cases} 0,& e_j\text{ 不关联 }v_i\ 1,& e_j\text{ 是非自环且关联 }v_i\ 2,& e_j\text{ 是自环且关联 }v_i \end{cases}

解释：

普通边连接两个顶点，所以对应两行各有一个 1；
自环在一个顶点上贡献 2。

2. 无向图关联矩阵性质

每一列元素和为 2；
每一行元素和等于对应顶点的度；
全 0 行对应孤立点；
重边对应相同的列。

3. 有向图关联矩阵

有向图中，关联矩阵要体现方向。

一般按教材定义：

f_{ij}= \begin{cases} 0,& e_j\text{ 不关联 }v_i\ 1,& e_j\text{ 以 }v_i\text{ 为起点}\ -1,& e_j\text{ 以 }v_i\text{ 为终点}\ -2,& e_j\text{ 是关联 }v_i\text{ 的自环} \end{cases}

不同教材对有向自环的矩阵记法可能略有差异，但普通有向边最重要的是：

\boxed{\text{起点记 }1,\text{ 终点记 }-1}

二、邻接矩阵

邻接矩阵描述的是：

\boxed{\text{顶点和顶点之间的连接关系}}

设：

V={v_1,v_2,\dots,v_n}

邻接矩阵是：

n\times n

矩阵。

1. 有向图邻接矩阵

有向图中：

A=(a_{ij})_{n\times n}

其中：

a_{ij}=k

表示从 $v_i$ 到 $v_j$ 的有向边有 $k$ 条。

如果没有边，则：

a_{ij}=0

2. 无向图邻接矩阵

无向图中：

a_{ij}=k

表示 $v_i$ 和 $v_j$ 之间有 $k$ 条边。

3. 简单图邻接矩阵特点

如果 $G$ 是简单图，则：

主对角线元素全为 0；
每个元素只能是 0 或 1；
无向简单图的邻接矩阵是对称矩阵。

即：

A=A^T

4. 用邻接矩阵求度

对于有向图：

出度

d^+(v_i)=\sum_{j=1}^{n}a_{ij}

也就是第 $i$ 行元素之和。

入度

d^-(v_i)=\sum_{j=1}^{n}a_{ji}

也就是第 $i$ 列元素之和。

总度

d(v_i)=d^+(v_i)+d^-(v_i)

三、邻接矩阵的幂

这是很重要的计算结论。

设 $A$ 是无重边有向图的邻接矩阵。

那么：

A^m

中第 $i,j$ 个元素表示：

\boxed{\text{从 }v_i\text{ 到 }v_j\text{ 的长度为 }m\text{ 的路径条数}}

如果：

i=j

则表示从 $v_i$ 出发又回到 $v_i$ 的长度为 $m$ 的循环条数。

例子理解

如果：

(A^3)_{24}=5

表示：

从 $v_2$ 到 $v_4$ 的长度为 3 的路径有 5 条。

四、可达矩阵

可达矩阵只关心：

能不能到达。

不关心有几条路径，也不关心路径长度。

设有向图 $G$ 的可达矩阵为：

P=(p_{ij})

其中：

p_{ij}= \begin{cases} 1,& i=j\text{ 或 }v_j\text{ 从 }v_i\text{ 可达}\ 0,& v_j\text{ 从 }v_i\text{ 不可达} \end{cases}

1. 可达矩阵的含义

如果：

p_{ij}=1

表示：

v_i\to v_j

可达。

如果：

p_{ij}=0

表示不可达。

2. 用邻接矩阵求可达矩阵

如果有 $n$ 个顶点，则只需考虑长度不超过 $n-1$ 的基本路径。

所以可以用布尔矩阵运算：

P=I\lor A\lor A^{(2)}\lor\cdots\lor A^{(n-1)}

其中：

$I$ ：单位矩阵，表示自己到自己可达；
$A^{(k)}$ ：布尔意义下的 $k$ 次幂；
$\lor$ ：布尔或。

也可以先求普通幂：

A+A^2+\cdots+A^{n-1}

再把非零元素改成 1。

3. 强分图与可达矩阵

如果有可达矩阵 $P$ ，那么：

P\land P^T

可以表示互相可达关系。

如果：

p_{ij}=1

且：

p_{ji}=1

说明：

v_i

和：

v_j

互相可达，可能属于同一个强分图。

五、距离矩阵

距离矩阵记录的是两个顶点之间最短距离。

设：

D=(d_{ij})

其中：

d_{ij}=d[v_i,v_j]

如果不可达，则：

d_{ij}=\infty

如果：

i=j

则：

d_{ii}=0

12.4 应用举例

这一节主要讲图论应用。

教材里有几类：均分问题、最短路径问题、最优路径问题、关键路径问题。

一、均分问题

这种题一般把“状态”看成顶点，把“一步操作”看成边。

比如三个容器倒水问题：

每一种水量分布是一个状态；
从一种状态倒水到另一种状态，就是一条边；
问能否均分，就是问图中是否存在从初始状态到目标状态的路径。

核心思想：

\boxed{\text{状态 = 顶点，操作 = 边，求解 = 找路径}}

二、赋权图

1. 定义

如果图的每条边都赋有一个数值，称为赋权图，也叫带权图。

记边 $e$ 的权为：

W(e)

权可以表示：

距离；
时间；
费用；
风险；
容量；
损耗。

2. 路径长度

在赋权图中，一条路径的长度不是边数，而是路径上所有边权之和。

如果路径：

\mu=e_1e_2\cdots e_k

则：

l(\mu)=W(e_1)+W(e_2)+\cdots+W(e_k)

三、Dijkstra 算法

Dijkstra 算法用于求：

\boxed{\text{从一个源点到其他顶点的最短路径}}

通常要求边权非负。

1. 算法思想

把顶点分成两类：

集合	含义
$P$	已确定最短路径的顶点
$T$	暂时未确定的顶点

初始时：

P={v_0}

然后不断从 $T$ 中选出当前距离最小的顶点，加入 $P$ ，并更新它的邻接点距离。

2. 算法步骤

设源点为 $v_0$ 。

第一步：初始化

d(v_0)=0

对于其他顶点：

d(v_i)= \begin{cases} W(v_0,v_i),& v_0\text{ 与 }v_i\text{ 有边}\ \infty,& v_0\text{ 与 }v_i\text{ 无边} \end{cases}

第二步：选最小

从未确定顶点中选 $d$ 值最小的顶点 $v_k$ ，加入 $P$ 。

第三步：更新

对 $v_k$ 的邻接顶点 $v_i$ ，若：

d(v_k)+W(v_k,v_i)<d(v_i)

则更新：

d(v_i)=d(v_k)+W(v_k,v_i)

第四步：重复

一直重复，直到目标点被加入 $P$ ，或者所有顶点都加入 $P$ 。

3. 适用场景

Dijkstra 适合：

单源最短路径；
非负权图；
地图导航；
网络路由；
成本最小问题。

四、Floyd 算法

Floyd 算法用于求：

\boxed{\text{任意两点之间的最短路径}}

也叫全源最短路径算法。

1. 初始矩阵

设初始距离矩阵为：

D^{(0)}=(d_{ij}^{(0)})

其中：

d_{ij}^{(0)}

表示边 $v_i\to v_j$ 的权。

如果没有边：

d_{ij}^{(0)}=\infty

如果：

i=j

则：

d_{ii}^{(0)}=0

2. 核心更新公式

Floyd 算法的核心是：

\boxed{ d_{ij}^{(k)} = \min\left(d_{ij}^{(k-1)},\ d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\right) }

意思是：

从 $i$ 到 $j$ 的最短路，要么不经过 $k$ ，要么经过 $k$ 。

如果经过 $k$ 更短，就更新。

3. 算法过程

依次令：

k=1,2,\dots,n

逐步允许路径经过更多中间顶点。

最终：

D^{(n)}

就是所有顶点对之间的最短距离矩阵。

4. Dijkstra 与 Floyd 区别

算法	作用
Dijkstra	求一个源点到其他点的最短路径
Floyd	求任意两点之间的最短路径

一句话：

\boxed{\text{Dijkstra 是单源，Floyd 是全源}}

五、决策图与最优路径

1. 决策图

决策图是一类有向赋权图。

顶点分层：

V_1,V_2,\dots,V_s

边只从前一层指向后一层。

这种图常用来表示多阶段决策问题。

2. 最优路径

从初始顶点到终止顶点的路径中，权值总和最小的路径叫最优路径。

求法通常是动态规划思想：

从后往前，逐层计算每个顶点到终点的最优值。

3. 核心思想

如果从 $v$ 出发，可以走到若干后继顶点 $u_1,u_2,\dots,u_k$ ，则：

F(v)=\min_i{W(v,u_i)+F(u_i)}

意思是：

从当前点出发的最优值 = 走一条边的代价 + 后面最优值的最小值。

六、PERT 图与关键路径

PERT 图用于工程项目管理。

1. PERT 图的特点

PERT 图是一种有向无环图。

顶点表示事件；
边表示任务；
边权表示完成任务所需时间；
有一个源点；
有一个汇点。

2. 最早完成时间

顶点 $v_i$ 的最早完成时间记作：

TE(v_i)

表示在不违反先后顺序的情况下，事件 $v_i$ 最早什么时候能发生。

通常：

TE(v_1)=0

对其他点：

TE(v_i)=\max{TE(v_j)+W(v_j,v_i)}

其中 $v_j$ 是 $v_i$ 的前驱顶点。

3. 最迟完成时间

顶点 $v_i$ 的最迟完成时间记作：

TL(v_i)

表示在不延误总工期的情况下，事件 $v_i$ 最晚什么时候必须发生。

终点：

TL(v_n)=TE(v_n)

对其他点：

TL(v_i)=\min{TL(v_j)-W(v_i,v_j)}

其中 $v_j$ 是 $v_i$ 的后继顶点。

4. 关键路径

如果某条路径上的顶点都满足：

TE(v)=TL(v)

则这条路径可能是关键路径。

关键路径的长度就是整个工程的最短完成时间。

5. 关键路径的意义

关键路径上的任务不能延误。

只要关键路径上任一任务延误，整个项目就会延误。

非关键路径上的任务通常有一定机动时间。

第十二章核心公式总结

知识点	公式 / 结论
无向完全图边数	$\frac{n(n-1)}{2}$
有向完全图边数	$n(n-1)$
握手定理	$\sum_{v\in V}d(v)=2m$
奇顶点个数	一定是偶数
基本路径最大长度	$n-1$
基本循环最大长度	$n$
有向图出度	$d^+(v_i)=\sum_j a_{ij}$
有向图入度	$d^-(v_i)=\sum_j a_{ji}$
邻接矩阵幂	$(A^m)_{ij}$ 表示长度为 $m$ 的路径条数
可达矩阵	$P=I\lor A\lor A^{(2)}\lor\cdots\lor A^{(n-1)}$
Floyd 更新	$d_{ij}^{(k)}=\min(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)})$
路径权长	$l(\mu)=\sum W(e_i)$

第十二章常考题型

题型一：判断图的类型

常问：

是无向图还是有向图？
是简单图还是多重图？
有没有自环？
有没有重边？
是不是完全图？
是不是正则图？

口诀：

\boxed{\text{简单图：无自环、无重边}}

\boxed{\text{完全图：任意两点都有边}}

题型二：求顶点的度

无向图中：

普通边贡献 1；
自环贡献 2。

有向图中：

出边算出度；
入边算入度；
总度 = 出度 + 入度。

题型三：用握手定理判断图是否存在

给出度数序列，问是否可能构成无向图。

先看：

\sum d(v)

是否为偶数。

如果是奇数，必不可能。

还要看是否违反简单图条件，比如某个顶点度数超过：

n-1

题型四：判断子图

要看：

V'\subseteq V,\quad E'\subseteq E

生成子图看顶点是否全部保留。

导出子图看是否保留了对应的所有边。

题型五：判断图同构

先查：

顶点数；
边数；
度数序列；
是否连通；
是否有自环、重边；
是否有三角形、孤立点、割点等结构。

如果这些不同，肯定不同构。

如果都相同，还要进一步找顶点对应关系。

题型六：判断连通性

无向图：

\boxed{\text{任意两点有路径} \Rightarrow \text{连通}}

有向图：

\boxed{\text{强连通} \Rightarrow \text{单向连通} \Rightarrow \text{弱连通}}

题型七：求邻接矩阵、关联矩阵

邻接矩阵：

n\times n

表示顶点和顶点关系。

关联矩阵：

n\times m

表示顶点和边关系。

题型八：用矩阵求路径条数

如果题目问：

“从 $v_i$ 到 $v_j$ 长度为 $m$ 的路径有几条？”

就看：

(A^m)_{ij}

题型九：求可达矩阵

用：

P=I\lor A\lor A^{(2)}\lor\cdots\lor A^{(n-1)}

或用 Warshall 类方法。

题型十：最短路径

单源最短路径：

\boxed{\text{Dijkstra}}

任意两点最短路径：

\boxed{\text{Floyd}}

最容易混的点

1. 路径、简单路径、基本路径

名称	要求
路径	可以重复边、重复点
简单路径	边不重复
基本路径	顶点不重复

所以：

\boxed{\text{基本路径一定是简单路径，反之不一定}}

2. 循环、简单循环、基本循环

名称	要求
循环	起点终点相同
简单循环	边不重复
基本循环	除起点终点外，顶点不重复

3. 强连通、单向连通、弱连通

\boxed{\text{强：双向可达}}

\boxed{\text{单向：至少一个方向可达}}

\boxed{\text{弱：去掉方向后连通}}

4. 关联矩阵和邻接矩阵

矩阵	行	列	表示
关联矩阵	顶点	边	顶点与边是否关联
邻接矩阵	顶点	顶点	顶点之间是否有边

5. Dijkstra 和 Floyd

算法	用途
Dijkstra	一个点到其他点
Floyd	所有点到所有点

第十二章一句话总结

第十二章就是图论入门，核心主线是：

\boxed{\text{图是什么}}

\boxed{\text{图有哪些基本结构}}

\boxed{\text{图中能不能走通}}

\boxed{\text{如何用矩阵表示图}}

\boxed{\text{如何解决最短路径和关键路径问题}}

最该背的是：

\boxed{\sum_{v\in V}d(v)=2m}

\boxed{\text{奇度顶点个数一定为偶数}}

\boxed{\text{基本路径长度}\leq n-1}

\boxed{(A^m)_{ij}\text{ 表示从 }v_i\text{ 到 }v_j\text{ 长度为 }m\text{ 的路径数}}

\boxed{\text{强连通}\Rightarrow\text{单向连通}\Rightarrow\text{弱连通}}

\boxed{\text{Dijkstra 求单源最短路，Floyd 求任意两点最短路}}

这章概念很多，但逻辑很清楚：先认识图，再研究走法，再用矩阵计算，最后拿去解路径问题。