离散数学实验2 关联矩阵、相邻矩阵、生成树、环路空间、断集空间的求解 C++

• 离散数学实验报告2
• • 一、实验题目
  • 二、实验目的
  • 三、实验要求
  • 四、实验步骤和内容
  • • 需求分析：
    • • 输入形式与输入范围
    • 概要设计：
    • • 使用的数据结构与算法：
      • 程序流程：
    • 详细代码
    • 调试分析
    • • 调试过程中所遇到的问题及解决方法
      • 算法的时空分析
  • 五、实验结果
  • 六、实验总结

实验题目：关联矩阵、相邻矩阵、生成树、环路空间、断集空间的求解

实验时间: 2021.12.16

1. 掌握无向连通图生成树的求解方法；

2. 掌握基本回路系统和环路空间的求解方法；

3. 掌握基本割集系统和断集空间的求解方法；

4. 了解生成树、环路空间和断集空间的实际应用。

1. 给定无向简单连通图的相邻矩阵 例如:[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MPyNdYqm-1654332805884)(/Users/a26012/Desktop/截屏2021-12-23 15.02.35.png)]。
2. 输出此图的关联矩阵M。
3. 求此图所有生成树个数。
4. 输出其中任意一颗生成树的相邻矩阵（默认第i行对应顶点vi）和关联矩阵（默认第i行对应顶点vi，第j列对应边ej）。
5. 求此生成树对应的基本回路系统（输出形式如：{e1e4e3,e2e5e3}）。
6. 求此生成树对应的环路空间（输出形式如：{Φ,e1e4e3,e2e5e3,e1e4e5e2})。
7. 求此生成树对应的基本割集系统（输出形式如：{{e1,e4},{e2,e5},{e3,e4,e5}})。
8. 求此生成树对应的断集空间（输出形式如：{Φ, {e1,e4}, {e2,e5}, {e3,e4,e5}, {e1,e2,e4,e5}, {e1,e3,e5}, {e2,e3,e4}, {e1,e2,e3}})。

给定相邻矩阵，求关联矩阵，生成树个数，输出其中任意一颗生成树的相邻矩阵和关联矩阵。

求此生成树对应的基本回路系统，环路空间

求此生成树对应的基本割集系统，断集空间

预设输入点范围 : 0 < n < 999 0

邻接矩阵的边数： 0 < m < 99 9 2 0

输入形式: 相邻矩阵 如：

0 1 1 0 1
1 0 1 0 1
1 1 0 1 0
0 0 1 0 1
1 1 0 1 0

输出：

示例：

0 1 1 0 1
1 0 1 0 1
1 1 0 1 0
0 0 1 0 1
1 1 0 1 0

  e1 e2 e3 e4 e5 e6 e7 
v1 1  1  1  0  0  0  0  
v2 1  0  0  1  1  0  0  
v3 0  1  0  1  0  1  0  
v4 0  0  0  0  0  1  1  
v5 0  0  1  0  1  0  1  

生成树的个数为：24

它的一棵树为：
   V1 V2 V3 V4 V5 
V1  0  1  1  0  1 
V2  1  0  0  0  0 
V3  1  0  0  1  0 
V4  0  0  1  0  0 
V5  1  0  0  0  0 

  e1 e2 e3 e4 
v1 1  1  1  0  
v2 1  0  0  0  
v3 0  1  0  1  
v4 0  0  0  1  
v5 0  0  1  0  

基本回路系统:{e4e2e1, e5e3e1, e7e3e2e6, }
环路空间:{ Φ,e1e2e4,e1e3e5,e2e3e6e7,e2e3e4e5,e1e3e4e6e7,e1e2e5e6e7,e4e5e6e7,}

基本割集系统:{e4e5e1,e4e5e7e2,e4e5e7e3,e4e5e7e6,}
断集空间{ Φ,e1e4e5,e2e4e5e7,e3e4e5e7,e4e5e6e7,e1e2e7,e1e3e7,e1e6e7,e2e3,e2e6,e3e6,e1e2e3e4e5,e1e2e4e5e6,e1e3e4e5e6,e2e3e4e5e6e7,e1e2e3e6e7,}

关联矩阵、相邻矩阵、广度优先遍历、深度优先遍历、矩阵树定理(Matrix-Tree 定理)求生成树个数、分治思想

