无向图中查找线性无关环的算法研究开题报告

1. 研究目的与意义

现实生活中，在管道方面，计算各管道的实际压力和流量是经常要做的事情。实际的应用中，由于管道的组合各种各样，即可以把管道组合看成一个复杂的无向图，要列出的解答式的个数，与线性无关环的个数有关。线性无关环的概念:在无向图中，若存在两个环，组成这两个环的边，其中一个环的边有不属于另一个环的边，则称这两个环互为线性无关环。

这就给课题求图的线性无关环的个数有了实际生活背景。

2. 研究内容和预期目标

内容：设计几种从无向图中查找线性无关环的算法,研究比较各算法的优劣。

1．设计几种算法并写成适当的函数形式

2．编写研究程序,使其能方便地输入各种无向图,调用自己设计的算法函数,记录求解所花费的时间,输出求解的结果。

3. 研究的方法与步骤

算法设计步骤：

1.先查阅相关资料：图算法的理论知识、数据结构的理论知识、算法设计分析等

2.任选一种语言，实现图的数据结构，把图由平面转化成计算机内的元素可以用计算机显示出图，邻接表或邻接矩阵；

4. 参考文献

[1]michaelt.goodrich.算法分析与设计,人民邮电出版社

[2]严蔚敏.数据结构及应用算法教程，清华大学出版社

[3]microsoftdevelopernetwork(msdn)

5. 计划与进度安排

(1)2022年12月8日2022年3月19日

接受毕业设计任务，查阅资料并完成开题报告；

(2)2022年3月20日2022年4月11日