关联矩阵、邻接矩阵、生成树、环空间和破集空间的解
实验题目：关联矩阵、邻接矩阵、生成树、环空间和破集空间的解
实验目的:
1.掌握无向连通图生成树的求解方法；
2.掌握基本回路系统和回路空间的求解方法；
3.掌握基本割集系统和破集空间的求解方法；
4.了解生成树、环空间和破集空间的实际应用。
实验要求:
1.给定无向简单连通图的邻接矩阵(例如：)。
1.输出该图的相关矩阵m。
2.求这个图的所有生成树的数目。
3.输出任意生成树的相邻矩阵(默认行I对应顶点vi)和相关矩阵(默认行I对应顶点vi，列J对应边ej)。
4.找到与此生成树对应的基本环路系统(输出形式：{e1e4e3，e2e5e3 })。
5.找到对应于此生成树的循环空间(输出形式，如{，e1e4e3，e2e5e3，E1 E4 e 2 })。
6.找到与此生成树对应的基本割集系统(输出形式为：{{e1，e4}，{e2，e5}，{e3，e4，e5}})。
7.找到与此生成树对应的破集空间(输出形式为：{、{E1、E4}、{E2、E5}、{E3、E4、E5}、{E1、E2、E4、E5}、{E1、E3、E5}、{E2、E3、E4}、{E1
*说明：学生设计的程序不仅要针对给定的相邻矩阵，还要针对教师测试数据集，才能得到正确的结果。
实验内容和实验步骤：(由学生填写)
输入：第一行是整数n，表示有n个订单。
接下来，每行n个整数的n行是邻接矩阵。
输出：输出由图的每条边连接的两个点。
在图中输出相关矩阵。
输出生成树的数量
输出生成树的相邻矩阵。
输出生成树的关联矩阵。
生成树的基本回路系统
生成树的循环空间
生成树的基本割集系统
生成树的破集空间
1.求给定邻接矩阵的关联矩阵，遍历邻接矩阵中的所有点，如果a[i][j]==1，则申请一个边连接I，j，并加入到关联矩阵中，在边[m] [1]和边[m] [2]中记录mth边连接的两点，为以后的使用做铺垫。trans()函数在代码中实现。
2.求生成树的个数，参考网络上的基尔霍夫矩阵，A-B=C，A代表度方程，B代表邻接矩阵，C代表基尔霍夫矩阵。树定理是去掉基尔霍夫矩阵的一行一列得到的行列式就是生成树的个数。countt()函数在代码中实现。
3.找到最小生成树。以Kruskar并集的方式，先将每个点fa赋给自己，然后遍历每条边。如果两个连接点fa不同，这意味着它们不在同一个块上，可以连接。如果两个点fa相同，说明这两个点在同一个树上，如果我们继续连接边，树的结构就会被破坏。在确定连通边的过程中，可以同时计算生成树的邻接矩阵，并为每条边记录SCEDGE [M] [1]和SCEDGE [M] [2]，其中M为生成树的边。Sctree()函数是用代码实现的。
4.找到基本的循环系统。对于不在生成树中的边，先把边加入到一个基本循环中，然后对于边连接的X和Y两个点，利用之前准备的边数组就可以很容易的得到。然后，树中的dfs寻找从X到Y的路径，该路径存在并且是唯一的。对每个字符串重复上述操作。basecircle()函数在代码中实现。
5.找到循环空间。循环空间由基本循环及其循环操作组成。
在前一步中，我们已经计算出了基本回路系统并获得了矩阵。第一行表示第一个基本循环由前三个或四个边组成。那么两条边的环运算实际上可以看作是判断同一条边是否重复奇数次，如果是奇数次，则可以保留。所以val数组用来记录累加值。很难选择一些边来列出所有的情况。很容易知道L边各有选择或不选择两种情况，所以有L次和sx次两种情况。从0到sx-1的每一个数字都可以恰好代表一个选择状态，其二进制的每一位都是0或1，正好可以代表对应的基本电路是否被选择。所以你可以得到所有的可能性。
6.找到基本的割集系统。利用并集的思想，对于树中的一条边I，除了I的边连接之外，树中的两点被并集合并。最后，树将被分成两部分。然后，对于字符串，看两个连接点X和Y是否在同一个块上，即它们的fa是否相等。如果没有，可以将其添加到基本切割集中。对树的每条边重复操作，最后生成基本割集系统。
7.破碎的集合空间。用基本割集做环化操作，从4到5的过程与上述过程类似。
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/149512.html