1. 读入相邻矩阵
2. 根据相邻矩阵，求出邻接矩阵sq2，基尔霍夫矩阵K。
3. 输出邻接矩阵
4. 根据基尔霍夫矩阵和矩阵树定理求出生成树个数gauss( )。
5. printTree( )函数中用广度优先遍历求出生成树，xl为树的相邻矩阵 ，gl为树的邻接矩阵
6. 求基本回路系统和环路空间printSystem()。求基本回路系统方法：枚举每一条弦，如果把它加到树中，就会有且只有一条回路，该回路就是一条基本回路。求环路空间方法，深度优先搜索，枚举所有情况，进行对称差运算。
7. 求基本割集系统，断集空间printSystem2()。求基本割集系统：枚举每一条树枝，找到该树枝对应的边割集，该割集就是一个基本割集。求断集空间方法，同上，深度优先搜索，枚举所有情况，进行对称差运算。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int sq[1000][1000];    //相邻矩阵
int sq2[1000][10000],edx=0,eedx=0;   //邻接矩阵
int edge[1000][1000];    //边编号
int c[1000][1000];
int xl[1000][1000];    //树的相邻矩阵
int gl[1000][1000];   //树的邻接矩阵
bool st[1000];     //是否遍历到
int wsz[1000];  //方便计算对称差
int K[1000][1000];  //生成树个数
vector> baseC;   //基本回路系统
vector> baseG;   //基本割集系统
int sz=0;
const int MOD = 0x3f3f3f3f;
int gauss(int n) {//求矩阵K的n-1阶顺序主子式
    int res = 1;
    for (int i = 1; i <= n - 1; i++) {//枚举主对角线上第i个元素
        for (int j = i + 1; j <= n - 1; j++) {//枚举剩下的行
            while (K[j][i]) {//辗转相除
                int t = K[i][i] / K[j][i];
                for (int k = i; k <= n - 1; k++)//转为倒三角
                    K[i][k] = (K[i][k] - t * K[j][k] + MOD) % MOD;
                swap(K[i], K[j]);//交换i、j两行
                res = -res;//取负
            }
        }
        res = (res * K[i][i]) % MOD;
    }
    return (res + MOD) % MOD;
}


