第7章图论基础与计算可视化
全部视频列播放表本站本章的学习目标包括:
●什么是图论?
●图论是怎么出现的?
●图论有哪些基本的概念?
●如何在Raptor中保存图的数据结构？
●邻接矩阵与邻接表有何不同?
●邻接矩阵与邻接表各自适用于哪些场合？
●如何在Raptor中实现邻接矩阵与邻接表？
●如何求解最小网络建设成本？
●如何求解最短旅行路线？
●如何求解最优商业网点布局？
●如何在Raptor中体现图类算法的可视性？
“七桥问题”是18世纪著名古典数学问题之一。18世纪初普鲁士的柯尼斯堡，普雷格尔河流经此镇，奈发夫岛位于河中，共有7座桥横跨河上，把全镇连接起来，如图7-1(a)所示。当欧拉在1736年访问柯尼斯堡时，他发现当地的市民正从事一项非常有趣的消遣活动。柯尼斯堡城中有一条名叫普雷格尔的河流横经其中，这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。这就是柯尼斯堡七桥问题。欧拉用点表示岛和陆地，两点之间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判断连通网络能否一笔画的问题，如图7-1(b)所示，并证明上述走法是不可能的。 图7-1七桥问题推进式搅拌桨
他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）必须由另一座桥离开此点。所以每行经一点时，需要两座桥（或线），从起点离开的线与最后回到始点的线亦需要两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。因此，连通网络可一笔画的充要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2。而七桥所成之图形中，没有一点含有偶数条数，因此上述的任务无法完成。 欧拉的这个考虑非常重要，也非常巧妙，它表明了数学家处理实际问题的独特之处
——把一个实际问题抽象成合适的“数学模型”。这种研究方法就是“数学模型方法”。这并不需要运用多么深奥的理论，但想到这一点，却是解决难题的关键。
接下来，欧拉运用网络中的一笔画定理为判断准则，很快地就判断出要一次不重复走遍哥尼斯堡的7座桥是不可能的。也就是说，多少年来，人们费脑费力寻的那种不重复的路线，根本就不存在。一个曾难住了那么多人的问题，竟是这么一个出人意料的答案！
1736年，欧拉在交给彼得堡科学院的《哥尼斯堡7座桥》的论文报告中，阐述了他的解题方法。他的巧解，为后来的数学新分支——拓扑学的建立奠定了基础。
七桥问题和欧拉定理。欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为欧拉定理：
⒈凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。
⒉凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。
⒊其他情况的图都不能一笔画出。(奇点数除以二便可算出此图需几笔画成。)
对于一个连通图，通常把从某节点出发一笔画成所经过的路线叫做欧拉路。人们又通常把一笔画成回到出发点的欧拉路叫做欧拉回路。具有欧拉回路的图叫做欧拉图。
有关七桥问题的讨论，表现出计算机出现之前，作为人的计算思维的出表现。而在计算机出现后，计算机科学发展出利用计算机自动解决类似的问题的方法，于是就有了以下的问题求解过程。
7.1图的定义和常用术语
破碎轨迹图7-2所示的(a)、（b）、（c）均为图(Graph)，它有若干个不同的点v1，v2，…，vn，在其中一些点
之间用直线或曲线连接。图中的这些点被称为顶点(vertex)或节点，连接顶点的曲线或直线称为边(edge)。通常将这种由若干个顶点以及连接某些顶点的边所组成的图形称为图，顶点通常被称作是图中的数据元素。 图7-2 有关图的案例
在线性结构中每个元素只有一个前趋和一个后续，而图7-2中的各个图则与之不同，它是一种较为复杂的非线性数据结构，在图结构中的任意两个元素之间都可能相互联系，即每个元素都可能有多个前趋或多个后续。图作为一种数据结构，通常又可被定义为：graph=(V，E)或G=(V，E)，即一个图是由顶点的集合V和边的集合E组成。
耐酸碱保护膜在图7-2中的⑴图中的边没有方向，用无序偶对（vi, vj）来表示。这类图称为无向图(undirected graph)。在记录或描述无向图时，(v1，v2 )等价于(v2，v1)。
在图7-2中(b)图中的边上有一个箭头，它表示边的方向，这类图称为有向图(directed graph)。在记录有向图时，<v1，v2 >与<v2，v1 >是两条不同的边。一般称这条连线为弧。弧用顶点的有序偶对<vi, vj>来表示，有序偶对的第一个节点vi被称为始点（或弧尾），在图中就是不带箭头的一端；有序偶对的第二个节点vj被称为终点（或弧头），在图中就是带箭头的一端。
图7-2中(a)图的顶点集合为：
V ＝｛v1，v2，v3，v4｝
边集合为：
E ＝｛（v1，v2），（v1，v3），（v2，v3），（v2，v4），（v3，v4）｝
图7-2中(b)图的顶点集合为：
V ＝｛v1，v2，v3，v4｝
弧集合为：
E ＝｛<v1，v2 >，<v1，v3 >，<v1，v4 >，<v2，v1 >，<v4，v2 >}
图的常用术语:
环(cycle)：图7-2中(c)图中的v1点本身也有边相连，这种边称为环。
有限图：顶点与边数均为有限的图，如图7-2中的三个图均属于有限图。
简单图：没有环且每两个顶点间最多只有一条边相连的图，如图7-2中的(a)图。
邻接与关联：当（v1，v2）∈E，或<v1，v2 >∈E，即v1，v2间有边相连时，则称v1和v2是相邻的，它们互为邻接点（adjacent），同时称（v1，v2）或<v1，v2 >是与顶点v1、v2相关联的边。
顶点的度数(degree)：从该顶点引出的边的条数，即与该顶点相关联的边的数目，简称度。图7-2中(a)、(b)图的各顶点的度见表7-1：
表7-1 图的度数
入度（in degree）：有向图中把以顶点v为终点的边的条数称为是顶点v的入度。
出度（out degree）：有向图中把以顶点v为起点的边的条数称为是顶点v的出度。
图7-2 (b)图各顶点的入度和出度见表7-2 (各顶点的入度与出度之和为该顶点的度数)：
v3。
路径与路径长度：在图G=( V，E)中，如果存在由不同的边(v1，v2 )，(v2，v3 )，…，(vn-1，vn )组成的序列，则称顶点v1，vn是连通的，顶点序列（v1，v2，v3，…，vn）是从顶点v1到顶点vn的一条道路。路长是道路上边的数目，v1到vn 的这条道路上的路长为n-1。
连通图：对于图中任意两个顶点vi 、vj ∈V ，vi 、vj 之间有道路相连，则称该图为连通图 (connected graph)，如图7-2中的 (a)图。
无向完全图：在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有n 个顶点的无向完全图中，有n(n-1)/2条边。
有向完全图：在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n 个顶点的有向完
全图中，有n(n-1)条边。
稠密图、稀疏图：若一个图接近完全图，称为稠密图；称
边数很少的图为稀疏图。
牙科涡轮机带权图：给图7-2中(a)图的边上附加一个代表性数据 (比如
表示长度、流量或其他 )，则称其为带权图。
网络：带权的连通图，如图7-3所示。
7.2图的存储
图的最常见的存储方式是用邻接矩阵和邻接表。
7.2.1邻接矩阵存储原理
邻接矩阵 (Adjacency Matrix)是表示顶点间邻接关系的矩阵。在图的邻接矩阵表示法中通常用一个邻接矩阵表示顶点间的相邻关系，另外用一个顺序表来存储顶点信息。
具有 n 个顶点的图 G=(V ， E)的邻接矩阵可以定义为：
A[i][j]=
若G 是网图，则邻接矩阵可定义为：
A[i][j]=
例7-1：使用邻接矩阵对有向图G1(参见图7-4)进行描述。
{ 1 若(v i ,v j )或<v i ,v j >是E(G)中的边
0 若(v i ,v j )或<v i ,v j >不是E(G)中的边 {
w ij 若(v i ,v j )或<v i ,v j >是E(G)中的边
∞ 若(v i ,v j )或<v i ,v j >不是E(G)中的边
图7-3 网络
图 7-4 有向图G1
解：图7-4中的有向图可以用一组基本参数描
述（参见图
7-5）:
G1.vexs: 顶点名表
G1.arcs: 弧邻接矩阵
G1.vexnum：顶点数量
G1.arcnum：弧的数量
G1.kind:DG 表示有向图
邻接矩阵表示法对于以图的顶点为主的运算比较适用，除完全图外，其他图的邻接矩阵有许多零元素，特别是当vexs 值较大，而边数(arcs)又少时，则此矩阵称为稀疏矩阵，浪费存储空间。
从图7-5可以看出，有向图邻接矩阵的每一行，可以统计该行数据所描述顶点的出度，而每一列，可以统计该顶点的入度。扩管机
在该矩左上到右下的数据对角线上，该对角线上的所有数据为0，以该对角线对称轴的数据不对称。
例7-2：使用邻接矩阵对无向图G2(参见图7-6)进
行描述。
图 7-6 无向图G2
图7-6中的有向图可以用一组基本参数描述（参见图7-7）， G2.kind:UDG 表示无图7-7 G2的基本描述 图7-5 G1的基本描述
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议