下载文档原格式
课程名称图论入门论文题目图论在物流物配送上的应用指导教师刘颖学院管理学院姓名郭凤午学号2011030284图论在物流货物配送中的应用摘要：最短路径问题对于节约人们的时间成本具有重要意义。
最短路问题是图论理论的一个经典问题。
寻找最短路径就是在指定网络中两结点间找一条距离最小的路。
最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。
它可被用来解决厂区布局、管路铺设、线路安装等实际问题。
本文介绍了图论的起源和发展、最短路径问题及其算法，并应用图论最短路径问题的分析方法解决物流货物配送中问题。
1 引言数学是一门古老的学科，它已经有了几千年的历史。
然而，图论作为数学的一个分支，却只有200多年的历史，但是其发展十分迅速。
图论是以图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系。
事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟，而且它具有形象直观的特点，在图中点的位置和线的长短曲直无关紧要[1]。
图论的发展大力地推进了科学文明的进步，解决了很多实际应用问题。
图论是数学领域中发展最快的分支之一，它以图为研究对象。
图论中的图是有若干给定的点及连接两点的线所构成的图形，这种图形常用来描述某些事物之间的某种特定关系，用来代表事物，用连接两点的线表示相应两个事物间具有这种关系。
图论本身是应用数学的一部分，因此，历史上图论曾经被好多位数学家各自独立的建立过。
关于图论的文字记载最早出现在欧拉1736年的论文中，他所考虑的原始问题有很强的实际背景。
数学史上著名的七桥问题欧拉只用了一步就证明了不重复地通过7座桥的路线是根本不存在的!这是拓扑学研究的先声。
图的染色问题一直是图论研究的焦点问题。
数学家赫伍德成功地运用肯普的方法证明了五色定理，即一张地图能够用五种或者更少的颜色染色。
美国伊利诺斯大学的黑肯和阿佩尔，经过四年的艰苦工作．终于完成了四色猜想的证明。
图论毕业论文图论是数学的一个分支，主要研究图的性质和结构。
它对于解决各种实际问题具有重要的意义，如交通网络优化、电子芯片设计等。
本文将就图论的概念、基本性质以及其在实际问题中的应用等方面进行论述。
首先，图论是研究图的性质和结构的数学学科。
图是由节点和边组成的数学结构，可以用来描述各种实际问题，如交通网络、社交关系等。
图由节点和边构成，节点表示图中的元素或对象，边表示节点之间的关系。
图可以分为有向图和无向图，有向图中的边有方向性，无向图中的边没有方向性。
图的回路是指从一个节点出发，沿着边走过一系列节点之后再回到起始节点的路径。
图的连通性是指图中的任意两个节点之间存在一条路径。
其次，图论具有一些基本性质。
首先是图的度数。
图的度数是指图中一个节点与其相邻节点的边的个数。
度数为奇数的节点称为奇节点，度数为偶数的节点称为偶节点。
其次是图的邻接矩阵和关联矩阵。
邻接矩阵是一个n×n的矩阵，其中n是图的节点数，矩阵元素a_ij表示节点i与节点j之间是否存在边。
关联矩阵是一个n×m的矩阵，其中n是图的节点数，m是图的边数，矩阵元素b_ij表示节点i是否与边j相关联。
最后是图的连通性。
图的连通性决定了图中是否存在从一个节点到达另一个节点的路径。
如果图中的任意两个节点之间都存在路径，则图是连通的；否则，图是非连通的。
最后，图论在实际问题中有广泛的应用。
首先是交通网络优化。
图论可以用来优化交通网络中的路径规划和交通流量分析等问题，从而提高交通的效率和安全性。
其次是电子芯片设计。
图论可以用来分析电子芯片中各个元件之间的连接关系，从而提高芯片的性能和可靠性。
此外，图论还可以用来解决诸如社交网络分析、物流规划等实际问题。
综上所述，图论是数学的一个分支，主要研究图的性质和结构。
它对于解决各种实际问题具有重要的意义。
未来，随着科学技术的不断发展，图论在实际问题中的应用将会越来越广泛。
因此，对图论的进一步研究和应用具有重要的意义。
图论算法应用【图论的应用】数学与统计学院图论论文课程名称图论及其应用题目图论中的应用姓名邵雪莲学号 [1**********]19专业数学与应用数学10级1班图论的应用摘要：图论从诞生至今已近300年，但很多难题很一直没有很好地解决。
随着计算机科学的发展战略，图论又重新成为了人们研究讨论的热点，图形是一种描述和解决问题有效的手段，这里给出图论现实生活在现实生活之中的一些应用。
引言：虽然最早的图论问题追溯1736年(哥尼斯堡七桥间题) ，而且在19世纪关于图论的推算出许多重要结论已得出。
但是直到20世纪20年代图论才引起广大学者的注意并得以广泛接受和。
图论即形像地用一些点以及点与点之间的直播间构成的图或网络来表示具体问题。
利用图与网络的特点来解决系统中的善用问题，比用线性规划等其他模型来求解往往三维要简单、有效得多。
同调代数就是研究图和网络模型特点、性质和方式的理论。
图论在许多领域,诸如物理、化学、运筹学、计算机科学、信息论、控制论、网络理论、社会科学以及经济管理等各方面都有广泛的应用, 它已经广泛地应用于实际生活、生产和科学研究中会。
1首先：图论可以逐步解决一些看似很难却实际上却很简单的问题：例一：一个部门中有25人，由于纠纷而紧绷使得关系极为紧张，是否可便每个人与5个人相处融洽? 则可以建立一个图的模型，最基本的问题是如何描述它—什么是结点，什么是边? 在本问题中，没有太多的选择，只有人和纠纷。
我们可试着用结点来代表人。
用边来领袖人物图中结点之间的关系，这是很常见的。
在这里结点之间的关系是“关系是否融洽”，因此，若两个结点(人) 关系融洽，那么就在它们之间以致一条边。
现在假设每个人与其他5个人关系融洽。
在图显示出我们所描述的图的一部分，小张与小王、小李、小赵、小黄和小吴关系密切，再没有其他人。
25个人均是此种情况。
这是否可能? 在图论中，一个重要的推论:在任意图中，具有奇数度的结点个数必为偶数。
课程名称图论入门论文题目图论在物流物配送上的应用指导教师刘颖学院管理学院姓名郭凤午学号2011030284图论在物流货物配送中的应用摘要：最短路径问题对于节约人们的时间成本具有重要意义。
最短路问题是图论理论的一个经典问题。
寻找最短路径就是在指定网络中两结点间找一条距离最小的路。
最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。
它可被用来解决厂区布局、管路铺设、线路安装等实际问题。
本文介绍了图论的起源和发展、最短路径问题及其算法，并应用图论最短路径问题的分析方法解决物流货物配送中问题。
1 引言数学是一门古老的学科，它已经有了几千年的历史。
然而，图论作为数学的一个分支，却只有200多年的历史，但是其发展十分迅速。
图论是以图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系。
事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟，而且它具有形象直观的特点，在图中点的位置和线的长短曲直无关紧要[1]。
图论的发展大力地推进了科学文明的进步，解决了很多实际应用问题。
图论是数学领域中发展最快的分支之一，它以图为研究对象。
图论中的图是有若干给定的点及连接两点的线所构成的图形，这种图形常用来描述某些事物之间的某种特定关系，用来代表事物，用连接两点的线表示相应两个事物间具有这种关系。
图论本身是应用数学的一部分，因此，历史上图论曾经被好多位数学家各自独立的建立过。
关于图论的文字记载最早出现在欧拉1736年的论文中，他所考虑的原始问题有很强的实际背景。
数学史上著名的七桥问题欧拉只用了一步就证明了不重复地通过7座桥的路线是根本不存在的!这是拓扑学研究的先声。
图的染色问题一直是图论研究的焦点问题。
数学家赫伍德成功地运用肯普的方法证明了五色定理，即一张地图能够用五种或者更少的颜色染色。
美国伊利诺斯大学的黑肯和阿佩尔，经过四年的艰苦工作．终于完成了四色猜想的证明。
Dijkstra 算法在移动通信中的应用李鹏翔 信息与通信工程学院1、问题的提出在移动通信中，尤其是端到端的通信中，常常会涉及到求最短路问题。
但是，这里的最短路不仅仅指一般地理意义上的距离最短。
由于基站与基站之间、基站与终端之间的距离、阴影等因素的相同，不同设备之间构建的通信模型也各不相同，为了便于量化，我们将这些因素归一化，赋予它们以不同的权值，权值越小说明信道状况越好，信号传输需要的资源越少。
端到端之间最短路问题实际上是寻找所有可能路径之中权值最小的路径。
一个实际问题如下：上图中，我们假设1v 与6v 为两个移动用户，2345,,,v v v v 为四个基站，用户只能与和它相邻的基站进行通信，基站除了与用户外还能与和它相邻的基站进行通信。
基站与基站间、基站与终端间的权值不同，代表不同设备之间的环境状况不同，求从1v 到6v 应选择哪一路径使权值最小。
2、算法简介Dijkstra 算法是图论中确定最短路的基本方法，也是其它算法的基础。
Dijkstra 算法基本步骤： 令：{}{}_23,1,,,,i n s v i s v v v === 并令：{()()10,j j W v T v v s-==∞∈（1）、对j v s -∈，求()(){}()min ,j i ij j T v W v w T v +=。
（2）、求(){}min j j v sT v ∈得()k T v ，使()k T v =(){}min j j v sT v ∈令()()k k W v T v =（3）、若k n v v =则已找到1v 到n v 的最短路距离()k W v ，否则令i k =从s -中删去i v 转（1）。
这样经过有限次迭代则可以求出1v 到n v 的最短路线，可以用一个流程图来表示：第一步：先取()10W v =意即1v 到1v 的距离为0，而()j T v 是对()j T v 所赋的初值。
第二步：利用()1W v 已知，根据()(){}min ,j i ij T v W v w +对()j T v 进行修正。
1.引言图论是数学的一个分支，并且是组合数学和应用数学的一部分。
它以图做为研究对象，而图是由若干节点和节点之间的边所构成的图型。
在图论中，图往往是某个具体现实生活中问题的数学抽象，可以说，图中的节点代表着生活中的某些特定事物，而节点之间的边则代表着节点之间的特定联系。
图论这门学科需要解决的就是如何利用数学知识去解决它们之间的关系。
图论最早起源于1736年著名的柯尼斯堡七桥问题[1]。
这个问题的内容是：在柯尼斯堡的普莱格尔河上有七座桥将河中的岛屿与河岸连接起来。
问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，最后再回到起始点。
然而人们无数次的尝试解决却都没有成功。
直到1736年，欧拉解决了这个问题。
他用抽像分析法将这个问题化为世界上第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条边来代替，从而得到了一个“图”。
最终，欧拉成功证明了这个问题是无解的，并且推广了这个问题的意义，给出了对于一个给定的图可以某种方式走遍的判定法则。
这就是后来的欧拉通路、欧拉回路以及欧拉图问题。
于是，欧拉成为了图论学的创始人。
从那以后开始的几百年间，图论开始了飞速的发展。
虽然图论研究的是点和边之间所构成图的问题，但其应用领域还是十分广阔的。
图论的应用不仅仅局限于数学问题和计算机领域，它同时还涵盖了交通管理、通信领域、社会学等诸多其他研究领域。
而最短路径问题是图论应用中的基本问题。
最短路径顾名思义就是在所有的路径中找出一条距离最短的有效路径。
实际上，这里所指的“距离”不仅仅是指地理意义上的距离，还可以引申到时间、费用、等其他度量单位上面。
本文中，以重庆地铁为研究对象，利用图论知识解决在搭乘重庆地铁时的最短路径问题。
可以说，最短路径问题再交通网络结构的分析以及交通路线的选择中都有重要的应用价值。
此外，最短路径问题一直是计算机科学、地理信息学、交通管理学等学科中一个研究的热点问题。
图的着色是指对图的每个节点指定一种颜色，使得相邻的节点的颜色不相同。
最小生成树——Prim算法1、算法问题的提出首先介绍生成树的概念连通图G=(V,E)是无向带权图，若一个子图G’是一棵包含G的所有顶点的树，则该子图G’称为G的生成树。
生成树是连通图的极小连通子图。
所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。
生成树各边的权值总和称为生成树的权。
本次设计是求在图G中所有生成树中权值总和（费用/代价）最小的生成树，即最小生成树。
用两个例子进行实例演示。
2、Prim算法思想用哲学的观点来说，每个事物都有自己特有的性质，那么图的最小生成树也是不例外的。
按照生成树的定义，n 个顶点的连通网络的生成树有n 个顶点、n-1 条边。
（1）从树中某一个顶点V0开始，将V0到其他顶点的所有边当作候选边。
（2）重复以下步骤n-1次，使得其他n-1个顶点被并入到生成树中。
○1从候选边挑出权值最小的边输出，并将与该边另一端的相接的顶点V并入生成树中。
○2考察所有剩余顶点V i，如果(V,V i)的权值比lowcost[V i]小，则用（V,V i）的权值更新lowcost[V i]。
其中的vset[i]的值记录顶点V[i]顶点是否被选入最小生成树中，V[i]=0,表示为被选入，V[i]=1，表示已被选入。
用到辅助数组pre[]，记录当前所选入顶点的前驱结点，当并入前一个顶点时，剩下顶点到生成树的权值发生了改变时，就需要及时修改剩下顶点V[i]的前驱结点。
3、程序设计（1）所用数据结构，图的存储结构模块（nodetype.h）#define MAXSIZE 7#define INF 100typedef struct{int no;}VertexType; //顶点类型定义typedef struct{int edges[MAXSIZE][MAXSIZE]; //存入边的权值int n; //顶点数int e; //总的边数VertexType vex[MAXSIZE];}MGraph; //图的存储结构MGraph g;（2）主模块（main.cpp）#include#include"nodetype.h"#include"initiate.h"#include"prim.h"void prim(MGraph g,int v0,int &sum);int main(){int sum=0;int v0;initiate(g); //图的初始化printf("请输入起点编号：\n");scanf("%d",&v0);//输入起始节点prim(g,v0,sum); //调用prim算法，构成最小生成树printf("最小生成树的总代价为%d\n",sum);return 0;}（3）读取数据模块,图的初始化（initiate.h）void initiate(MGraph &g){int i,j,v0=0;printf("Please input the Sumnum of MGraph:\n");scanf("%d",&g.n);printf("依次输入各边权值（不相临接的边权值为100）!\n\n"); for(i=1;i<=g.n;i++){g.vex[i].no=i; //节点编号for(j=1;j<=g.n;j++){printf("边[%d][%d]的权值为：",i,j);//各边的权值scanf("%d",&g.edges[i][j]);printf("\n");}}}(4）运用贪心策略——Prim算法构造最小生成树（prim.h）void prim(MGraph g,int v0,int &sum){int lowcost[MAXSIZE],vset[MAXSIZE];int v,pre[MAXSIZE]; //pre[]存入前驱结点数组int i,j,k,min;v=v0; //初始起点for(i=1;i<=g.n;i++){lowcost[i]=g.edges[v0][i]; //lowcost[]的数组pre[i]=v0;vset[i]=0;}vset[v0]=1;sum=0;for(i=1;imin=INF;for(j=1;j<=g.n;j++){if(vset[j]==0&&lowcost[j]min=lowcost[j];k=j;}}vset[k]=1; //将此结点并入到所够造的生成树中v=k;if(min!=INF){printf("边的起点为：%d 终点为：%d 权值为%d\n",pre[v],v,min);sum+=min;}else{break;}for(j=1;j<=g.n;j++){//并入新结点后修改剩下的结点到生成树的权值if(vset[j]==0&&g.edges[v][j]lowcost[j]=g.edges[v][j];pre[j]=v; //并记其下全趋结点}}}}4、算法分析Prim算法的时间复杂度主要是在双重循环构造最小生成树的过程中，设图的顶点数为n，则双重循环的时间复杂度为O(n2)，在生成最小生成树的过程中，增加了两个数组，vset[]和lowcost[]数组，同时增加了一个前驱数组prey[]，用来记录所选顶点的全趋结点，故空间复杂度为O(3n)。
图论本科毕业论文近年来，随着社会的发展和科技的进步，图论在各个领域中得到了广泛应用，尤其是网络科学、计算机科学和数学领域。
图论的基础理论和应用研究，也受到越来越多的关注。
本文主要介绍了图论的基础理论和应用研究，以及本人在此领域中的研究工作。
一、图论的基础理论图论是一门基础数学学科，它主要研究图的结构、性质和算法等方面的问题。
在图论中，图是由节点和边组成的集合，它可以用来描述各种实际问题，例如社交网络、电子电路、物流运输等。
图可以分为有向图和无向图两种类型。
有向图是由有向边连接节点而成的图，可以描述各种节点之间的方向关系。
而无向图则是由无向边连接节点而成的图，不考虑节点之间的方向关系，可以表示各种关系网络。
图论中的一些基本概念包括节点、边、路径、回路和连通性等。
节点是图中的基本元素，边是节点之间的连接线，路径指的是由一系列连续的边连接的节点序列，回路是一个首尾相接的路径。
而连通性则是描述图中各个节点之间的相互可达性的层次结构。
图论的另外一个重要的概念是图的度数。
节点的度数指与此节点相邻的边的数目，而图的度数则是所有节点度数之和。
在研究图的性质和结构时，度数是一个非常重要的指标，它可以用来刻画图的稠密或稀疏程度。
二、图论的应用研究图论在实际中的应用非常广泛。
例如，图论可以用于描述社交网络中各个节点之间的关系网络。
在这个网络中，节点代表人或组织，边则代表人和组织之间的关系。
通过研究这个网络的结构和性质，可以分析社交网络中的信息传播和节点的影响力等问题。
图论也广泛应用于计算机科学领域中。
例如，在计算机网络中，图论可以用来描述网络拓扑结构，并通过研究图的各种性质和算法，来优化网络的性能和安全性。
图论还可以用于描述物流和运输网络中的各种问题。
例如，在交通运输中，可以通过赋予各个节点和边合适的权重来刻画交通拥堵程度，从而优化交通运输的效率。
三、本人在图论领域的研究工作在本人的毕业论文中，我主要研究了图论中的连通性问题。
最短路算法的比较与应用[摘要]本文较详尽地介绍了最短路算法相关的基本概念，给出了Dijkstra 算法、Floyd 算法、SPFA 算法等常用算法及其核心思想，并对各种最短算法做了多角度的比较，阐述了各种算法的应用范围，并对其在运输网络、舰船通道路线设计、工业生产中的应用做出了举例说明，侧重于模型的建立、思考和证明的过程，最后作出总结。
关键词：最短路算法 Dijkstra 算法 Floyd 算法 SPFA 算法1 引言最短路算法是图论中的核心问题之一，他是许多更深层次算法的基础，同时，该问题有着大量的生产实际的背景.很多问题从表面上看与最短问题没有什么关系，却也可以归结为最短路问题，本文通过收集整理关于最短路径的普遍算法，为研究最短路径问题在一些出行问题，工程问题，及实际生活问题中的应用，为企业和个人提供方便的选择方法。
2 最短路2.1 最短路的定义对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权)0(≥ij w 的有效算法是由荷兰著名计算机专家E.W.Dijkstra 在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G 中一特定点到其它各顶点的最短路。
后来海斯在Dijkstra 算法的基础之上提出了海斯算法.但这两种算法都不能解决含有负权的图的最短路问题.因此由Ford 提出了Ford 算法,它能有效地解决含有负权的最短路问题.但在现实生活中,我们所遇到的问题大都不含负权,所以我们在)0(≥ij w 的情况下选择Dijkstra 算法。
定义1 若图),(E V G G =中各边e 都赋有一个实数)(e W ,称为边e 的权,则称这种图为赋权图,记为),,(W E V G G =。
定义2 若图),(E V G G =是赋权图且)(,0)(G E e e W ∈≥,若u 是i v 到jv 的路)(u W 的权,则称)(u W 为u 的长,长最小的i V 到j V 的路)(u W 称为最短路.若要找出从i v 到n v 的通路u ,使全长最短,即()()min ij e uW u W e ∈=∑。
图论的应用摘 要图论从诞生至今已近300年，但很多问题一直没有很好地解决。
随着计算机科学的发展，图论又重新成为了人们研究讨论的热点，图形是一种描述和解决问题直观有效的手段，这里给出图论在现实生活中的一些应用。
关键词：图论；应用；最小生成树；最短行程1 引言图论起源于18世纪。
第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。
1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。
1857年，凯莱在计数烷22n n C H 的同分异构物时，也发现了“树”。
哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。
图论中所谓的“图”是指某类具体事物和这些事物之间的联系。
如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。
图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。
哥尼斯堡七桥问题（如图1）就是一个典型的例子。
在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。
当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。
欧拉为了解决这个问题，采用了建立数学模型的方法。
他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。
问题成为从任一点出发一笔画出七条线再回到起点。
欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。
图论及其应用论文姓名：xxx学号：xxx专业:xxx图论在高校互联校内网建设的应用摘要图论和我们的生活其实是息息相关的，我们在生活中处处可见图论的实际应用。
特别的，图论对我们通信专业以后的工作也有着极大的帮助.在以后的工作中也会时时用到图论的相关知识。
本论文的主旨是利用相关的图论知识来解决重庆几所高校建立互联校内网的问题。
主要是为了能使各重庆高校的学生能够免费共享高校的学习资源。
从而促进各高校学生的共同发展。
本文中，解决重庆几所高校建立互联校内网主要应用的是求图的最小生成树的方法。
而求图的最小生成树有两种算法，一种是Prim（普里姆）算法,另一种是Kruskal(克鲁斯卡尔）算法.本文通过将高校转换成连通图，再将连通图转换成邻接矩阵。
在C++上,通过输入结点和权值，用普里姆算法获得权值最小边来得到最小生成树,从而在保证各个地点之间能连通的情况下节省所需费用。
关键字：最小生成树、PRIM算法、邻接矩阵、高校互联校内网建设1.连通图(1）概述在图论中，连通图基于连通的概念。
在一个无向图 G 中，若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径），则称vi和vj是连通的。
如果 G 是有向图，那么连接vi和vj的路径中所有的边都必须同向.如果图中任意两点都是连通的,那么图被称作连通图。
图的连通性是图的基本性质。
（2）严格定义对一个图 G=(V,E) 中的两点 x 和 y ，若存在交替的顶点和边的序列Γ=（x=v0-e1—v1—e2—。
..-ek—（vk+1)=y) (在有向图中要求有向边vi−( vi+1)属于E )，则两点 x 和 y 是连通的。
Γ是一条x到y的连通路径，x和y分别是起点和终点。
当 x = y 时，Γ被称为回路.如果通路Γ 中的边两两不同，则Γ 是一条简单通路，否则为一条复杂通路.如果图 G 中每两点间皆连通，则 G 是连通图.(3）相关概念连通分量：无向图 G的一个极大连通子图称为 G的一个连通分量（或连通分支).连通图只有一个连通分量,即其自身；非连通的无向图有多个连通分量。
强连通图：有向图 G=（V，E）中,若对于V中任意两个不同的顶点 x和 y，都存在从x到 y以及从 y到 x的路径,则称 G是强连通图。
相应地有强连通分量的概念.强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连分量。
弱连通图：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图.如果一个有向图的基图是连通图，则有向图是弱连通图。
初级通路:通路中所有的顶点互不相同。
初级通路必为简单通路，但反之不真。
(4)性质一个无向图 G=（V，E）是连通的，那么边的数目大于等于顶点的数目减一:｜E｜>=｜V｜—1,而反之不成立.如果 G=（V,E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目:|E｜>=｜V｜，而反之不成立。
没有回路的无向图是连通的当且仅当它是树，即等价于:|E|=|V|-1.2. 最小生成树（1）树树包含n（n>=0）个节点。
当n=0时表示为空树。
其定义如下：T=（D,R)其中，D为树中节点的有限集合,关系R满足一下条件：①有且仅有一个节点k0属于D，它对于关系R来说没有前趋节点，结点k0称作树的根结点.②除根结点k0之外，D中的每个结点仅有一个前趋结点，但可以有过个后继结点.③D中可以有多个终端结点.即除根结点无父结点,其余各结点都有一个父结点和n（n>=0）个子结点.(2)邻接矩阵图的矩阵表示,本文中只用到了邻接矩阵，故在这只提出邻接矩阵的定义，及其图在邻接矩阵中的表示.设图 A = (V， E）是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A。
edge［n］[n],用来存放顶点的信息和边或弧的信息。
是表示顶点之间相邻关系的矩阵。
设G=(V，E)是一个图，其中V=｛v1,v2，…,vn}.G的邻接矩阵是一个具有下列性质的n阶方阵:①无向图的邻接矩阵是对称的；有向图的邻接矩阵可能是不对称的。
②无向图的邻接矩阵中第i行第j列表示i结点到j结点的度即权值，可以表示为某一具体应用的数据。
也表示i结点是否与j结点连通。
（3)最小生成树在一给定的无向图G=(V， E)中(u,v) 代表连接顶点u与顶点v的边（即),而 w （u，v)代表此边的权重，若存在T为E的子集（即)且为无循环图,使得的w（T)最小则此T为G的最小生成树。
3。
prim算法思想：首先，选择带最小的边,把它放进生成树里，相继添加带权最小的边，这些边与已在树立的顶点相关联,并且不与已在数理的边形成圈，当已经添加了n—1条边为止步骤：假设V是图中顶点的集合，E是图中边的集合，TE为最小生成树中的边的集合，则prim算法通过以下步骤可以得到最小生成树:（1)初始化：U=｛u 0｝，TE={f｝。
此步骤设立一个只有结点u 0的结点集U和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中，这个形态会不断的发生变化，直到得到最小生成树为止。
(2）在所有u∈U,v∈V－U的边（u,v)∈E中,找一条权最小的边（u0，v0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。
此步骤的功能是在边集E中找一条边，要求这条边满足以下条件：首先边的两个顶点要分别在顶点集合U和V－U中，其次边的权要最小.找到这条边以后，把这条边放到边集TE中，并把这条边上不在U 中的那个顶点加入到U中。
这一步骤在算法中应执行多次,每执行一次，集合TE和U 都将发生变化，分别增加一条边和一个顶点，因此,TE和U是两个动态的集合，这一点在理解算法时要密切注意。
（3）如果U=V，则算法结束；否则重复步骤2。
可以把本步骤看成循环终止条件。
我们可以算出当U=V时，步骤2共执行了n－1次（设n为图中顶点的数目），TE中也增加了n－1条边，这n－1条边就是需要求出的最小生成树的边。
4。
实际问题及其解决现有：重庆大学,西南大学，西南政法大学，重庆师范大学，重庆邮电大学5所高校,要求把他们的校内网进行互联，以组建一个更大的校园网络.在发费最少的情况下进行光缆的铺设。
根据实际测量地图的得到的各学校之间的直线距离图：由于每公里光缆造价相同,故可以用实际距离代替造价作为权重。
实际情况缩略图：设：重庆邮电大学V1重庆大学V2重庆师范大学V3西南大学V4西南政法大学V5 输入程序运行得到结果：解决问题得到结果：5。
总结通过对prim算法编写的Ｃ程序我们可以轻易地得到在发费最少的情况下进行光缆的铺设的路径。
这大大的节约了成本和时间，是对实际问题的一次生动尝试。
同时这个程序也可以进行相应的改善和推广，以利于我们的工作实践。
参考文献【1】《图论及其算法》，殷剑宏等,中国科学技术大学出版社.【2】《C语言程序设计》(第三版)，谭浩强，清华大学出版社。
【3】《数据结构》(C语言版），严蔚敏吴伟民,清华大学出版社。
程序＃include "stdio。
h"＃define maxnum 10#define maxvalue 88typedef struct //定义存放各节点间边的权值的二位数组为新的数据类型可称为图｛int v[maxvalue]［maxvalue]；｝ mgraph； //该数据类型用标识符mgraph表示mgraph input(int n) //数据输入函数用于输入各节点间边的权值{mgraph x; //定义x为mgraph类型while（n〈=0|｜n〉maxnum） //控制输入出错重新执行{printf（"输入有误,请重新输入：”)；scanf("%d”,&n);｝for（int i=1；i<=n;i++） //双层循环控制每个节点到其他各节点的权值｛for(int j=0;j〈=n;j++){int temp; //定义临时变量用于存放输入权值便于接下的过滤操作if（i==j） //各节点到自身的权重赋为0x。
v［i］［j]=0;elseif(i<j) //赋值其他各点到比其大的下标的节点{printf（"请输入节点%d到节点％d的权：",i,j)；scanf（"％d"，&temp）; //将输入临时存放在tempwhile（temp==0｜｜temp<—1） //过滤输入数据｛printf（"输入有误，请重新输入：\n")；printf(”请输入%d到％d的权:"，i,j）;scanf(”%d"，&temp）;}if（temp〉0) //将符合要求数据赋值给tempx.v［i][j]=temp;else //temp=-1时将权重赋值最大值88x.v[i］[j]=maxvalue；｝else //i〉j由于权重是对称的即呈上三角或下三角分布故只需将i，j对换即可x。
v[i][j］=x.v[j]［i］；｝printf（"\n");｝return x; //返回图x}void print(mgraph g，int n) //打印函数｛int i,j； //定义整型i，jprintf(” "）； //打印美观需要for（i=1；i<=n;i++）printf(”％2d ",i);printf（”\n"）;for(i=1;i〈=n;i++） //双层循环按矩阵方式打印输出各节点间权值｛printf（”%d ”，i）;for（j=1；j<=n；j++)printf("％2d ”，g.v［i］［j])；printf（"\n"）;}}void prim（mgraph g，int k，int n) //核心算法Prim算法实现函数{int i，j,min,p； //定义整型变量i，j用于循环 min和p分别用于临时存放最小权值及其下标struct //定义型类型数据closedge［］用于临时存放下标和最小边{int adjvex;int lowcost；}closedge[maxnum];for（i=1;i<=n;i++） //初始化辅助数组if(i!=k）{closedge[i]。
adjvex=k；closedge［i］.lowcost=g.v[k]［i];｝closedge［k].lowcost=0； //将节点加入生成树中for(i=1;i<n;i++） //循环比较最小权值且将最小权值的点加入生成树中并打印输出｛p=1; //初始化pmin=maxvalue； //初始化最小权值for(j=1;j<=n；j++) //循环n次比较最小权值if（closedge[j].lowcost！=0＆＆closedge[j］.lowcost<min） //当前节点不在已生成树中且权值最下{min=closedge［j］。
