图论基础讲解

目录

1. 图的基本概念

1.1 结点的度

1.2 完全图、补图

2. 图的连通性

2.1 通路与回路

2.2 结点的连通

2.3 割点与割边

3. 图的矩阵表示

3.1 无向图邻接矩阵

4. 欧拉图和哈密顿图

4.1 欧拉图

4.2 哈密顿图

5. 树

5.1 树

---

1. 图的基本概念

1.1 结点的度

（1）结点度数：设G为一个无向图，其中一个结点为v，与v关联的边的条数，称为度数，简称度。（注意：在无向图中，一个自调环，是两度）

（2）握手定理（无向图）：在无向图G中，在计算各结点度数之和时，每条边都能提供两度，所以m条边共有2m度。

（3）可图化：一个非负整数序列中，奇度数结点的个数不为奇数，则该序列可图化。

（4）可简单图化：如果一个序列可图化，且 序列中的最大度数≤序列的结点个数-1，则该序列可以简单图化。

例：判断下列序列哪些可图化，哪些可简单图化。

①（5，5，4，4，2，1）

②（5，4，3，2，2）

③（3，3，3，1）

④（4，4，3，3，2，2）

解：①的奇结点个数为3，不可图化。

②最大度数为5，结点个数-1为4，5＞4，可图化，不可简单图化。

③最大度数为3，结点个数-1为3，3≤3，可图化，可简单图化。

④最大度数为4，结点个数-1为5，4≤5，可图化，可简单图化。

1.2 完全图、补图

（1）完全图：设G为无向简单图，如果任意两个结点之间都有边相连，则称G为完全图。n个结点的无向完全图Kn的边数为Cn2 = nn-12。

例：

（2）补图：能使图G成为完全图而添加的边，由这些添加的边所组成的图，称为补图，记作G。

例：画出图G的补图。

图G   补图G

2. 图的连通性

2.1 通路与回路

（1）通路：无向图G中，如果一个结点v0能到达另一个结点vn ，则称这是一条通路。

（2）回路：如果通路的起点和终点是同一个结点，则称为回路。

2.2 结点的连通

（1）连通：如果无向图G中，存在从结点v0到vn的通路，则称v0与vn是连通的。

（2）连通图：如果无向图G中的任意两个结点都是连通的，则称为连通图。

2.3 割点与割边

对一个连通图在删去一个点或一条边后，使该连通图不再连通。

例1：对下面连通图进行割点和割边。

解：在去掉v3或v5后，原图不再连通，所以割点为v3和v5。

在去掉e5或e6后，原图不再连通，所以割点为e5和e6。

例2：对下面连通图进行割点和割边。

解：在去掉v4或v6后，原图不再连通，所以割点为v4和v6。

在去掉e5或e6后，原图不再连通，所以割点为e5和e6。

3. 图的矩阵表示

3.1 无向图邻接矩阵

在矩阵中用数字表示每个结点与是否与其它结点相连，相连就为1，不相连就为0。矩阵的每一行就是一个结点。

例：已知邻接矩阵，画出对应的无向图。

邻接矩阵  对应的无向图

4. 欧拉图和哈密顿图

4.1 欧拉图

（1）经过图G所有边一次且仅一次的回路，称为欧拉回路，存在欧拉回路的图称为欧拉图。欧拉图的奇结点的个数为0。（奇结点：度数为奇数的结点）

（2）经过图G所有边一次且仅一次的通路，称为欧拉路，存在欧拉路且无欧拉回路的图称为半欧拉图。半欧拉图的奇结点个数为2。

注：①奇结点个数为0和2以外的，都不是欧拉图或半欧拉图。

②平凡图（只有一个点的图）是欧拉图。

例：判断下面哪些图是欧拉图，哪些是半欧拉图。

解：图1和图2奇结点的个数为0，是欧拉图。

图3奇结点的个数为2，是半欧拉图。

图3奇结点的个数为4，既不是欧拉图，也不是半欧拉图。

4.2 哈密顿图

（1）经过图G每个结点一次且仅一次的回路，称为哈密顿回路，存在哈密顿回路的图称为哈密顿图。

（2）经过图G每个结点一次且仅一次的通路，称为哈密顿路，存在哈密顿路且无哈密顿回路的图称为半哈密顿图。

注：①平凡图是哈密顿图。

②欧拉图看边，哈密顿图只看结点。

例：判断下面哪些图是哈密顿图，哪些是半哈密顿图。

解：图1和图2都能把所有结点连成回路，是哈密顿图。

图3能连通所有结点，但不能连成回路，是半哈密顿图。

图4不能连通所有结点，既不是哈密顿图，也不是半哈密顿图。

5. 树

5.1 树

（1）一个连通且无回路的无向图，称为一颗树。

（2）在树中，度数为1的结点称为树叶。

（3）在树中，边数m = 结点数n - 1。

例1：该树有6个结点，则边数为5。

例2：已知无向树T中，有1个3度结点，2个2度结点，其余结点全是树叶，画出对应的无向树，并求树叶数。

解：对应的无向树为由图可以看出有3个树叶。

（4）最小生成树：在一个带权图G的所有生成树中，树权最小的那颗生成树，称为G的最小生成树。

（5）Kruskal算法（避圈法/加边法）：

①先构造一个只有n个结点的子图。

②从原图中权值最小的边开始，如果加上它后，不会使子图中产生回路，则在子图中加上这条边。如果会产生回路，就跳过该边，看下一条边。

③一直重复第二步，直到加上n-1条边为止。

例：求图T的最小生成树，并求出权和。

解：图中结点n为8，所以要加上7条边。（分步演示）

①  ②  ③  ④

⑤  ⑥  ⑦

权和W（T）=1+2+3+5+6+8+9=34