《图及其图的概念.doc》由会员分享，可在线阅读，更多相关《图及其图的概念.doc（3页珍藏版）》请在金锄头文库上搜索。
1、图及其图的概念在图结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，图的应用极为广泛。如：电子线路分析、寻找最短路径、工程计划分析、统计力学、控制论等技术领域都把图结构作为解决问题的主要手段之一。相关定义（一）图图G由两个集合V和E组成。V是一个有限的非空的顶点集合，E是边的集合。图1中G1、G2、G3就是三个图。图 1图G1、G2中代表边的顶点偶数对是无序的，则称图G1、G2为无向图，边(Vi，Vj) 和(Vj，Vi)代表的是同一条边。图G3中代表边的顶点偶数对是有序的，则称图G3为有向图，有向图中的边又称为弧。弧(Vi，Vj)表示从顶点i指向顶点j，顶点Vi称为
2、弧(Vi，Vj)的尾，Vj称为弧(Vi，Vj) 的头。故有向图中(Vi，Vj)和(Vj，Vi)代表着两条不同的弧。在一个有个顶点的无向图中，若每一个顶点和其它（-1）个顶点之间都有边相连，则共有(1)/2条边。这是任何个顶点的无向图的最大边数。一个拥有(1)/2条边的个顶点的无向图称为无向完全图。如图13.11中的G1是有4 个顶点的无向完全图。类似地在有个顶点的有向图中，最多可能有（）条弧， 具有（）条弧的个顶点的有向图称为有向完全图。在一些实际应用问题中，图的边往往与具有一定意义的数相关，这种与图的边相关的数叫权，这个权，可以表示从一个顶点到另一个顶点的距离或花费的代价等等。 我们称边拥有
3、权的图为网。（二）邻接若(V1，V2)是E(G)中的一条边，则称顶点V1和V2为相邻接的顶点，而称边(V1，V2)是依附于顶点V1和V2的边。例如，在图13.11的G2中，与V2顶点相邻接的顶点是V1、V4和V5。若(V1，V2)是有向图G中的一条弧，则称顶点V1邻接至顶点V2，顶点V2邻接至顶点V1，弧(V1，V2) 依附于顶点V1和V2。（三）度依附于顶点的边的数目称为该顶点的度。有向图中，把以顶点V 为头的弧的数目称作顶点V的入度，而把以V为尾的弧的数目称之为顶点V的出度，顶点V的出度与入度之和就是它的度。（四）路径在图G中，从顶点Vp到顶点Vq的路径是顶点序列(Vp，Vi1，Vi2，.
4、，Vin，Vq)，且( Vp，Vi1)，(Vi1，Vi2)，.，(Vin，Vq)是E(G)中的边。若G是有向图，则路径也是有向的，由弧(Vp，Vi1)，(Vi1，Vi2)，.，(Vin， Vq)组成。路径上的边数称为路径长度。在一条路径中，如果除了第一个顶点和最后一个顶点外，其余顶点都各不相同，则称这样的路径为简单路径。例如，在图13.11中，由边(V1，V2)，(V2，V4)，(V4，V3)构成从顶点V1到顶点V3的路径可以写成顶点序列(V1，V2，V4，V3)。路径(V1，V2，V4，V3)和(V1，V2，V4，V2)都是长度为3的路径，显然，前者是一条简单的路径，而后者则不是。 我们把第
5、一个顶点和最后一个顶点相同的路径称为回路，若一个简单路径的第一个顶点和最后一个顶点相同，则称为简单回路。图的存储结构表示图的存储结构有多种形式，我们只介绍其中常用的两种，即邻接矩阵表示法和邻接表表示法。 （一）邻接矩阵表示法若某图G有个顶点V1，V2，.，Vn，则其邻接矩阵是这样的一个阶方阵：1 (顶点Vi，Vj有相连)A(i，j)0 (顶点Vi，Vj不相连)显然，无向图的邻接矩阵是对称的，因此，在赋值时只要对上三角矩阵(或下三角矩阵)赋值即可。而有向图的邻接矩阵不一定是对称的。对于网的邻接矩阵可定义为：Wij (顶点Vi，Vj有相连时的权值)A(i，j)0 (顶点Vi，Vj不相连)采用邻接矩
6、阵的方法来表示一个图，我们可以很容易地判定任意两个顶点之间是否有边相连，并容易求得各个顶点的度，但是所耗费的存储空间是十分大的-需要个存储单元。当一个图的顶点数较多而边数较少时，这时对应的邻接矩阵为稀疏矩阵，这种存储结构浪费了许多存储单元，在这种情况下，也可采取图的另一种表示方法-邻接表表示法。（二）邻接表表示法这种表示法是为图中的每一个顶点Vi建立一个链表，即把邻接矩阵中的行表示成个链表。对于无向图，第i个链表是把图中与顶点Vi相邻接的所有顶点链接在一起， 链表中的每个结点表示一条依附于顶点Vi的边（见图13.12()）。而有向图的第i 个链表是把邻接自顶点Vi的所有顶点链接在一起，链表中的
7、每个结点表示一条以顶点Vi为尾的弧（见图13.12()）。链表的结构为，每个结点有两个域：顶点域-用来表示与顶点Vi相邻接的顶点序号；指针域-用来指向依附于顶点Vi的另一条边或弧。对于网，结点中还需增加一个存放权值的域，每个链表都有一个起始结点，为处理方便，我们把邻结表的所有链表的头指针集中存放在一个数组中，这样就可以方便地随机访问图中每个结点的链表。 图 2 图的邻接表表示法对于一个有个顶点和条边的无向图，若采用这种存储表示法，需要个头结点和个表结点，每个表结点有两个域（对于网则有三个）显然，在边稀疏的情况下，采用邻接表比邻接矩阵要省空间。图的基本知识及有关概念图(Graph)是一种复杂的非
8、线性结构。在人工智能、工程、数学、物理、化学、生物和计算机科学等领域中，图结构有着广泛的应用。图的二元组定义 图G由两个集合V和E组成，记为： G=(V，E)其中：V是顶点的有穷非空集合，E是V中顶点偶对(称为边)的有穷集。 通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。有向图和无向图1有向图 若图G中的每条边都是有方向的，则称G为有向图(Digraph)。（1）有向边的表示 在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head
9、)。 【例】表示一条有向边，vi是边的始点(起点)，vj是边的终点。因此，和是两条不同的有向边。（2）有向图的表示 【例】下面(a)图中G1是一个有向图。图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为： V(G1)=v1，v2，v3 E(G1)=，2无向图 若图G中的每条边都是没有方向的，则称G为无向图(Undigraph)。（1）无向边的表示 无向图中的边均是顶点的无序对，无序对通常用圆括号表示。 【例】无序对(vi，vj)和(vj，vi)表示同一条边。（2）无向图的表示 【例】下面(b)图中的G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为： V(G2)=v
10、1，v2，v3，v4 E(G2)=(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4) V(G3)=v1，v2，v3，v4，v5，v6，v7 E(G3)=(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7) 注意： 在以下讨论中，不考虑顶点到其自身的边。即若(v1，v2)或是E(G)中的一条边，则要求v1v2。此外，不允许一条边在图中重复出现，即只讨论简单的图。3图G的顶点数n和边数e的关系（1）若G是无向图，则0en(n-1)/2 恰有n(n-1)/2条边的无向图称无向完全图(Undireet-ed Complete Graph)（2）若G是有向图，则0en(n-1)。 恰有n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。 注意：完全图具有最多的边数。任意一对顶点间均有边相连。 【例】上面(b)图的G2就是具有4个顶点的无向完全图。
