图的基本概念

图的定义

图 由顶点集 和边集 组成，记为 #card=math&code=G%3D%28V%2CE%29&id=TMJtb)，其中 #card=math&code=V%28G%29&id=mdzcf) 表示图 中顶点的有限非空集；#card=math&code=E%28G%29&id=uNdre) 表示图 中顶点之间的关系 （边）集合。若 ，则用 表示图 中顶点的个数，也称图 的阶，，用 表示图 中边的条数。

注意：线性表可以是空表，树可以是空树，但图不可以是空图。就是说，图中不能一个顶点也没有，图的顶点集 一定非空，但边集 可以为空，此时图中只有顶点而没有边。

下面是图的一些基本概念及术语。

有向图和无向图

若 是有向边（也称弧）的有限集合时，则图 为有向图。弧是顶点的有序对，记为 ，其中 ， 是顶点， 称为弧尾， 称为弧头， 称为从顶点 到顶点 的弧，也称 邻接到 ，或 邻接自 。

若 是无向边（简称边）的有限集合时，则图 为无向图。边是顶点的无序对，记为 #card=math&code=%28v%2Cw%29&id=m7sSL) 或 #card=math&code=%28w%2Cv%29&id=otN2s)，因为%3D(w%2Cv)#card=math&code=%28v%2C%20w%29%3D%28w%2Cv%29&id=pli7t) 其中 ， 是顶点。可以说顶点 和顶点 互为邻接点。边 #card=math&code=%28v%2C%20w%29&id=Nnon0) 依附于顶点 和 ，或者说边 #card=math&code=%28v%2C%20w%29&id=AhXNy) 和顶点 ， 相关联。

简单图和多重图

一个图 若满足：

1. 不存在重复边；
2. 不存在顶点到自身的边，则称图 为简单图。

   考研数据结构中仅讨论简单图。

若图 中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则 为多重图。多重图的定义和简单图是相对的。

顶点的度、入度和出度

图中每个顶点的度定义为以该顶点为一个端点的边的数目。

对于无向图，顶点 的度是指依附于该顶点的边的条数，记为 #card=math&code=%5Cmathrm%7BTD%7D%20%28v%29&id=rQkfL)。

在具有 个顶点、 条边的无向图中 即无向图的全部顶点的度的和等于边数的 2 倍，因为每条边和两个顶点相关联。

对于有向图，顶点 的度分为入度和出度，入度是以顶点 为终点的有向边的数目，记为 #card=math&code=%5Cmathrm%7BID%7D%28v%29&id=JTf5g)；而出度是以顶点 为起点的有向边的数目，记为 #card=math&code=%5Cmathrm%7BOD%7D%28v%29&id=NgcS7)。顶点 的度等于其入度和出度之和，即 %3D%5Cmathrm%7BID%7D(v)%2B%5Cmathrm%7BOD%7D(v)#card=math&code=%5Cmathrm%7BTD%7D%20%28v%29%3D%5Cmathrm%7BID%7D%28v%29%2B%5Cmathrm%7BOD%7D%28v%29&id=BCGYZ)。

在具有 个顶点、 条边的有向图中，

即有向图的全部顶点的入度之和与出度之和相等，并且等于边数。这是因为每条有向边都有一个起点和终点。

路径、路径长度和回路

顶点 到顶点 之间的一条路径是指顶点序列 ，当然关联的边也可以理解为路径的构成要素。

路径上边的数目称为路径长度。

第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有 个顶点，并且有大于 条边，则此图一定有环。

简单路径、简单回路

在路径序列中，顶点不重复出现的路径称为简单路径。

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

距离

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

连通、连通图

在无向图中，若从顶点 到顶点 有路径存在，则称 和 是连通的。若图 中任意两个顶点都是连通的，则称图 为连通图，否则称为非连通图。

若图 是连通图，则至少有 条边。若 是非连通图，则至多可能有 条边

强连通图

在有向图中，若从顶点 到顶点 和从顶点 到顶点 之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。

若 是强连通图，则最少有 条边（形成回路）

注意：强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性，在有向图中考虑强连通性。

子图

设有两个图 #card=math&code=G%3D%28V%2CE%29&id=rCM0G) 和 #card=math&code=G%27%3D%28V%27%2CE%27%29&id=ei70T) ，若 是 的子集，且 是 的子集，则称 是 的子图。若有满足 %3DV(G)#card=math&code=V%28G%27%29%3DV%28G%29&id=pUbxp) 的子图 ，则称其为 的生成子图。

注意：并非 和 的任何子集都能构成 的子图，因为这样的子集可能不是图，即 的子集中的某些边关联的顶点可能不在这个 的子集中。

连通分量、强连通分量

无向图中的极大连通子图称为连通分量。

有向图中的极大强连通子图称为有向图的强连通分量。

注意：要区分极大连通子图和极小连通子图，极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边；极小连通子图是既要保持图连通又要使得边数最少的子图。

生成树、生成森林

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 ，则它的生成树含有 条边。

对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

边的权和网

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

带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

完全图

无向完全图：无向图中任意两个顶点之间都存在边，若无向图的顶点数 ，则

有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧，若有向图的顶点数 ，则

稠密图、稀疏图

边数很少的图称为稀疏图，反之称为稠密图。

稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图 满足 时，可以将 视为稀疏图。

树、有向树

树：不存在回路，且连通的无向图。 个顶点的树，必有 条边。

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