# 图的定义

# 图的定义一

图 G = (V, E) 是一个系统 ，其中
(1)$V \ne \varnothing$ 是一个有限集合；V 中的每一元素$v\in V$ 都称为图 G 的一个结点 (node ,vertex)， V 称为图 G 的结点集；
(2) E 是一个有限集合； E 中的每一元素$e\in E$ 都称为图 G 的一条边 (edge) ；E 称为图 G 的边集。

此定义的优点是简单，适应面广；缺点是没有规定清楚点、线之间的关系。

# 图的定义二

图 G = (V, E) 是一个系统 ，其中
(1)$V \ne \varnothing$ 是一个有限集合；V 中的每一元素$v\in V$ 都称为图 G 的一个结点 (node ,vertex)， V 称为图 G 的结点集；
(2)$E\subseteq V\times V$ 是一个有限集合，一个 V 上的关系； E 中的每一元素$(u,v)\in E$ 都称为图 G 的一条边 (edge)，这里$u,v\in V$；E 称为图 G 的边集。

此定义的优点是简单，规定了清楚的点、线之间的关系，很适合简单图、特别是有向图（比如第二章的关系图、哈斯图）；缺点是无法表示平行边，因此不适合多重图（比如上节的七桥图）

# 图的定义三

图$G = (V,\sum, E)$ 是一个系统 ，其中
(1)$V \ne \varnothing$ 是一个有限集合；V 中的每一元素$v\in V$ 都称为图 G 的一个结点 (node ,vertex)， V 称为图 G 的结点集；
(2)$\sum$ 是一有限集合；$\sum$ 中的每一元素$\sigma$ 都称为图 G 中的一个标号 (label)；$\sum$ 称为图 G 的标号集
(3)$E\subseteq V\times \sum \times V$ 是一个有限集合，一个三元关系； E 中的每一元素$(u,\sigma,v)\in E$ 都称为图 G 的一条边 (edge) 或弧 (arc), 此边起自 u 而终于 v ；称 u 是此边的起点，称$\sigma$ 是此边的标号，称 v 是此边的终点 ，起点和终点统称为边的端点，这里$(u,v\in V,\sigma \in \sum)$； E 称为图 G 的边集。

• 此定义是由美国哈佛大学爱伦堡教授给出的；
• 此定义规定了严格的点、线之间的关系，适应面很广、特别适合多重图（比如上节的七桥图）；缺点是边表示比较复杂，简单图一般不采用。
• 标号实际上是为了区别两点间的平行边而设的；标号集的大小一般就是图中平行边的最大条数 (图的重数，参见下面概念)。
• 当图的重数为 1，即图无平行边时 (简单图，参见下面概念)，有$\sum = \{\sigma_1\}$, 各边标号一样，全为$\sigma_1$. 这时可取掉各边标号及标号集，定义 3 就变成了定义 2；所以定义 3 适合于图的一般情况，特别是 (有平行边的) 多重图，而定义 2 适合于 (无平行边的) 简单图。

# 图的定义四

图$G=(V,E, \gamma)$ 是一个系统，其中
(1)$V \ne \varnothing$ 是一个有限集合；V 中的每一元素$v\in V$ 都称为图 G 的一个结点 (node ,vertex)， V 称为图 G 的结点集；
(2)$E$ 是一个有限集合；E 中的每一元素$e\in E$ 都称为图 G 的一条边 (edge)；E 称为图 G 的边集。
(3)$\gamma$ 是边到结点集的一个关联函数，即

$$\gamma :E \to 2^V(无向图)或\gamma :E \to V\times V(有向图)$$

$\gamma$ 将 E 中的每条边$e\in E$ 与结点集 V 中的一个二元子集$\{u,v\}\in 2^V$ (或$\{u,v\}\subseteq V)$ 相关联，或与结点集 V 上的一个二元组$\{u,v\}\in 2^V$ (或$\{u,v\}\subseteq V\times V)$ 相关联，即

$$\gamma(e)=\{u,v\}(无向图)或\gamma(e)=（u,v）$$

