1.1 图的基本概念

1.1.1 图的定义

图论的研究起源于哥尼斯堡七桥问题，为了获取对图的一些直观认识，我们先从该案例出发。

在哥尼斯堡城的Pregel河上有两个小岛，有七座桥与四块陆地彼此相连，如图1-1a所示。当时困扰当地居民的一个问题是：如何从其中一块陆地出发，走过每一座桥一次且仅一次，最后再回到出发点。当地的人们不断尝试，都没有解决这个问题。后来，欧拉给出了问题的解。他将四块陆地表示成四个节点，若两块陆地之间有桥相连，则用连接两个节点的一条边代替，这样就将问题抽象成了图1-1b。运用图的相关理论，欧拉证明了这样的回路是不存在的。

欧拉认为，对于一个给定的图，如果能够走完所有的边并且没有重复，要求图中最多只能有两个点（起点和终点）与奇数条边相连，其余的中间点所关联的边的数目必须为偶数，这样才能保证从一条边进入某点，再从另一条边出去。而图1-1b中的所有顶点均有奇数条边与其相连，显然这样的回路是不存在的。

在该例子中，欧拉用图1-1b代替了图1-1a，从而使得对问题的研究归结为对图的研究。

事实上，图能在相当程度上代表我们所研究问题的本质，现实中的很多问题都可以抽象为图的形式，从而利用图结构和技术解决相应问题。例如，在计算机辅助设计（Computer Aided Design，CAD）中，首先需要将电网络转换为图，然后才能进行电路分析。对于图1-2a中的电网络，可以将其抽象为图1-2b。

在图论中，一个 图 （Graph）定义为由两个集合 V 和 E 组成，记为 G =（ V ， E ），其中 V 是顶点（Vertex）的有限非空集； E 是两个顶点之间的关系（边）的集合。通常，也将图 G 的顶点集和边集分别表示为 V （ G ）和 E （ G ）。假设顶点集 V ={ v ₁ ， v ₂ ，…， v _n }，边集 。下面介绍图的一些基本术语。

1.1.2 图的基本术语

1.无向图和有向图

如果顶点 v _i 和 v _j 之间的边是无向边（简称边），则该边用无序偶对（ v _i ， v _j ）表示，此时的图称为无向图（Undirected Graph），如图1-3a所示。

如果顶点 v _i 和 v _j 之间的边是有向边（也称弧），则该边用有序偶对< v _i ， v _j >表示，其中 v _i 称为弧尾， v _j 称为弧头，此时的图称为有向图（Directed Graph），如图1-3b所示。

2.无向完全图和有向完全图

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图（Undirected Complete Graph），如图1-4a所示。

在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图（Directed Complete Graph），如图1-4b所示。

3.稀疏图和稠密图

如果用 n 表示图中的顶点数目，用 e 表示边或弧的数目。当图 G 满足 e < n log n 时，将图 G 称为稀疏图（Sparse Graph），反之称为稠密图（Dense Graph）。

4.子图

对于两个图 G =（ V ， E ）和 G′ =（ V′ ， E′ ），如果 V′ 是 V 的子集，且 E′ 是 E 的子集，则称 G′ 是 G 的子图（Subgraph）。图1-5a中给出了无向图 G ₁ 及其子图 ，图1-5b给出了有向图 G ₂ 及其子图 。

5.邻接点和依附

对于无向图 G =（ V ， E ），如果存在边 ，则称顶点 v _i 和 v _j 互为邻接点（Adjacent），即 v _i 和 v _j 相邻接。也称边（ v _i ， v _j ）依附（Incident）于顶点 v _i 和 v _j 。

对于有向图 G =（ V ， E ），如果存在弧 ，则称顶点 v _i 邻接到顶点 v _j ，顶点 v _j 邻接自顶点 v _i 。也称弧< v _i ， v _j >依附于顶点 v _i 和 v _j 。

6.权、网

在一个图中，边上或者弧上可以标上某种有意义的数值，这种与图的边或弧相关的数称作权（Weight）。权值可以表示一个顶点到另一个顶点之间的距离、时间或者价格等。边上带权的图称为网（Network）。图1-6a为一个无向网，图1-6b为一个有向网。

7.顶点的度、入度和出度

在无向图中，顶点 v 的度（Degree）指依附于顶点 v 的边的条数，记为TD（ v ）。例如在图1-5a中给出的无向图 G ₁ 中，顶点 v ₃ 的度为2。

对于有向图，由于弧有方向性，故顶点 v 的度分为入度（In-Degree）和出度（Out-Degree），入度是以顶点 v 为弧头的弧的条数，记为ID（ v ）。出度是以顶点 v 为弧尾的弧的条数，记为OD（ v ）。顶点的度记为TD（ v ），有TD（ v ）=ID（ v ）+OD（ v ）。例如在图1-5b中给出的有向图 G ₂ 中，顶点 v ₁ 的度为3，入度为2，出度为1。

8.路径、路径长度和回路

在图 G 中，顶点 v _i 到顶点 v _j 的路径（Path）是指从顶点 v _i 到顶点 v _j 之间所经过的顶点序列。路径上边或弧的数目称为路径长度（Path Length）。第一个顶点和最后一个顶点相同的路径称为回路（Circuit）。

9.简单路径和简单回路

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

10.连通图和连通分量

在无向图中，若顶点 v _i 和顶点 v _j 之间存在路径，则称 v _i 和 v _j 是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图（Connected Graph）。

无向图中的极大连通子图称为连通分量（Connected Component）。所谓“极大”，是指尽可能多地包含原图中的顶点和这些顶点之间的边。图1-7中给出了无向图 G ₃ 以及图 G ₃ 的3个连通分量。

11.强连通图和强连通分量

在有向图中，对于顶点 v _i 和 v _j ，若从 v _i 到 v _j 和从 v _j 到 v _i 都存在路径，则称这两个顶点 v _i 和 v _j 是强连通的。如果图中任意两个顶点都是强连通的，则称该图是强连通图（Strongly Connected Graph）。

有向图中的极大连通子图称为有向图的强连通分量（Strongly Connected Component）。图1-8中给出了有向图 G ₄ 以及图 G ₄ 的两个强连通分量。

12.生成树和生成森林

一个含有 n 个顶点的连通图的生成树（Spanning Tree）是一个极小连通子图，它包含图中的全部顶点，有且仅有 n -1条边。图1-5a中图 G ₁ 的一棵生成树如图1-9a所示。如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。

在非连通图中，每一个连通分量都可以得到一棵生成树，这些生成树构成了该非连通图的生成森林（Spanning Forest）。这个生成森林含有图中全部的顶点。图1-7a中图 G ₃ 的生成森林如图1-9b所示。