全屏显示专题章节

图7－1中G2每条边都没有方向，这样的图称为无向图（undigraph），图G1每条边都有方向，称为有向图（digraph）。

图7－1有向图G1中＜1，2＞属于图中边的集合，则＜1，2＞表示从顶点1到顶点2的一条弧（arc），并称1为弧尾（tail）或起始点，称2为弧头（head）或终端点。

图7－1无向图G2中，（1，2）属于图中边的集合，表示1和2之间的一条边（edge），同时2和1之间也有一条边，因为这条边是无向的，此时的图称为无向图。

2.完全图－稀疏图－稠密图－子图

我们设n表示图中顶点的个数，用e表示图中边或弧的数目，并且不考虑图中每个顶点到其自身的边或弧。即若＜vi，vj＞∈V（边集合），则vi≠vj。对于无向图而言，其边数e的取值范围是0～n（n－1）／2。我们称有n（n－1）／2条边（图中每个顶点和其余n－1个顶点都有边相连）的无向图为无向完全图。对于有向图而言，其边数e的取值范围是0～n（n－1）。我们称有n（n－1）条边（图中每个顶点和其余n－1个顶点都有弧相连）的有向图为有向完全图（如图7－2所示）。对于有很少条边的图（e＜nlog2n）称为稀疏图，反之称为稠密图。

设有两个图G＝（V，｛E｝）和图G′＝（v′，｛E′｝），若v′≤v且E′≤E，则称图G′为G的子图。图7.3给出了几个子图示例。

3.邻接点顶点的度（出度、入度）、权值与网

对于无向图G＝（V，｛E｝），如果边（v，v′）∈E，则称顶点v、v′互为邻接点，即v、v′相邻接。边（v，v′）依附于顶点v和v′，或者说边（v，v′）与顶点v和v′相关联。对于有向图G＝（V，｛A｝）而言，若弧＜v，v′＞∈A，则称顶点v邻接到顶点v′，顶点v′邻接自顶点v，或者说弧＜v，v′＞与顶点v、v′相关联。

（2）度、入度和出度

对于无向图而言，顶点v的度是指和v相关联的边的数目，记作TD（v）。例如，图7－2中G2中顶点A的度是3，B的度是3；在有向图中顶点v的度分出度和入度两部分，其中以顶点v为弧头的弧的数目称为该顶点的入度，记作ID（v），以顶点v为弧尾的弧的数目称为该顶点的出度，记作OD（v），则顶点v的度为TD（v）＝ID（v）＋OD（v）。例如，图G1中顶点A的入度是ID（A）＝3，出度OD（A）＝3，顶点A的度TD（A）＝ID（A）＋OD（A）＝6。

在实际应用中，有时图的边或弧往往与具有一定意义的数有关，即每一条边都有与它相关的数值，称为权，这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息。我们将这种带权的图叫作赋权图或网，如图7－4所示。

（4）路径与回路

无向图G＝（V，｛E｝）中从顶点v到v′的路径是一个顶点序列vi0，vi1，vi2，…，vin，其中（vij－1，vij）∈E，1≤j≤n。如果图7－5是有向图，则路径也是有向的，顶点序列应满足＜vij－1，vij＞∈A，1≤j≤n。路径的长度是指路径上经过的弧或边的数目。在一个路径中，若其第一个顶点和最后一个顶点是相同的，即v＝v′，则称该路径为一个回路或环。若表示路径的顶点序列中的顶点各不相同，则称这样的路径为简单路径。除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路为简单回路。

如图7－5中，1到3的路径：1，2，3，5，6，3，路径长度是5；简单路径：1，2，3，5；回路：1，2，3，5，6，3，1；简单回路：3，5，6，3。

4.连通图－生成树

在无向图G＝（V，｛E｝）中，若从vi到vj有路径相通，则称顶点vi与vj是连通的。如果对于图中的任意两个顶点vi，vj∈V，vi、vj都是连通的，则称该无向图G为连通图。例如，图7－6中G1就是连通图，无向图中的极大连通子图称为该无向图的连通分量，如图7－7所示。

在有向图G＝（V，｛A｝）中，若对于每对顶点vi，vj∈V且vi≠vj，从vi到vj和vj到vi都有路径，则称该有向图为强连通图。例如，图7－6中G2就是强连通图，有向图的极大强连通子图称作有向图的强连通分量，如图7－8所示。

一个连通图的生成树是指一个极小连通子图，它含有图中的全部顶点，但只有足以构成一棵树的n－1条边，如图7－9所示。如果在一棵生成树上添加一条边，必定构成一个环；因为这条边使得它依附的两个顶点之间有了第二条路经。一棵有n个顶点的生成树有且仅有n－1条边，如果它多于n－1条边，则一定有环。但是，有n－1条边的图不一定是生成树。如果一个图有n个顶点和小于n－1条边，则该图一定是非连通图。

一个图的生成森林有若干棵生成树，含有图中全部顶点，但只有足以构成若干棵不相交的树的边，如图7－10所示，即图的各连通分量对应的生成树构成的森林。