称 u 是此边的起点，称 v 是此边的终点 ，结点 u 和 v 统称为边的端点

• 此定义是对美国库曼教授所给定义的一个修正；
• 此定义的优点是适应面较广，尤其是将边看作是和结点同样的独立的研究对象，边不再是由结点表示的一个附属对象，用函数概念规定了点、线之间的严格关联关系，这样一来，就便于边概念的进一步推广（比如引出超图概念）；缺点是关联函数表示比较烦琐，简单图一般不采用。

# 图论的概念术语

# (n,m) 图

|V| = n,|E| = m，即有 n 个结点和 m 条边的图称为 (n, m) 图。

# 无向边 (undirected edges 简 edges)

在定义 3 下，若边$(u,\sigma , v)$ 与边$(v,\sigma ,u)$ 表示同一条边，则称此边为无向边。

# 无向图 (undirected graph 简 graph)

所有的边都是无向边的图称为无向图。记为 G。

# 有向边 (directed arc 简 arc 或 arrow)

在定义 3 下，若边 (u, , v) 与边 (v, ,u) 表示不同的边，则称此边为有向边。

# 有向图 (directed graph 简 digraph)

所有的边都是有向边的图称为有向图。记为 D。

# 混和图 (mixed graph)

既有有向边又有无向边的图称为混和图。

# 空图 (empty graph)

$V=\varnothing (当然 E=\varnothing)$，即没有一个结点的图称为空图。

# 零图 (null graph)

$E=\varnothing$ 即没有一条边的图称为零图。

# 平凡图 (trivial graph)

|V| = 1，即只有一个结点的图称为平凡图。

# 二边相邻 (adjacent)

在图中，若两条边有一公共端点，则称此二边相邻。

# 二结点相邻 (adjacent)

若两个结点是同一条边的两个端点，则称此二结点相邻。

# 一结点与一边相关联 (incident)

若一结点是一边的一个端点，则称此结点与该边相关联。

# 孤立点 (isolated vertex)

不与任何边相关联的结点称为孤立点。

# 自环 (loop)

两个端点相同的边称为自环。

# 平行边 (parallel edges)

有相同端点 (相同的起点，相同的终点) 的两条边称为平行边。

# 重数 (multiplicity)

两结点间平行边的条数称为平行边的重数。

# 多重图 (multiply graph)

具有平行边的图称为多重图；多重图的重数是图中平行边重数的最
大者

# 简单图 (单图、单纯图 (simple graph))

无平行边、无自环的图称为简单图。

# 图的阶 (order)

图中结点的个数 | V | 称为图的阶

# 完全图 (complete graph)

每一对不同的结点间都有一条边的简单图称为完全图。
n 个结点 m 条边的无向完全图：$m=\dfrac{n(n-1)}{2}$
n 个结点 m 条边的有向完全图：$m=n(n-1)$
n 个结点的无向完全图记为：$K_n$

# 子图与补图

# 子图 (subgraph)

设$G=(V, E)和G'=(V', E')$ 是两个 (有向的或无向的) 图。
(1) 若$V\subseteq V$ 且$E\subseteq E$，则称$G'$ 为$G$ 的子图；
(2) 若$V\subset V$ 且$E\subset E$，则称$G'$ 为$G$ 的真子图 (proper-)；
(3) 若$V= V$ 且$E= E$，则称$G'$ 为$G$ 的生成子图 (spanning-)；
(4) 若$V= V$ 且$E= E$，或$V= V$ 且$E= \varnothing$，称$G'$ 为$G$ 的平凡子图 (trivial-)；即:
图 G 本身和 G 的零图是 G 的平凡子图。

# 商图 (quotient graph)

设$G=(V, E)$ 是一 (有向的或无向的) 图。$R\subseteq V\times V$ 是一结点集 V 上的等价关系。
那么， 定义图 G 关于等价关系 R 的商图为简单图
$G^R=(V^R,E^R) \quad$ 其中：
$V^R=V/R=\{[v]_R|v\in R\}$ 是 V 关于等价关系 R 的商集；
E^R=\

