1.图的基本概念

图的定义

图 $G$ 由顶点集 $V$ 和边集 $E$ 组成,记为 $G=(V,E)$ ，其中 $V(G)$ 表示图 $G$ 中顶点的有限非空集; $E(G)$ 表示图 $G$ 中顶点之间的关系(边)集合。若 $V=\{v_{1},v_{2},v_{3},\dots v_{n}\}$ ，则用 $\mid V\mid$ 表示图 $G$ 中顶点的个数, $E=\{(u,v)|u\in V,v\in V\}$ , 用 $\mid E\mid$ 表示图 $G$ 中边的条数。

注意

图的顶点集 $V$ 一定非空,但边集 $E$ 可以为空,此时图中只有顶点而没有边

有向图

若 $E$ 是有向边(也称孤^[1])的有限集合时,则图 $G$ 为有向图。弧是顶点的有序对,记为 $<v,w>$ 其中 $v,w$ 是顶点, $v$ 称为弧尾, $w$ 称为弧头, $<v,w>$ 称为从 $v$ 到 $w$ 的弧,也称 $v$ 邻接到 $w$ 。

\begin{gathered} G_{1}=(V_{1},E_{1}) \\ V_{1}=\{1,2,3\} \\ E_1=\{<1,2>,<2,1>,<2,3>\} \end{gathered}

无向图

若 $E$ 是无向边(简称边)的有限集合时,则图 $G$ 为无向图。边是顶点的无序对,记为 $(v,w)$ 或(w,v)。可以说 $w$ 和 $v$ 互为邻接点。边 $(v,w)$ 依附于 $w$ 和 $v$ ,或称边 $(v,w)$ 和 $v,w$ 相关联。

\begin{gathered} G_2=(V_2,E_2) \\ V_{2}=\{1,2,3,4\} \\ E_{2}=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\} \end{gathered}

简单图、多重图

一个图 $G$ 如果满足:

不存在重复边;
不存在顶点到自身的边,那么称图G 为简单图。
图6.1中 $G_{1}$ 和 $G_{2}$ 均为简单图。若图 $G$ 中某两个顶点之间的边数大于 1条,又允许顶点通过一条边和自身关联,则称图 $G$ 为多重图。多重图和简单图的定义是相对的。数据结构中仅讨论简单图。

完全图(也称简单完全图)

在完全图中任意两个项点之间都存在边,有 $n(n-1)/2$ 条边的无向图称为完全图,有 $n(n-1)$ 条弧的有向图称为有向完全图

子图

设有两个图 $G(V,E)$ 和 $G'=(V',E')$ ，若 $V'$ 是 $V$ 的子集，且 $E'$ 是 $E$ 的子集，则称 $G'$ 是 $G$ 的
子图。若有满足 $V(G')=V(G)$ ^[2]的子图 $G'$ ，则称其为 $G$ 的生成子图。图6.1中 $G_{3}$ 为 $G_{1}$ 的子图。

注意

并非 $V$ 和 $E$ 的任何子集都能构成 $G$ 的子图,因为这样的子集可能不是图,即 $E$ 的子集中的某些边关联的顶点可能不在这个 $V$ 的子集中。

连通、连通图和连通分量

在无向图中,若从顶点 $v$ 到顶点 $w$ 有路径存在,则称 $v$ 和 $w$ 是连通的。若图 $G$ 中任意两个顶点都是连通的,则称图 $G$ 为连通图,否则称为非连通图。无向图中的极大连通子图称为连通分量,在图中,图 $G_{4}$ 有3个连通分量如图所示。假设一个图有 $n$ 个顶点,如果边数小于 $n-1$ ,那么此图必是非连通图，如果图是非连通图,那么最多可以有 $C_{n-1}^2$ 条边

连通图边数

若G是连通图，最少有 $n-1$ 条边
如果图是非连通图,那么最多可以有 $C_{n-1}^2$ 条边

强连通图、强连通分量

在有向图中,如果有一对顶点 $v$ 和 $w$ ,从 $v$ 到 $w$ 和从 $w$ 到 $v$ 之间都有路径,则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的,则称此图为强连通图。有向图中的极大强连通子图称^[3]为有向图的强连通分量

强连通图边数

有向图强连通情况下边最少的情况:至少需要 $n$ 条边,构成一个环路

注

在无向图中讨论连通性,在有向图中讨论强连通性

生成树、生成森林

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n,则它的生成树含有n-1条边。包含图中全部顶点的极小连通子图,只有生成树满足这个极小条件,对生成树而言,若砍去它的一条边,则会变成非连通图,若加上一条边则会形成一个回路。
在非连通图中, 连通分量的生成树构成了非连通图的生成森林。

注意

区分极大连通子图和极小连通子图。

极大连通子图是无向图的连通分量,极大即要求该连通子图包含其所有的边;
极小连通子图是既要保持图连通又要使得边数最少的子图。

顶点的度、入度和出度

无向图

在无向图中,顶点 $v$ 的度是指依附于顶点的边的条数,记为 $\mathrm{TD}(v)$

对于具有 $n$ 个项点、 $e$ 条边的无向图,有 $\displaystyle\sum_{i=1}^n(v_{i})=2e$

有向图

在有向图中,顶点 $v$ 的度分为入度和出度,入度是以顶点 $v$ 为终点的有向边的数目,记为 $\mathrm{ID}(v)$ ; 而出度是以顶点 $v$ 为起点的有向边的数目,记为 $\mathrm{OD}(v)$

\mathrm{TD}(v)=\mathrm{ID}(v)+\mathrm{OD(v)}

\sum_{i=1}^{n}\mathrm{ID}(\nu_{i})=\sum_{i=1}^{n}\mathrm{OD}(\nu_{i})=e

边的权和网

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。

稠密图、稀疏图

$|E|<|V|\mathrm{log}|V|$ 可视为稀疏图

路径、路径长度和回路

若一个图有n个顶点，并且有大于n-1条边，则此图一定有环。

简单路径、简单回路

在路径序列中，顶点不重复出现的路径称为简单路径。
除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

距离

从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到
v根本不存在路径，则记该距离为无穷(∞)。

有向树

一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。

注意弧和路径的区别，弧的长度为1，路径不一定 ↩︎
即包含了原图的所有顶点，但是少了部分边 ↩︎
子图必须联通，且包含尽可能多的顶点和边 ↩︎

1.图的基本概念

# 图的定义

# 有向图

# 无向图

# 简单图、多重图

# 完全图(也称简单完全图)

# 子图

# 连通、连通图和连通分量

# 强连通图、强连通分量

# 生成树、生成森林

# 顶点的度、入度和出度

# 无向图

# 有向图

# 边的权和网

# 稠密图、稀疏图

# 路径、路径长度和回路

# 简单路径、简单回路

# 距离

# 有向树