00-1010 (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}

在日常生活中，图形的应用随处可见。比如各种交通图、线路图、结构图、流程图等等。

无图

有向图

00-1010在无向图中，如果有一条边(vi，vj)，那么vi和vj就是这条边的两个Endpoint，并且它们是相邻的，也就是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的外边和内边)；顶点vj。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；可以类似地分析其他顶点。

00-1010无向图中顶点V的度数定义为以此顶点为端点的边数，表示为D(v)。在G1，如图7-1所示，v0顶点的度数是4，v1顶点的度数是2。有向图中顶点V的度数可分为内度数和外度数。In-degree是顶点的边数，记录为ID (V)。外倾角是顶点的边数，记录为OD(V)；一个顶点的度数等于它的内度数和外度数之和，即D(v)=ID(v) OD(v)。在图7-1所示的G2中，顶点A的入度为0，出度为2，度为2；顶点C的入度为2，出度为2，度为4。

如果图中有n个顶点和e条边，则图的所有顶点的度和边数e满足以下关系：

很容易理解，因为每条边连接两个顶点，这样这两个顶点的度数分别增加1，和增加2，那么所有顶点的度数都是所有边的两倍，或者边的数量是所有顶点的一半。

图的定义

如果无向图中每两个顶点之间有一条边，有向图中每两个顶点之间有两条方向相反的边，这样的图称为完全图。显然，如果完整的图是无向图，则该图包含

1/2 n(n-1)

边缘；如果一个完整的图是有向的，则该图包含n(n-1)

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

m=pc">

完全图和稀疏图

（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；震动的雪碧、b、e、a为一条简单回路，其路径长度为3；震动的雪碧、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就分别是一个无向带权图和有向带权图。

无向带权图和有向带权图