图的基本概念

有向图

<V,E>（v = vertex(节点)，e = edge(边)）
平凡图：只有一个 v，没有 e 的图
n 阶图：n 为节点数
邻接：有向边起点邻接到终点，故邻接矩阵中第 n 行为第 n 个节点作为起点，第 n 列为第 n 个节点作为终点，以此统计出度和入度

子图

真子图：与原图不一样就行
生成子图：节点数一样就行，边可以比原图连的少，但不能自己加边
导出子图：可以不用到所有节点，但母图中对应用到节点的边都要保留（或者不用到所有边，但对应的节点保留（废话，你都用到边了，那没节点哪来的边））

补图

补图：设简单无向图 G = (V, E)，其补图记为 Ḡ = (V, Ē)，其中

Ē = { {u, v} | u, v ∈ V，u ≠ v，且 {u, v} ∉ E }
即在保持顶点集不变的情况下，Ḡ 中的边恰好是 G 中不存在的边。

同构图

同构图：设图 G₁ = (V₁, E₁)，G₂ = (V₂, E₂)，若存在一个双射 f : V₁ → V₂，使得

对任意 u, v ∈ V₁，{u, v} ∈ E₁ 当且仅当 {f(u), f(v)} ∈ E₂，

则称 G₁ 与 G₂ 同构，记为 G₁ ≅ G₂。

顶点数相同，边数相同，度数序列相同,但这只是必要条件，充分条件只能用瞪眼法了

连通性

回路与通路

当一条回路中的所有边互不相同时为简单回路，与此相反，有边相同时就是复杂回路，一个由 3 个节点形成的 8 是简单回路
若简单回路中除了初始节点和结束节点相同外，其他节点都不相同，则为初级回路，上文的 8 就不是初级回路

初级回路和简单回路区分:初级想成是最基本的,结构最为合理,故不会出现重复节点;简单说明是回路就行,要求少一点
把上面的回路两个字换成通路就可以得到简单通路,复杂通路,初级通路的定义了

如果 u 到 v 存在通路，则称u和v是连通的,在有向图中称 u 可达 v，若图 G 任意两个顶点都连通，则称 G 是连通图，注意平凡图也是连通图
连通分支:图G相互之间不连通的导出子图
G的连通分支的数量记为p(G)

有向图的连通性

可达与相互可达

设有向图 D = <V, E>，u, v ∈ V。

u 可达 v：
从 u 到 v 存在一条有向通路。
规定：u 到自身总是可达。
u 与 v 相互可达：
u 可达 v 且 v 可达 u。

弱连通

将 D 中所有有向边忽略方向，得到的无向图是连通图。

单向连通

对任意 u, v ∈ V,u 可达 v 或 v 可达 u

强连通

对任意 u, v ∈ V,u 与 v 相互可达

割集

设 G = (V, E) 为连通图。

边割集：设 C ⊆ E，若

图 G − C 不连通；

对任意 e ∈ C，G − (C \ {e}) 仍连通；
则称 C 为 G 的边割集。

即C已经是能够让G不连通的最小边集合了,若C只有一条边e,称e为割边或桥

点割集：设 S ⊆ V，若

图 G − S 不连通或退化为单点图；

对任意 v ∈ S，G − (S \ {v}) 仍连通；
则称 S 为 G 的点割集。

即S已经是能够让G不连通的最小点集合了,若S只有一个顶点v,称v为割点

分量与割

连通分量

无向图的连通分量
无向图 G 的一个极大连通子图称为 G 的一个连通分量（或连通分支）。
- 每一个顶点和每一条边都属于唯一的一个连通分量
- 连通图只有一个连通分量，即其自身
- 非连通无向图有多个连通分量
有向图的强连通分量
有向图中的强连通分量是其极大的强连通子图。
- 强连通图只有一个强连通分量，即其自身
- 非强连通的有向图有多个强连通分量

点割与点连通度

