图及其图的概念.doc

图及其图的概念
　　在图结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，图的应用极为广泛。如：电子线路分析、寻找最短路径、工程计划分析、统计力学、控制论等技术领域都把图结构作为解决问题的主要手段之一。
相关定义
　　（一）图
　　图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称为弧(Vi，Vj)的尾，Vj称为弧(Vi，Vj) 的头。故有向图中(Vi，Vj)和(Vj，Vi)代表着两条不同的弧。
　　在一个有ｎ个顶点的无向图中，若每一个顶点和其它（ｎ-1）个顶点之间都有边相连，则共有ｎ(ｎ－1)/2条边。这是任何ｎ个顶点的无向图的最大边数。一个拥有ｎ(ｎ－1)/2条边的ｎ个顶点的无向图称为无向完全图。如图13.11中的G1是有4 个顶点的无向完全图。类似地在有ｎ个顶点的有向图中，最多可能有ｎ（ｎ－１）条弧， 具有ｎ（ｎ－１）条弧的ｎ个顶点的有向图称为有向完全图。
　　在一些实际应用问题中，图的边往往与具有一定意义的数相关，这种与图的边相关的数叫权，这个权，可以表示从一个顶点到另一个顶点的距离或花费的代价等等。 我们称边拥有权的图为网。
　　（二）邻接
　　若(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，......，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的路径，显然，前者是一条简单的路径，而后者则不是。 我们把第一个顶点和最后一个顶点相同的路径称为回路，若一个简单路径的第一个顶点和最后一个顶点相同，则称为简单回路。
图的存储结构
　　表示图的存储结构有多种形式，我们只介绍其中常用的两种，即邻接矩阵表示法和邻接表表示法。
　 （一）邻接矩阵表示法
　　若某图G有ｎ个顶点V1，V2，......，Vn，则其邻接矩阵是这样的一个ｎ阶方阵：
　　　　　　　　1 (顶点Vi，Vj有相连)
　　A(i，j)＝{
　　　　　　　　0 (顶点Vi，Vj不相连)
显然，无向图的邻接矩阵是对称的，因此，在赋值时只要对上三角矩阵(或下三角矩阵)赋值即可。而有向图的邻接矩阵不一定是对称的。
　　对于网的邻接矩阵可定义为：
　　　　　　　　Wij (顶点Vi，Vj有相连时的权值)
　　A(i，j)＝{
　　　　　　　　0 (顶点Vi，Vj不相连)
　　采用邻接矩阵的方法来表示一个图，我们可以很容易地判定任意两个顶点之间是否有边相连，并容易求得各个顶点的度，但是所耗费的存储空间是十分大的--需要ｎ×ｎ个存储单元。当一个图的顶点数较多而边数较少时，这时对应的邻接矩阵为稀疏矩阵，这种存储结构浪费了许多存储单元，在这种情况下，也可采取图的另一种表示方法--邻接表表示法。
　　（二）邻接表表示法
　　这种表示法是为图中的每一个顶点Vi建立一个链表，即把邻接矩阵中的ｎ行表示成ｎ个链表。对于无向图，第i个链表是把图中与顶点Vi相邻接的所有顶点链接在一起， 链表中的每个结点表示一条依附于顶点Vi的边（见图13.12(ａ)）。而有向图的第i 个链表是把邻接自顶点Vi的所有顶点链接在一起，链表中的每个结点表示一条以顶点Vi为尾的弧（见图13.12(ｂ)）。链表的结构为，每个结点有两个域：
　　顶点域--用来表示与顶点Vi相邻接的顶点序号；
　　指针域--用来指向依附于顶点Vi的另一条边或弧。
　　对于网，结点中还需增加一个存放权值的域，每个链表都有一个起始结点，为处理方便，我们把邻结表的所有链表的头指针集中存放在一个数组中，这样就可以方便地随机访问图中每个结点的链表。

　　　　　　　　　　　　　图 2 图的邻接表表示法
　　对于一个有ｎ个顶点和ｍ条边的无向图，若采用这种存储表示法，需要ｎ个头结点和２ｍ个表结点，每个表结点有两个域（对于网则有三个）显然，在边稀疏的情况下，采用邻接表比邻接矩阵要省空间。
图的基本知识及有关概念
图(Graph)是一种复杂的非线性结构。在人工智能、工程、数学、物理、化学、生物和计算机科学等领域中，图结构有着广泛的应用。
图的二元组定义
　图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)。
【例】<vi，vj>表示一条有向边，vi是边的始点(起点)，vj是边的终点。因此，<vi，vj>和<vj，vi>是两条不同的有向边。
（2）有向图的表示
【例】下面(a)图中G1是一个有向图。图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为：
V(G1)={v1，v2，v3}
E(G1)={<v1，v2>，<v2，v1>，<v2，v3>}
2．无向图
　若图G中的每条边都是没有方向的，则称G为无向图(Undigraph)。
（1）无向边的表示
　无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
【例】无序对(vi，vj)和(vj，vi)表示同一条边。
（2）无向图的表示
【例】下面(b)图中的G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为：
V(G2)={v1，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)或<vl，v2>是E(G)中的一条边，则要求v1≠v2。此外，不允许一条边在图中重复出现，即只讨论简单的图。
3．图G的顶点数n和边数e的关系
（1）若G是无向图，则0≤e≤n(n-1)/2
　恰有n(n-1)/2条边的无向图称无向完全图(Undireet-ed Complete Graph)
（2）若G是有向图，则0≤e≤n(n-1)。
　恰有n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。
注意：完全图具有最多的边数。任意一对顶点间均有边相连。
【例】上面(b)图的G2就是具有4个顶点的无向完全图。