NOIP高中信息技术竞赛资料 - -数据结构(9)

第6章 图

第6章 图

图(Graph)是一种复杂的非线性结构，在图结构中，对结点的前驱和后继的个数没有任何限制，结点之间的关系是任意的，图中任意两个结点之间都可能有关系。图结构在计算机科学、人工智能、工程、数学、物理等领域中，有着广泛的应用。

6.1图的概念

1.图的二元组定义

图G由两个集合V和E组成，记为：G=(V，E)

其中：V是有限的非空集合，V中的元素称为顶点或结点，E是V中顶点偶对(vi,vj)的集合，E中的元素称为边。

说明：图G的顶点集和边集也可记为V(G)和E(G)。E(G)可以是空集，若为空，则图G只有顶点没有边；图中的边(vi,vj)描述了两个顶点之间是相关的。

图6.1中G1给出了一个图的示例，在该图中： 集合V＝{v1,v2,v3,v4,v5}；

集合E＝{(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5) }。

V1 V3 V4 V5 V3 V4 V2 V1 V2 图6.1 无向图G1 图6.2 有向图G2

2.无向图和有向图 （1）无向图

若图G中的每条边都是没有方向的，则称G为无向图。

无向图中边的表示：无向图中的边均是顶点的无序对，无序对通常用圆括号表示，无序对(vi,vj)和(vj,vi) 表示图中的同一条边。

如图6.1所示图G1是一个无向图。 （2）有向图

若图G中的每条边都是有方向的，则称G为有向图。

有向图中边的表示：有向图中的边是由顶点的有序对组成，有序对通常用尖括号表示，有序对和 表示的是图中不同的边。有向边也称为弧，边的始点称为弧尾，终点称为弧头。

第6章 图

说明：

①若(v1，v2)或是E(G)中的一条边，则要求v1≠v2； ②不允许一条边在图中重复出现；

③不允许在同一个图中既有有向边又有无向边。 如图6.2所示图G2是一个有向图： G2=(V2,E2) V2={v1,v2,v3,v4}

E2={,,,} （3）完全图

①无向完全图：若G是具有n个顶点e条边的无向图，则顶点数与边数的关系为0≤e≤n(n-1)/2。把恰有n(n-1)/2条边的无向图称为无向完全图。

②有向完全图：若G是具有n个顶点e条边的有向图，则顶点数与边数的关系为0≤e≤n(n-1)。把恰有n(n-1)条边的有向图称为有向完全图。

说明：完全图具有最多的边数。任意一对顶点间均有边相连。 3.图的边和顶点的关系 （1）无向边和顶点关系

若(vi,vj)是一条无向边，则称顶点vi和vj互为邻接顶点，或称vi和vj相邻接；并称(vi,vj)依附或关联于顶点vi和vj，或称(vi,vj)与顶点vi和vj相关联。

（2）有向边和顶点关系

若是一条有向边，则称顶点vi邻接到vj，顶点vi邻接于顶点vj；并称边关联于vi和vj或称与顶点vi和vj相关联。

（3）顶点的度

①无向图中顶点v的度：无向图中顶点v的度是关联于该顶点的边的数目，记为D(v)。

②有向图顶点v的入度：有向图中，以顶点v为终点的边的数目称为v的入度，记为ID(v)。

③有向图顶点v的出度：有向图中，以顶点v为始点的边的数目，称为v的出度，记为OD(v)

④有向图顶点v的度：有向图中，顶点v的度定义为该顶点的入度和出度之和，即D(v)=ID(v)+OD(v)。

⑤无论有向图还是无向图，顶点数n、边数e和度数之间有如下关系：

第6章 图

1ne??D(vi)

2i?1例如，在图6.1无向图G1中有：

D(v1)=2 D(v2)=3 D(v3)=3 D(v4)=2 D(v5)=2 在图6.2有向图G2中有：

ID(v1)=1 OD(v1)=2 D(v1)=3 ID(v2)=1 OD(v2)=0 D(v2)=1 ID(v3)=1 OD(v3)=1 D(v3)=2 ID(v4)=1 OD(v4)=1 D(v4)=2 4.子图

设G=(V，E)是一个图，若V'是V的子集，E'是E的子集，且E'中的边所关联的顶点均在V'中，则G'=(V'，E')也是一个图，并称其为G的子图。

图G1和G2的子图如图6.3所示。

V1 V2 V1

V3

V3 V4 V5

V4 图6.3 图G1和G2的两个子图

5.路径

（1）无向图的路径

在无向图G中，若存在一个顶点序列vp，vi1，vi2，…，vim，vq，使得(vp,vi1)，(vi1,vi2)，…，(vim,vq)均属于E(G)，则称该序列为顶点vp到vq的一条路径。

（2）有向图的路径

在有向图G中，若存在一个顶点序列vp，vi1，vi2，…，vim，vq，使得有向边，，…，均属于E(G) ，则称该序列为顶点vp到vq的一条路径。

（3）路径长度

路径长度定义为该路径上边的数目。 （4）简单路径

若一条路径除两端顶点可以相同外，其余顶点均不相同，则称此路径为一条简单路径。

第6章 图

（5）回路

起点和终点相同的路径称为回路。 （6）简单回路或简单环

起点和终点相同的简单路径称为简单回路或简单环。 （7）有根图和图的根

在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为有根图，v称作图的根。

6.连通图和连通分量 （1）顶点间的连通性

在无向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的。 （2）连通图

若在无向图G中，任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图。

（3）连通分量

无向图G的极大连通子图称为G的连通分量。示意图见图6.4。

A C D E F E F B A B C D (a) 无向图G3 (b)G3的两个连通分量

图6.4 无向图及连通分量

说明：

①任何连通图的连通分量只有一个，即是其自身； ②非连通的无向图有多个连通分量。

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

（1）强连通图

有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。

（2）强连通分量

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

第6章 图

说明：

①强连通图只有一个强连通分量，即是其自身； ②非强连通的有向图有多个强连分量。 有向图的强连通分量见图6.5。

V1 V2 V3 V4 8.网络

图6.5 有向图G2的两个强连通分量

若将图的每条边都赋上一个权，则称这种带权图为网络(Network)。 如图6.6。

A 5 C 7 2 8 B 3 D 图6.6 一个无向网

说明：权是表示两个顶点之间的距离、耗费等具有某种意义的数。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库NOIP高中信息技术竞赛资料 - -数据结构(9)在线全文阅读。