割点集
在连通图 G 中，一个由顶点组成的集合，若从 G 中删除这些顶点后图变得不连通，则称该集合为割点集。
点连通度
点连通度 κ(G) 定义为割点集中顶点数的最小值。
k-点连通图
若图 G 可以在删除 k 个顶点后变得不连通，但不能在删除 k−1 个顶点后变得不连通，则称 G 为 k-点连通图。
特别地，阶数为 n 的完全图是 (n−1)-点连通的。

局部连通度

u, v 的割点集
对一对顶点 u, v，若删除某个顶点集合后使 u 与 v 不连通，则该集合称为 u, v 的割点集。
局部连通度
κ(u, v) 表示使 u 与 v 不连通的最小割点集的大小。
性质
- 在无向图中，κ(u, v) = κ(v, u)
- 除完全图外，κ(G) 等于所有不相邻顶点对 u, v 的 κ(u, v) 的最小值

边割与边连通度

桥
在图 G 中，删除某一条边后图变得不连通，则该边称为桥。
割边集
一个由边组成的集合，若删除这些边后图变得不连通，则称为割边集。
边连通度
λ(G) 表示最小割边集的大小。
局部边连通度
λ(u, v) 表示使 u 与 v 不连通的最小割边集的大小。
k-边连通图
若 λ(G) ≥ k，则称图 G 为 k-边连通图。

连通度之间的关系

设 δ(G) 为图 G 的最小度，则有不等式：

1
2
3


κ(G) ≤ λ(G) ≤ δ(G)

极大连通图
若 κ(G) = δ(G)，称 G 为极大连通图
若 λ(G) = δ(G)，称 G 为极大边连通图

图的矩阵表示

无向图的关联矩阵

定义：设无向图 G = (V, E)，|V| = n，|E| = m。
无向图的关联矩阵是一个 n × m 的 0-1 矩阵 M，其中

M[i][j] = 1或2，当且仅当顶点 v_i 与边 e_j 关联；

否则 M[i][j] = 0。

关联即顶点作为该边的起点或者终点出现次数,当出现自环时关联次数为2
每一列都恰好有两个1或一个2
第i行元素之和为vi的度数,所有元素之和为2m
例：
V = {v1, v2, v3, v4}
E = {
e1 = {v1, v2},
e2 = {v1, v3},
e3 = {v2, v3},
e4 = {v4, v4}
}

	e1	e2	e3	e4
v1	1	1	0	0
v2	1	0	1	0
v3	0	1	1	0
v4	0	0	0	2

有向图的关联矩阵

定义：设无环有向图 G = (V, E)，|V| = n，|E| = m。
有向图的关联矩阵是一个 n × m 的矩阵 M，其中

M[i][j] = -1，若边 e_j 从 v_i 出发；

M[i][j] = 1，若边 e_j 指向 v_i；

否则 M[i][j] = 0。

每一列都有一个-1和1

例：

V = {v1, v2, v3, v4}
E = {
e1: v1 → v2,
e2: v1 → v3,
e3: v2 → v4,
e4: v3 → v4
}

	e1	e2	e3	e4
v1	-1	-1	0	0
v2	1	0	-1	0
v3	0	1	0	-1
v4	0	0	1	1

有向图的邻接矩阵

定义：设有向图 G = (V, E)，|V| = n。
有向图的邻接矩阵是一个 n × n 的矩阵 A，其中

A[i][j] = 1，表示存在从 v_i 到 v_j 的有向边；

否则 A[i][j] = 0。

所有元素之和等于边数

例：

v1 → v2，v1 → v3，v2 → v4，v3 → v4

	v2	v3	v4
v1	1	1	0
v2	0	0	1
v3	0	0	1
v4	0	0	0

有向图的可达矩阵

定义：设有向图 G = (V, E)，|V| = n。
可达矩阵是一个 n × n 的矩阵 R，其中

R[i][j] = 1，表示从 v_i 出发存在一条路径可到达 v_j；

否则 R[i][j] = 0。

由于顶点到自身都是可达的,故可达矩阵对角线上的元素恒为1
例：
基于上述有向图

	v1	v2	v3	v4
