本章概述了图论中的一些概念，部分内容来源于
OI Wiki
图
图 (Graph) 是一个由 点集 (Vertex set) 和 边集 (Edge set) 组成的二元组。常用
G
=
(
V
,
E
)
G = \left ( V, E \right )
G=(V,E)表示图
图分为 有向图 (Directed graph) 和 无向图(Undirected graph)
无向图的边集中的每个元素为一个无序二元组
(
u
,
v
)
\left ( u,v \right )
(u,v)，称作 无向边 (Undirected edge)
有向图的边集中的每一个元素为一个有序二元组
(
u
,
v
)
\left ( u,v \right )
(u,v)，也写作
u
→
v
u\rightarrow v
u→v，称作 有向边 (Directed edge) 或 弧 (Arc)
图
G
G
G的点数
∣
V
(
G
)
∣
\left | V\left ( G \right ) \right |
∣V(G)∣也被称作图
G
G
G的阶 (Order)
相邻
一个顶点
v
ϵ
V
v \: \epsilon\: V
vϵV的 邻域 (Neighborhood) 是所有与之相邻的顶点所构成的集合，记作
N
(
v
)
N\left ( v \right )
N(v)
一个点集
S
S
S的邻域是所有与
S
S
S中至少一个点相邻的点所构成的集合，记作
N
(
S
)
N\left ( S \right )
N(S)，即：
N
(
S
)
=
⋃
v
ϵ
S
N
(
v
)
N\left ( S \right )= \displaystyle\bigcup_{ v\epsilon S} N\left ( v \right )
N(S)=vϵS⋃N(v)
度
与一个顶点
v
v
v关联的边的条数称作该顶点的 度 (Degree)，记作
d
(
v
)
d(v)
d(v)
对于无向简单图，有
d
(
v
)
=
∣
N
(
v
)
∣
d(v)=|N(v)|
d(v)=∣N(v)∣
握手定理（又称图论基本定理）：对于任何无向图
G
=
(
V
,
E
)
G =( V, E )
G=(V,E)，有
∑
v
ϵ
V
d
(
v
)
=
2
∣
E
∣
\sum _{v\epsilon V} d(v) = 2\left | E \right |
∑vϵVd(v)=2∣E∣
简单图
自环 (Loop)
重边 (Multiple edge)
简单图 (Simple graph)：若一个图中没有自环和重边，它被称为简单图。具有至少两个顶点的简单无向图中一定存在度相同的结点
如果一张图中有自环或重边，则称它为 多重图 (Multigraph)
路径
途径 (Walk)：途径是一个将若干个点连接起来的边的集合
迹 (Trail)：每一条经过的边都不相同的途径叫做迹
路径 (Path)（又称 简单路径 (Simple path))：对于一条迹
w
w
w，若其连接的点的序列中点两两不同，则称
w
w
w是一条路径
回路 (Circuit)
环/圈 (Cycle)（又称 简单回路/简单环 (Simple circuit))：对于一个回路
w
w
w，若
v
0
=
v
k
v_0 = v_k
v0=vk是点序列中唯一重复出现的点对，则称
w
w
w是一个环
子图
H
=
(
V
′
,
E
′
)
H=(V',E')
H=(V′,E′)是
S
=
(
V
,
E
)
S=(V,E)
S=(V,E)的 导出子图/诱导子图 (Induced subgraph) 当且仅当
H
⊆
S
H\subseteq S
H⊆S且满足
∀
u
,
v
ϵ
V
′
\forall u,v \: \epsilon \: V'
∀u,vϵV′，只要
(
u
,
v
)
ϵ
E
(u,v)\: \epsilon E
(u,v)ϵE均有
(
u
,
v
)
ϵ
E
′
(u,v)\: \epsilon E'
(u,v)ϵE′
容易发现，一个图的导出子图仅由子图的点集决定，因此点集为
V
′
V'
V′的导出子图称为
V
′
V'
V′导出的子图 ，记作
G
[
V
′
]
G[V']
G[V′]
连通
无向图
对于一张无向图
G
=
(
V
,
E
)
G = \left ( V, E \right )
G=(V,E)，对于
u
,
v
ϵ
V
u, v \: \epsilon\: V
u,vϵV，若存在一条途径使得
v
0
=
u
,
v
k
=
v
v_0 = u, v_k = v
v0=u,vk=v，则称
u
u
u和
v
v
v是 连通的 (Connected)
若无向图
G
G
G满足其中任意两个顶点均连通，则称
G
G
G是 连通图 (Connected graph)， 这一性质称作 连通性 (Connectivity)
连通块/连通分量 (Connected component)
有向图
对于一张有向图
G
=
(
V
,
E
)
G = \left ( V, E \right )
G=(V,E)，对于
u
,
v
ϵ
V
u, v \: \epsilon\: V
u,vϵV，若存在一条途径使得
v
0
=
u
,
v
k
=
v
v_0 = u, v_k = v
v0=u,vk=v，则称
u
u
u可达
v
v
v（无向图中的连通也可以视作双向可达）
若一张有向图的节点两两互相可达，则称这张图是 强连通的 (Strongly connected)
若一张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是 弱连通的 (Weakly connected)
与连通分量类似，也有 弱连通分量 (Weakly connected component)（极大弱连通子图）和 强连通分量 (Strongly Connected component)（极大强连通子图）
