图论及其应用论文

《图论及其应用论文》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图论及其应用论文姓名：xxx学号：xxx专业：xxx图论在高校互联校内网建设的应用摘要图论和我们的生活其实是息息相关的，我们在生活中处处可见图论的实际应用。特别的，图论对我们通信专业以后的工作也有着极大的帮助。在以后的工作中也会时时用到图论的相关知识。本论文的主旨是利用相关的图论知识来解决重庆几所高校建立互联校内网的问题。主要是为了能使各重庆高校的学生能够免费共享高校的学习资源。从而促进各高校学生的共同发展。本文中，解决重庆几所高校建立互联校内网主要应用的是求图的最小生成树的方法。而求图的最小生成树有两种算法，一种是Prim（普里姆）算法，另一种是Krusk

2、al（克鲁斯卡尔）算法。本文通过将高校转换成连通图，再将连通图转换成邻接矩阵。在C++上，通过输入结点和权值，用普里姆算法获得权值最小边来得到最小生成树，从而在保证各个地点之间能连通的情况下节省所需费用。关键字：最小生成树、PRIM算法、邻接矩阵、高校互联校内网建设1.连通图（1）概述在图论中，连通图基于连通的概念。在一个无向图G中，若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径)，则称vi和vj是连通的。如果G是有向图，那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。（

3、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

4、=(V,E)中，若对于V中任意两个不同的顶点x和y，都存在从x到y以及从y到x的路径，则称G是强连通图。相应地有强连通分量的概念。强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连分量。弱连通图：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。初级通路：通路中所有的顶点互不相同。初级通路必为简单通路，但反之不真。(4)性质一个无向图G=(V,E)是连通的，那么边的数目大于等于顶点的数目减一：

5、E

6、>=

7、V

8、-1，而反之不成立。如果G=(V,E)是有向图，那么它是强连通图的必要条件

9、是边的数目大于等于顶点的数目：

10、E

11、>=

12、V

13、，而反之不成立。没有回路的无向图是连通的当且仅当它是树，即等价于：

14、E

15、=

16、V

17、-1。2.最小生成树（1）树树包含n（n>=0）个节点。当n=0时表示为空树。其定义如下：T=(D,R)其中，D为树中节点的有限集合，关系R满足一下条件：①有且仅有一个节点k0属于D，它对于关系R来说没有前趋节点，结点k0称作树的根结点。②除根结点k0之外，D中的每个结点仅有一个前趋结点，但可以有过个后继结点。③D中可以有多个终端结点。即除根结点无父结点，其余各结点都有一个父结点和n（n>=0）个子结点。（2）邻接矩阵图的矩阵表示，本

18、文中只用到了邻接矩阵，故在这只提出邻接矩阵的定义，及其图在邻接矩阵中的表示。设图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)

19、中(u,v)代表连接顶点u与顶点v的边(即),而w(u,v)代表此边的权重,若存在T为E的子集（即)且为无循环图，使得的w(T)最小则此T为G的最小生成树。3.prim算法思想：首先，选择带最小的边，把它放进生成树里，相继添加带权最小的边，这些边与已在树立的顶点相关联，并且不与已在数理的边形成圈，当已经添加了n-1条边为止步骤：假设V是图中顶点的集合，E是图中边的集合，TE为最小生成树中的边的集合，则prim算法通过以下步骤可以得到最小生成树：（1）初始化：U={u0},TE={f}。此步骤设立一个只有结点u0的结点集U和一个空的边集TE作为最小生成树的初始

20、形态，在随后的算法执行中，这个形态会不断的发生变化，