图论及其应用论文.doc

图论及其应用论文姓名：xxx学号：xxx专业：xxx图论在高校互联校内网建设的应用摘要图论和我们的生活其实是息息相关的，我们在生活中处处可见图论的实际应用。特别的，图论对我们通信专业以后的工作也有着极大的帮助。在以后的工作中也会时时用到图论的相关知识。本论文的主旨是利用相关的图论知识来解决重庆几所高校建立互联校内网的问题。主要是为了能使各重庆高校的学生能够免费共享高校的学习资源。从而促进各高校学生的共同发展。本文中，解决重庆几所高校建立互联校内网主要应用的是求图的最小生成树的方法。而求图的最小生成树有两种算法，一种是Prim（普里姆）算法，另一种是Kruskal（克鲁斯卡尔）算法。本文通过将高校转换成连通图，再将连通图转换成邻接矩阵。在C+上，通过输入结点和权值，用普里姆算法获得权值最小边来得到最小生成树，从而在保证各个地点之间能连通的情况下节省所需费用。关键字：最小生成树、PRIM算法、邻接矩阵、高校互联校内网建设1. 连通图（1）