void print_sq(){
    cout<<"  ";
    for(int i=1;i<=edx;i++){
        cout<<"e"<
        cout<<"v"<
            if(sq2[i][j]) cout<<1;
            else cout<<0;
            cout<<"  ";
        }
        cout<
    bool st[1000];

    memset(xl,0,sizeof xl);
    memset(st,0,sizeof st);
    memset(gl,0,sizeof gl);
    queue Q;
    Q.push(1);
    st[1]= true;
    while(!Q.empty()){
        int nw=Q.front();
        Q.pop();
        for(int i=1;i<=sz;i++){
            if(!st[i]&&sq[nw][i]){
                xl[nw][i]=xl[i][nw]=1;
                Q.push(i);
                st[i]= true;
            }
        }
    }

    cout<<"n它的一棵树为：n";
    printf("   ");
    for(int i=1;i<=sz;i++){
        printf("V%d ",i);
    }
    cout<
        printf("V%d ",i);
        for(int j=1;j<=sz;j++){
            printf(" %d ",xl[i][j]);
        }
        cout<
        for(int j=i+1;j<=sz;j++){
            if(xl[i][j]){
                ++edx;
                gl[i][edx]=gl[j][edx]=1;
            }
        }
    }
    cout<<"  ";
    for(int i=1;i<=edx;i++){
        cout<<"e"<
        cout<<"v"<
            if(gl[i][j]) cout<<1;
            else cout<<0;
            cout<<"  ";
        }
        cout<
    queue Q;
    vector tmp;
    bool st[1000];
    int fa[1000];
    memset(fa,0,sizeof fa);
    memset(st,0,sizeof st);

    Q.push(x);
    st[x]= true;
    fa[x]=-1;
    tmp.push_back(edge[x][y]);
    while(!Q.empty()){
        int nw=Q.front();
        Q.pop();
        for(int i=1;i<=sz;i++){
            if(!st[i]&&xl[nw][i]){
                xl[nw][i]=xl[i][nw]=1;
                Q.push(i);
                fa[i]=nw;
                st[i]= true;
            }
        }
        if(st[y]) break;
    }

    int nw=y;
    while(nw!=x){
        tmp.push_back(edge[nw][fa[nw]]);
        cout<<"e"<      //枚举对称差
    if(nub==0){
        for(int i=1;i<=eedx;i++){
            if(wsz[i]%2)
                cout<<"e"<
        for(int j=0;j< baseC[idx].size() ;j++)  wsz[ baseC[idx][j] ]++;
        dfs(nub-1,idx+1,1);    //选第idx个基本回路
        for(int j=0;j
        for(int j=0;j
    int base=0;

    cout<<"n基本回路系统:{";
    for(int i=1;i<=sz;i++){
        for(int j=i+1;j<=sz;j++){
            if(sq[i][j]&&!xl[i][j]){
                cout<<"e"<
        dfs(i,0,1);
    }
    cout<<"}n";
}
void gogo(int x){
    if(st[x]) return;
    st[x]= true;
    for(int i=1;i<=sz;i++){
        if(sq[x][i]) gogo(i);
    }
}
vector tmp;
bool wzy(int n){
    if(n==0){
        for(int i=0;i<=sz;i++) st[i]=0;
        gogo(1);
        for(int i=1;i<=sz;i++)
            if(!st[i]){
                baseG.push_back(tmp);
                return true;
            }
        return false;
    }
    for(int i=1;i<=sz;i++){
        for(int j=i+1;j<=sz;j++){
            if(sq[i][j]&&!xl[i][j]){
                sq[i][j]=sq[j][i]=0;
                tmp.push_back(edge[i][j]);
                bool rt=wzy(n-1);
                tmp.pop_back();
                sq[i][j]=sq[j][i]=1;
                return rt;
            }
        }
    }
}
void printSystem2(){
    int base=0;
    cout<<"n基本割集系统:{";
    for(int i=1;i<=sz;i++){
        for(int j=i+1;j<=sz;j++){
            if(xl[i][j]){
                sq[j][i]=sq[i][j]=0;
                tmp.clear();
                for(int k=1;;k++){
                    if(wzy(k)){
                        break;
                    }
                }
                baseG[baseG.size()-1].push_back(edge[i][j]);
                sq[j][i]=sq[i][j]=1;
            }
        }
    }
    for(int i=0;i
        for(int j=0;j
            cout<<"e"<
        dfs(i,0,2);
    }
    cout<<"}n";
}
int main() {

    string str;
    getline(cin,str);
    while(str!=""){
        stringstream ss(str);
        sz++;
        for(int j=1;!ss.eof();j++){
            ss>>sq[sz][j];
        }
        getline(cin,str);
    }
    for(int i=1;i<=sz;i++){
        for(int j=i+1;j<=sz;j++){
            if(sq[i][j]){
                ++edx;
                ++eedx;
                edge[i][j]=edge[j][i]=edx;
                sq2[i][edx]=sq2[j][edx]=1;
                K[i][i]++;
                K[j][j]++;
                K[i][j]--;
                K[j][i]--;
            }
        }
    }
    print_sq();
    cout< 
调试分析 
调试过程中所遇到的问题及解决方法 
一切正常
 
算法的时空分析 
求邻接矩阵，基尔霍夫矩阵，求生成树
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         2
        
       
       
        )
       
      
      
       O(n^2)
      
     
    O(n2)
 
Matrix-Tree 定理(求矩阵行列式)
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         4
        
       
       
        )
       
      
      
       O(n^4)
      
     
    O(n4)
 
基本回路系统
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         3
        
       
       
        )
       
      
      
       O(n^3)
      
     
    O(n3)
 
基本割集系统
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         4
        
       
       
        )
       
      
      
       O(n^4)
      
     
    O(n4)
 
求断集空间，环路空间
    
     
      
       
        O
       
       
        (
       
       
        
         2
        
        
         n
        
       
       
        )
       
      
      
       O(2^n)
      
     
    O(2n)
 
五、实验结果 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Q7ioy7pe-1654332805884)(/Users/a26012/Desktop/截屏2021-12-23 15.34.55.png)]
 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-X0JRu0BA-1654332805885)(/Users/a26012/Desktop/截屏2021-12-23 15.35.15.png)]
 
六、实验总结 
心得体会：
 
对无向连通图生成树的求解方法，基本回路系统和环路空间的求解方法，基本割集系统和断集空间的求解方法有了更深的理解，了解生成树、环路空间和断集空间的实际应用。很好的锻炼了代码能力，吸收了许多教训，学到了编程中的许多知识，非常有用。
可能是因为这个实验比较难，有一些同学借鉴了我的代码。