图的定义

（1）无向图的定义

无向图是一个有序的二元组< V, E>，记为G，如图7-1（a）所示。

V为顶点集，E为连结点的边集（无向边）

G 1= < V(G1) , E(G1) >

V(G1) = { 0,1,2,3,4,5}

E(G1) = {(0,1)，（0,2），（0,3），（0,4）（1,4），（2,4），（2,5），（3,5），（4,5）}

（2）有向图的定义

有向图是一个有序的二元组< V, E>，记为G，如图7-1（b）所示。

V为顶点集，E为边集（有向边）

G2= < V(G2) , E(G2) >

V(G2) = {0,1,2,3,4}

E(G2) = {<0,1>,<0,2>,<1,2>, <1,4>,<2,1>,<2,3>,<4,3>}

若用G2顶点的值表示其顶点集合边集，则如下表示：

V(G2)={A,B,C,D,E}

E(G2)={<A,B>,<A,C>,<B,C>,<B,E>,<C,B>,<C,D>,<E,D>}

在日常生活中，图的应用到处可见。如各种交通图、线路图、结构图、流程图等，不胜枚举。

无向图

有向图

（1）端点和邻接点

在一个无向图中，若存在一条边(vi,vj)，则称vi、vj为此边的两个端点（Endpoint），并称它们互为邻接点（Adjacent），即vi是vj的一个邻接点，vj也是vi的一个邻接点。如在图7-1所示的G1中，以顶点v0为端点的四条边是(0,1)、(0,2)、(0,3)和(0,4)，v0的四个邻接点分别为v1、v2、v3和v4；以顶点v3为端点的两条边是(3,0)和(3,5)，v3的两个邻接点分别为v0和v5；等等。

在一个有向图中，若存在一条边<vi,vj>，则称此边是顶点vi的一条出边（Out Edge），顶点vj的一条入边（In Edge）；称vi为此边的起始端点，简称起点或始点，vj为此边的终止端点，简称终点；称vi和vj互为邻接点，并称vj是vi的出边邻接点，vi是vj的入边邻接点。如在图7-1所示的G2中，顶点C有两条出边<C,B>和<C,D>，两条入边<A,C>和<B,C>，顶点C的两个出边邻接点为B和D，两个入边邻接点为A和B；其他顶点亦可进行类似分析。

（2）顶点的度、入度、出度

无向图中顶点v的度（Degree）定义为以该顶点为一个端点的边的数目，记为D(v)。如在图7-1所示的G1中，v0顶点的度为4，v1顶点的度为2。有向图中顶点v的度有入度和出度之分，入度（InDegree）是该顶点的入边的数目，记为ID(v)；出度（OutDegree）是该顶点的出边的数目，记为OD(v)；顶点v的度等于它的入度和出度之和，即D(v)=ID(v)+OD(v)。如图7-1所示的G2中，顶点A的入度为0，出度为2，度为2；顶点C的入度为2，出度为2，度为4。

若一个图中有n个顶点和e条边，则该图所有顶点的度同边数e满足下面关系：

这很容易理解，因为每条边连接着两个顶点，使这两个顶点的度数分别增1，总和增2，所以全部顶点的度数为所有边数的2倍，或者说，边数为全部顶点的度数的一半。

（3）完全图、稠密图、稀疏图

若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称这样的图为完全图。显然，若完全图是无向的，则图中包含有

1/2 n(n-1)

条边；若完全图是有向的，则图中包含有n(n-1)

条边。当一个图接近完全图时，则称它为稠密图，相反地，当一个图含有较少的边数时，则称它为稀疏图。图7-2中的G3就是一个含有5个顶点的无向完全图，G4就是一个含有6个顶点的稀疏图。

完全图和稀疏图

（4）子图

设有两个图G=(V,E)和G’=(V’,E’)，若V’是V的子集，即V’ÍV，且E’是E的子集，即E’ÍE，并且E’中的边所涉及到的顶点均属于V’，则称G’是G的子图。例如，由图7-2所示的G3中的全部顶点和同v0相连的所有边就构成了G3的一个子图，由G3中的顶点v0、v1、v2和它们之间的所有边可构成G3的另一个子图。

（5）路径和回路

在一个图G中，从顶点v到顶点v’的一条路径（path）是一个顶点序列u1、u2、…、um，其中v=u1、v’=um，若此图是无向图，则(uj-1,uj)∈E(G)，2≤j≤m；若此图是有向图，则<uj-1,uj>∈E(G)，2≤j≤m。路径长度是指该路径上经过的边的数目。若一条路径上的所有顶点均不同（但开始和结束顶点可以相同），则称为简单路径，否则称为复杂路径。在一条简单路径中，若开始和结束顶点相同，则称为简单回路或简单环（cycle）。如在图7-2所示的G4中，从顶点c到顶点d的一条路径为c、e、a、b、d，其路径长度为4；路径a、b、e、a为一条简单回路，其路径长度为3；路径a、b、e、f、b是一条复杂路径，因为顶点b出现两次，其中包含着从顶点b到b的一条回路。

（6）连通和连通分量

在无向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的。若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。无向图G的极大连通子图称为G的连通分量。一个连通图可能有许多连通分量，只要能够连通所有顶点的子图都是它的连通分量，而在非连通图中，每个连通分量都只能连通其一部分顶点，而不能连通其全部顶点。例如，上面例子中给出的图G1和图G3都是连通图。图7-3(a)是一个非连通图，它包含有三个连通分量，分别画于图7-3(b)、(c)、(d)中，其中第一个连通顶点A、B、C的分量，可以有各种不同的连通形式，只要能把这三个顶点连接的所有子图都是一个连通分量，当然，要连接三个顶点则至少需要选取两条

非连通图和连通分量

（7）强连通图和强连通分量

在有向图G中，若从顶点vi到顶点vj有路径，则称从vi到vj是连通的。若有向图G中的任意两个顶点vi和vj都连通，即从vi到vj和从vj到vi都存在路径，则称有向图G是强连通图。有向图G的极大强连通子图称为G的强连通分量。一个强连通的有向图至少包含一个强连通分量，一个非强连通的有向图一定包含多个强连通分量。如图7-4(a)包含三个强连通分量，分别对应图7-4(b)、(c)、(d)所示。

有向图和强连通分量

（8）权和网

在一个图中，每条边可以标记上具有某种含义的数值，此数值称为该边的权（weight），通常权为一个非负实数。例如，对于一个反映城市交通线路的图，边上的权可表示该条线路的长度或等级；对于一个反映电子线路的图，边上的权可表示两端点间的电阻、电流或电压；对于一个反映零件装配的图，边上的权可表示一个端点需要装配另一个端点的零件的数量；对于一个反映工程进度的图，边上的权可表示从前一子工程到后一子工程所需要的天数。边上带有权的图称作带权图，也常称做网（network）。图7-5中的G5和G6就分别是一个无向带权图和有向带权图。

无向带权图和有向带权图