图论实验

1. //输入一个图的邻接矩阵，自动算出每个点的度数，判断它是否满足握手定理，是否可以构成
   
2. //欧拉图，是否满足哈密尔顿图的充分条件。
   
3. #include<cmath>
   
4. #include<iostream>
   
5. using namespace std;
   
6. 
   
7. int main(){
   
8. loop:cout<<"此程序适用于无向图！"<<endl<<endl;
   
9.     int row;
   
10.         cout<<"请输入该图的点数："<<endl;
    
11.         cin>>row;
    
12.         int AdjMat[row][row];//定义一个邻接矩阵，行列从键盘获得
    
13.         cout<<"请输入矩阵"<<endl;
    
14.         for(int i=0;i<row;i++)
    
15.                 for(int j=0;j<row;j++)
    
16.                         cin>>AdjMat[i][j];
    
17. 
    
18.         int tmp=0;
    
19.         for(int i=0;i<row;i++)
    
20.                 for(int j=0;j<row;j++){
    
21.                     if(AdjMat[i][j]!=AdjMat[j][i]||AdjMat[i][i]==1)
    
22.                     tmp++;
    
23.                         }
    
24.          if(tmp>0){
    
25.          cout<<"ERROR!"<<endl<<"此程序应用于无向图！"<<endl;
    
26.          goto loop;
    
27.          }
    
28.                  
    
29.      
    
30.      
    
31.      int deg[row];//定义邻接矩阵的度数
    
32.      int i=0;
    
33.      while(i<row){
    
34.                    deg[i]=0;
    
35.                    for(int j=0;j<row;j++){
    
36.                            if(AdjMat[i][j]==1)
    
37.                            deg[i]++;
    
38.                            }
    
39.                    i++;
    
40.                    }
    
41.      
    
42.      
    
43.      
    
44.      
    
45.      int k=1;
    
46.    
    
47.      cout<<endl<<"点\t度数 "<<endl;//打印度数
    
48.       for(int i=0;i<row;i++)
    
49.       cout<<k++<<'\t'<<deg[i]<<endl;
    
50.       
    
51.       //求总度数
    
52.       int sumDeg=0;
    
53.       for(int i=0;i<row;i++)
    
54.       sumDeg+=deg[i];
    
55.       cout<<endl<<"该图各点的总度数为："<<sumDeg<<endl;
    
56.       
    
57.       
    
58.       
    
59.       //判断是否满足握手定理
    
60.       int side=0;//定义图的边数，遍历数组求边数
    
61.       for(int i=0;i<row;i++)
    
62.       for(int j=0;j<row;j++){
    
63.               if(AdjMat[i][j]==1)
    
64.               side++;
    
65.               }
    
66.       side=side/2;  
    
67.       cout<<endl<<"该图的边数为："<<side<<endl;
    
68.       if(sumDeg==2*side)
    
69.       cout<<endl<<"该图满足握手定理"<<endl;
    
70.       else
    
71.       cout<<endl<<"该图不满足握手定理"<<endl;
    
72.       
    
73.       
    
74.       
    
75.       
    
76.       //判断是否构成欧拉图
    
77.        int tmp1=0;
    
78.        for(int i=0;i<row;i++){
    
79.                if(deg[i]%2==0)
    
80.                tmp1++;
    
81.                }
    
82.        if(tmp1==row)
    
83.        cout<<endl<<"该图构成欧拉图"<<endl;
    
84.        else
    
85.        cout<<endl<<"该图不构成欧拉图"<<endl;
    
86.       
    
87.       
    
88.       
    
89.        //判断是否满足哈密尔顿图的充分条件
    
90.        int tmp2;
    
91.        for(int i=0;i<row;i++){
    
92.                if(deg[i]>deg[i++]){
    
93.                                    tmp2=deg[i];
    
94.                                    deg[i]=deg[i++];
    
95.                                    deg[i++]=tmp2;
    
96.                                    }
    
97.                }
    
98.        cout<<endl<<"度数最小的两点的度数和为："<<(deg[0]+deg[1])<<endl;
    
99.        cout<<endl<<"该图共有 "<<row<<" 个点"<<endl;
    
100.        if((deg[0]+deg[1])>=row)
     
101.        cout<<endl<<(deg[0]+deg[1])<<">="<<row<<"满足哈密尔顿图的充分条件" <<endl;
     
102.        else
     
103.        cout<<endl<<(deg[0]+deg[1])<<"<"<<row<<"不满足哈密尔顿图的充分条件" <<endl;
     
104.        cout<<endl;
     
105.    
     
106.                system("pause");
     
107.             return 0;
     
108. }
     

复制代码