图论及其应用
论文
姓名：学号：专业：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条边就是需要求出的最小生成树的边。