v1	1	1	1	1
v2	0	1	0	1
v3	0	0	1	1
v4	0	0	0	1

着色问题

着色问题：设 G = (V, E) 为无向无环图，给每个顶点分配一种颜色，使得

若 {u, v} ∈ E，则 u 与 v 的颜色不同,即相邻顶点颜色不同
记使用的最少颜色数为k,称G为k-可着色的

Welsh–Powell 算法：
是一种求图顶点着色的启发式算法，其基本思想是优先为度数大的顶点着色。

算法步骤：

将图中所有顶点按度数从大到小排序（若度数相同，可任意排列）；
取尚未着色的第一个顶点，赋予一种新颜色；
在剩余未着色顶点中，按排序顺序选择与已着该颜色顶点均不相邻的顶点，赋予同一颜色；
重复步骤 2–3，直到所有顶点均被着色。

例题

设  
V = {v1, v2, v3, v4, v5}  
E = { {v1,v2}, {v1,v3}, {v1,v4}, {v2,v3}, {v3,v4}, {v4,v5} }

各顶点度数：  
deg(v1)=3，deg(v3)=3，deg(v4)=3，deg(v2)=2，deg(v5)=1  

排序结果：  
v1, v3, v4, v2, v5  

着色过程：  
- 颜色 1：v1，v5  
- 颜色 2：v3  
- 颜色 3：v4  
- 颜色 4：v2  

因此该算法得到 G 为 4-可着色（不一定是最小色数）。

练手

答案

特殊的图

二部图

把一个图的顶点划分为两个不相交子集，使得每一条边都分别连接两个集合中的顶点，如果存在这样的划分，则此图为一个二部图