# 补图 (complement graph)

设$G=(V, E)$ 是一 (有向的或无向的) 图。$G'=(V', E')$ 是与图 G 相应的完全图。 定义图 G 的补图$\overline{G}= (V, \overline{E})$，其中：
$\overline{E}=E'$\E

# 结点的度

# 结点的出度 (out-degree)

有向图中以结点 v 为起点的有向边的条数称为结点 v 的出度。记为$\overleftarrow{deg}(v)$

# 结点的进度 (入度 (in-degree))

有向图中以结点 v 为终点的有向边的条数称为结点 v 的进度。记为$\overrightarrow{deg}(v)$

# 结点的度 (degree)

图中与结点 v 关联的边的条数称为结点 v 的度。记为$deg(v)$。

# 奇结点 (odd vertex)

度数为奇数的结点称为奇结点。

# 偶结点 (even vertex)

度数为偶数的结点称为偶结点。

# 图 G 的最小度 (minimal degree)

图 G 中各结点度数的最小者。记为$\delta (G)$。

# 图 G 的最大度： (maximum degree)

图 G 中各结点度数的最大者。记为$\Delta(G)$

# 正则图 (regular graph)

若图 G 中各结点的度数都相等，则称图 G 是正则图。 显然，这时$\delta(G)=\Delta(G)$。

# k - 正则的 (k- regular)

若图 G 中各结点的度数都相等，且为 k ，则称图 G 是 k - 正则的，或 k 度正则的。 显然，这时$\delta(G)=\Delta(G)= k$。

# 悬挂点 (hang vertex)

度数为 1 的结点称为悬挂点。

# 悬挂边 (hang edge)

与悬挂点关联的边称为悬挂边。

# 定理 1

1. 无向图 G 中，所有结点的度之和等于边数的二倍；
2. 有向图 G 中，所有结点的进度之和等于出度之和等于边数；

# 定理 2. 任何图中所有奇结点的度数之和是偶数。

推论 1.(握手引理) 在一次集会上和奇数个人握过手的人的
数目是偶数。

# 图的同构 (isomorphism of graphs)

# 同构的定义

(1) 称$G=(V,E)$ 和$G’=(V’,E’)$ 二图同构，记为$G\cong G'\iff$
存在两个双射函数$\varphi: V \rightarrow V',\psi: E \rightarrow E'$，
使得$\psi (u,v)=(u',v')\implies \varphi(u)=u'\land \varphi(v)=v'$。
(2) 称$G=(V,E,\gamma)$ 和$G’=(V’,E’,\gamma')$ 二图同构，记为$G\cong G'\iff$
存在两个双射函数$\varphi: V \rightarrow V',\psi: E \rightarrow E'$，使得
$\psi (e)=e'\land \gamma(e)=\{u,v\}\land \gamma'(e')=\{u',v'\}\implies \varphi(u)=u'\land \varphi(v)=v'$
$\psi (e)=e'\land \gamma(e)=(u,v)\land \gamma'(e')=(u',v')\implies \varphi(u)=u'\land \varphi(v)=v'$

图的同构远比代数系统的同构复杂。这是因为图的同构在同态公式中牵扯着两个 (甚至三个，考虑定义三) 双射函数的交叉关系，而代数系统的同构在同态公式中只有一个双射函数。因此图的同构问题不象代数系统的同构问题那样有许多进展、有几个定理好用，迄今为止，没有任何进展，没有任何定理可用，仅仅只能用定义。

# 性质

若两个图同构，则它们必须满足：
(1) 结点个数相等；
(2) 边数相等；
(3) 对应结点的进度、出度、度数均相等；
(4) 度数相同的结点个数相等；
(5) 平行边对应，重数相等；
(6) 自环对应；悬挂点对应；孤立点对应；
(7) 结点间的相邻关系对应；边间的相邻关系对应；结点与边的关联关系对应；
(8) 圈对应；路对应；
(9) 对应圈的长度相等；对应路的长度相等；
…