离散数学实验3 平面图判定及对偶图的求解 C++

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

实验题目：平面图判定及对偶图的求解

实验时间: 2021.12.23

1. 了解平面图的定义及其判定算法；
2. 掌握平面图的对偶图的求解方法；
3. 掌握平面图与其对偶图之间的点、面和边的关系；

给定平面图此图的面矩阵, 即 M r = ( m i j ) r × m M r=left(m_{i j}right)_{r times m} Mr=(mij​)r×m​,
m i j = { 1 e j  是  R i  的边界  0 e j  不是  R i  的边界  m_{i j}=left{begin{array}{cc} 1 & e_{j} text { 是 } R_{i} text { 的边界 } \ 0 & e_{j} text { 不是 } R_{i} text { 的边界 } end{array}right. mij​={10​ej​ 是 Ri​ 的边界 ej​ 不是 Ri​ 的边界 ​

1. 输出此平面图的顶点数n、边数m和面数r。
2. 输出此平面图的对偶图的顶点数n*、边数m和面数r。
3. 输出此平面图的对偶图的关联矩阵或邻接矩阵。

给定面矩阵，求平面图的顶点数n、边数m和面数r，求此平面图的对偶图的顶点数n*、边数m和面数r，求此平面图的对偶图的关联矩阵或邻接矩阵。

预设输入边范围 : 0 < m < 999 0

预设输入面范围： 0 < r < 999 0

输入形式: 连通分支数，面矩阵 如：

4

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

输出：

示例：

请输入连通分支数目:
4
请输入面矩阵:
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0
1 1 1 1 0 1 1 1 1 1

此平面图顶点数n：12  边数m：10  面数r：3
此对偶图图顶点数n*：3  边数m*：10  面数r*：9
2 0 4 
0 0 3 
4 3 4 

面矩阵、相邻矩阵、欧拉定理

1. 连通分支数和面矩阵

2. 根据欧拉定理和对偶图的性质，求此平面图的顶点数n、边数m和面数r。求此平面图的对偶图的顶点数n*、边数m*和面数r*

3. 求出对偶图的邻接矩阵，注意自环的情况。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
int sq[1000][1000];
int sq2[1000][1000];
using namespace std;
int p,r,m;
int main(){
    cout<<"请输入连通分支数目:n";
    cin>>p;
    getchar();
    cout<<"请输入面矩阵:n";
    string str;
    getline(cin,str);
    while(str!=""){
        stringstream ss(str);
        r++;
        for(int j=1;!ss.eof();j++){
            ss>>sq[r][j];
            m=max(m,j);
        }
        getline(cin,str);
    }

    int n=p + 1 - r + m;

    cout<<"此平面图顶点数n："<
        for(int j=1;j<=r;j++){
            if(sq[j][i]==1){
                if(a==-1){
                    a=j;
                }else{
                    b=j;
                }
            }
        }
        if(b==-1) b=a;
        sq2[a][b]++;
        sq2[b][a]++;
        a=-1;
        b=-1;
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=r;j++){
            cout< 
调试分析 
调试过程中所遇到的问题及解决方法 
一切正常
 
算法的时空分析 
求此平面图和对偶图的顶点数n、边数m和面数r。
    
     
      
       
        O
       
       
        (
       
       
        1
       
       
        )
       
      
      
       O(1)
      
     
    O(1)
 
求对偶图的邻接矩阵。
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         2
        
       
       
        )
       
      
      
       O(n^2)
      
     
    O(n2)
 
五、实验结果 
 
 
 
六、实验总结 
心得体会：对平面图的定义及其判定算法有了更深的理解，掌握了平面图的对偶图的求解方法，掌握了平面图与其对偶图之间的点、面和边的关系。很好的锻炼了代码能力，吸收了许多教训，学到了编程中的许多知识，非常有用。