[深入理解](htt ps://blog.csdn.net/qq_26822029/article/details/90382581)
若 G 中无长度为奇数的回路，则无向图 G 是二部图
证明

也就是说各自的子集中两个顶点之间都没有边

匹配

匹配（Matching）
在无向图 G = (V, E) 中，若边集 M ⊆ E 满足：
任意两条边不共享公共顶点(即不相连)，则称 M 为图 G 的一个匹配。

极大匹配（Maximal Matching）
若匹配 M 满足：
在图中不能再加入任何一条边而仍保持是匹配，则称 M 为极大匹配。

最大匹配（Maximum Matching）
在图 G 的所有匹配中，边数最多的匹配称为最大匹配。

匹配数
最大匹配 M 中边的条数称为匹配数

完美匹配（Perfect Matching）
若匹配 M 覆盖图中所有顶点，即每个顶点都恰好与一条匹配边相关联，
则称 M 为完美匹配。

完备匹配（Complete Matching）
在二部图 G = (X, Y, E) 中，若存在一个匹配使得 X 中的每个顶点
都与 Y 中某个顶点匹配，则称该匹配为完备匹配。(当|X|<|Y|时允许存在有顶点不匹配的情况)

Hall 定理及其引申

Hall 定理（婚姻定理）
设 G = (X, Y, E) 为二部图。
存在一个覆盖 X 的完备匹配，当且仅当对 X 的任意子集 S，
S 的邻接顶点集合 N(S) 满足：

|N(S)| ≥ |S|

Hall 定理的等价表述
二部图 G = (X, Y, E) 中存在完备匹配
当且仅当 X 的任意子集都不“缺少”可匹配的邻接顶点。

用人话说,当|X|<=|Y|时需要保证X中任意k个顶点至少邻接Y中k个顶点

Hall 定理的推论
设 G = (X, Y, E) 为二部图，若存在t>0,使得:

X中每个顶点至少关联t条边

Y中每个顶点至多关联t条边
则称G中存在X到Y的完备匹配

显然这是一个很强烈的充分条件而非必要条件

欧拉图

欧拉回路:通过图中所有边且每边仅通过一次的回路，具有欧拉回路的图称为欧拉图（Euler Graph）

将回路改为通路就得到了欧拉通路的定义

无向图中：

有欧拉回路：当且仅当 G 是连通图且无奇度顶点

有欧拉通路但没有欧拉回路：当且仅当 G 是连通图且恰好有两个奇度顶点

当然有欧拉回路就有欧拉通路,少连一条边就是了

有向图中：

有欧拉回路：当且仅当 G 是连通图且每个顶点的入度等于出度
直观上很好理解，证明还是算了吧

哈密顿图

通过图 G 的每个结点一次且仅一次的通路（回路），就是哈密顿通路（回路），存在哈密顿回路的图就是哈密顿图

判定方法

若n阶有向图G对应的无向图中含有生成子图Kn(即生成子图为完全图),则G中存在哈密顿通路

这个挺显然的,如果每个顶点间都有连线,怎么都能把所有顶点连接起来

平面图

若 G 能画在平面上而不出现边交叉，则为平面图，画出的图称为 G 的平面嵌入

面:设G是一个平面嵌入,G
的边将整个平面划分成若干区域,每个区域称为G的一个面,其中面积无限的区域称为无限面或外部面,面积有限的区域称为有限面或内部面

nnd图论这一堆中文别名就不能统一一下,自己研究起来不麻烦吗

包围面R的所有边构成的回路称为R的边界,边界的长度称为R的次数,记为deg®

注意若外部面包含割边,需要沿着割边的两侧绕行形成回路,故会计算两次
在简单平面图中，每个面的次数 ≥ 3 （因为不存在长度为 1 或 2 的回路）。
各面次数之和等于边数的 2 倍：
平面图各面的次数之和等于边数的2倍

证明
在平面图中，每一条边都有两侧：

要么分别邻接两个不同的面；

要么作为桥或割边，在同一个面边界上出现两次

无论哪种情况，
每一条边都会被恰好计入两个面的次数中。

极大平面图

若G是简单平面图, 且在任意两个不相邻的顶点
之间加一条新边所得图为非平面图, 则称G为极大平面图

极大平面图是连通的 (若不连通则可以继续加边,矛盾)
设G为n(n3)阶简单图, G为极大平面图的充分必要条件是, G每个面的次数均为3.

欧拉公式

对于连通平面图有欧拉公式：n + r - 2 = m，其中 n 为顶点数，m 为边数，r 为面数（显然边数总是最多的一方）

记住有个两个数相加减2等于另一个数,然后立方体中边数为12,顶点数为8,面数为6,就能记住欧拉公式

树

定义

不含回路的连通无向图称为树，平凡图(即一个点)称为平凡树,度数为 1 的顶点称为树叶，度数大于 1 的称为分支点

注意!!!
关于二叉树本教材默认第一层高度为0,第二层高度为1,以此类推!!!

生成树

G 是无向连通图，T 是 G 的生成子图且是树，则 T 为 G 的生成树（即连接了所有节点），G 在 T 中的边称为 T 的树枝，不在 T 中的边称为 T 的弦，T 中所有弦生成的导出子图称为 T 的余树(不一定是树,也未必连通)

定理:任何无向连通图G都有生成树

证明:若G无回路,则本身就是生成树,若含有回路,则删去回路上任意一条边,直到图中不再有回路,这不影响G的连通性,从而得到生成树

推论:n阶无向连通图G的边数大于等于n-1

证明:其生成树的边数为n-1

基本回路和基本割集

基本回路（Fundamental Circuit）
设 T 是连通图 G 的一棵生成树。
对任意一条不属于 T 的边 e(弦)，将 e 加入 T 中，
则在 T ∪ {e} 中产生且唯一的回路，称为关于生成树 T 的一个基本回路。

基本回路系统
由生成树 T 中所有弦各自对应的基本回路所组成的集合，
称为图 G 的一个基本回路系统。

基本割集（Fundamental Cutset）
设 T 是连通图 G 的一棵生成树。
对任意一条属于 T 的边 e，从 T 中删去 e，
生成树被分成两个连通分量。
在原图 G 中，所有连接这两个分量的边构成的集合，
称为关于生成树 T 和边 e 的基本割集。