无向简单图与无向连通图自动识别系统

摘要： 近年来，图论越来越受到全世界数学界和其它科学界的广泛重视。图的理论及其在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中各方面的应用研究都迅速发展。无向图作为图论的重要组成部分，研究无向图的连通性问题具有很重要的意义。本文介绍了无向简单图与无向连通图自动识别系统的设计与实现过程。

Abstract： In recent years， more and more attention was paid to the graph theory in Mathematics and other scientific fields； there is a great development in graph theory and the applying research of graph theory in the physical， chemical， operations research， computer science， electronics， information theory， cybernetics， network theory， social science and economic management and so on. As an important part of graph theory， it is very important to do the research about the connectivity of undirected simple graph. This paper introduces the designing and applying process of automatic identification system of undirected simple graph and undirected connected graph.

关键词： 图论；无向简单图；无向连通图；自动识别系统

Key words： graph theory；undirected simple graph；undirected connected graph；automatic identification system

中图分类号：TP39 文献标识码：A 文章编号：1006—4311（2012）28—0198—02

1 选题背景

目前，图的理论及其在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中各方面的应用研究都得到“爆炸性发展”。图论越来越受到全世界数学界和其它科学界的广泛重视。各种国际学术交流活动十分活跃。在人们的社会实践中，图论已成为解决自然科学、工程技术、社会科学、生物技术以及经济、军事等领域中许多问题的有力工具之一，因此越来越受到数学家和实际工作者的喜爱。在现如今的实际应用中，利用图论中的最小生成树理论，较好地解决了通讯网络的最优化铺设问题，并对这一类问题的解决提供一种新的思路。许多离散的问题也都可以用图建立模型。所以，对本课题的研究有很重要的意义，为以后在实际生活应用提供便利。

2 研究内容

采用C/S 架构，基于Microsoft Visual C++ 6.0平台，SQL SERVER2008数据库技术设计一个自动识别无向简单图和无向连通图的系统，用户登录需要先进行注册，获取权限后才可以进入判定系统。登录后的用户可以查看和修改个人信息，只有管理员有权限查看和修改所有用户信息。

3 功能模块设计

本系统总共划分了四大模块：注册登录模块、数据输入模块、图像判别模块、结果输出模块。

系统模块图如图1所示：

4 数据库设计

4.1 数据库需求分析 考虑将来功能上的扩展，设计下面所示的数据项和数据结构。

①角色信息，包括的数据项：角色ID，角色名称。

②用户信息，包括的数据项：用户ID，用户名称，用户密码，性别，年龄，手机号，Email等。

③点的信息：包括的数据项：点的横坐标，点的纵坐标，点与其他点的关系。

4.2 数据库表设计 根据前面的需求分析，建立了一个名为：ZZQ 的数据库，其中有三个数据表分别为：Roles角色信息表，Users用户信息表，Points点的信息表。如表1、表2、表3所示。

5 系统实现

5.1 数据输入 数据输入模块是把用户输入到Excel中的数据提取出来并写入数据库。程序识别的Excel文件是“.csv”的，所以其它格式的数据无法导入，所以用户首先把数据写入到Excel中，然后需另存为“.csv”格式的文件。用户界面需要用户数据表名，此表名用来在数据库中存放数据。选中表名和数据库以后系统会自动绑定该表名和此数据。

首先输入表名，然后程序判断此名称是否存在，如果不存在，则新建表，并绑定此表和文件数据。首先使用Select语句在数据库中查找此表名是否存在，如果存在，则重新输入。否则使用Create语句新建用户数据的表，并且修改表的架构为dbo。其次对文件路径的判断。首先判断选中文件的格式是否正确，然后判断路径是否存在，再读取文件中的数据并存储在数据库中，此选中的存放数据的表是上述判断的表名。

5.2 数据导出 用户在数据输入后，可以选择将数据以Excel的形式导出，先选择数据所在的表名，文件保存位置用户可以自行选择。

数据导出模块是把数据库中的数据导出到Excel中。程序是按Excel的“.csv”格式文件保存数据的，所以当用户输入文件名之后，默认保存的格式是“.csv”的文件。首先需要用户选择一个表名，选择成功后输入文件名，默认把此表名中的数据保存在此文件中。

首先选择一个表名，然后对文件路径的判断。首先判断选中文件的格式是否正确，然后判断路径是否存在，再读取数据中的数据并存储在文件中。

5.3 图像判别 数据输入完成后，进行判定操作，用户可以选择进行无向简单图判定或者是无向连通图判定，以无向简单图为例，用户在自动识别系统中选中无向简单图后，根据提示选择数据所在的表，此时，判别模块已经跟数据连上，开始进行判定。

图像判定分为无向简单图和无向连通图两个模块。

5.3.1 无向简单图是调用广度优先搜索算法实现的。

算法识别步骤如下：

①根据用户选择的表名从数据库中获得数据。

②首先过滤数据中的自环，然后提取出数据中边的关系，填充存放表的矩阵。

③删除数据中度小于2的点，然后依次删除与度小于2的点相连的边即相应的点，并将另外与这些边相关的其它顶点的度减1，一直到图中结点的度均大于等于2。

④如果数据中存在自环则不是无向简单图，否则判断第三步中到最后是否还有未删除的点，如果有，则存在环，如果没有，则该图为无向简单图。

⑤如果第四步中判断出此图不是无向简单图，则执行广度优先搜索算法，找出所有的环，并存储在内存中。

5.3.2 无向连通图是调用深度优先搜索算法实现的。

算法识别步骤如下：

①根据用户选择的表名从数据库中获得数据。

②首先过滤数据中的自环，然后提取出数据中边的关系，填充存放表的矩阵。

③找出所有度为0的节点，并存储和标记。

④若图中存在度为0的节点，则必定不是无向连通图，否则执行深度优先搜索算法。

执行深度优先搜索算法后，找出所有的连通分支，并存储在内存中。

5.4 结果输出 当图像判定完成后，系统自动输出结果，系统将根据数据库中的数据，输出相应的图形，并且在弹出框里输出判定的结果。

结果输出模块是依赖于图像判定模块的结果。

对于无向简单图的判定结果，如果是无向简单图，则使用同一种颜色画出全部的点和相连的边。如果不是无向简单图，找出所有的环，分别使用不同的颜色标识出所有的环，并显示出来，其它满足简单图的使用默认黑色，并把所有环的结果以对话框显示出来。画每一个点，如果使用系统的函数SetPixel画出来的点几乎看不到，所以必须要对一个点进行放大，程序中默认是放大10倍。

对于无向连通图的判定结果，如果是无向连通图，则使用同一种颜色画出全部的点和相连的边。如果不是无向连通图，找出所有的连通分支，分别使用不同的颜色标识出所有的连通分支，并把所有连通分支的结果以对话框显示出来。

参考文献：

[1]Kosak C， Marks J， Shieber S， Automating the layout of network diagrams with specified visual organization. IEEE Transactions on System， Man and Cybernetics， 1994.24（3）：440～454

[2]黄竞伟，康立山，陈毓屏.一个新的无向图画图算法.软件学报，2000，11（1）：138～142.

[3]王桂平，王衍，任嘉辰.图论算法理论、实现及应用.北京：北京大学出版社，2011，1.

推荐访问:连通 识别系统 简单