知行社区

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 1304|回复: 0
收起左侧

图论实验

[复制链接]
回帖奖励 10 金币 回复本帖可获得 1 金币奖励! 每人限 1 次(中奖概率 70%)
起名字最烦了 发表于 2011-11-15 00:42 | 显示全部楼层 |阅读模式
  1. //输入一个图的邻接矩阵,自动算出每个点的度数,判断它是否满足握手定理,是否可以构成
  2. //欧拉图,是否满足哈密尔顿图的充分条件。
  3. #include<cmath>
  4. #include<iostream>
  5. using namespace std;

  6. int main(){
  7. loop:cout<<"此程序适用于无向图!"<<endl<<endl;
  8.     int row;
  9.         cout<<"请输入该图的点数:"<<endl;
  10.         cin>>row;
  11.         int AdjMat[row][row];//定义一个邻接矩阵,行列从键盘获得
  12.         cout<<"请输入矩阵"<<endl;
  13.         for(int i=0;i<row;i++)
  14.                 for(int j=0;j<row;j++)
  15.                         cin>>AdjMat[i][j];

  16.         int tmp=0;
  17.         for(int i=0;i<row;i++)
  18.                 for(int j=0;j<row;j++){
  19.                     if(AdjMat[i][j]!=AdjMat[j][i]||AdjMat[i][i]==1)
  20.                     tmp++;
  21.                         }
  22.          if(tmp>0){
  23.          cout<<"ERROR!"<<endl<<"此程序应用于无向图!"<<endl;
  24.          goto loop;
  25.          }
  26.                  
  27.      
  28.      
  29.      int deg[row];//定义邻接矩阵的度数
  30.      int i=0;
  31.      while(i<row){
  32.                    deg[i]=0;
  33.                    for(int j=0;j<row;j++){
  34.                            if(AdjMat[i][j]==1)
  35.                            deg[i]++;
  36.                            }
  37.                    i++;
  38.                    }
  39.      
  40.      
  41.      
  42.      
  43.      int k=1;
  44.    
  45.      cout<<endl<<"点\t度数 "<<endl;//打印度数
  46.       for(int i=0;i<row;i++)
  47.       cout<<k++<<'\t'<<deg[i]<<endl;
  48.       
  49.       //求总度数
  50.       int sumDeg=0;
  51.       for(int i=0;i<row;i++)
  52.       sumDeg+=deg[i];
  53.       cout<<endl<<"该图各点的总度数为:"<<sumDeg<<endl;
  54.       
  55.       
  56.       
  57.       //判断是否满足握手定理
  58.       int side=0;//定义图的边数,遍历数组求边数
  59.       for(int i=0;i<row;i++)
  60.       for(int j=0;j<row;j++){
  61.               if(AdjMat[i][j]==1)
  62.               side++;
  63.               }
  64.       side=side/2;  
  65.       cout<<endl<<"该图的边数为:"<<side<<endl;
  66.       if(sumDeg==2*side)
  67.       cout<<endl<<"该图满足握手定理"<<endl;
  68.       else
  69.       cout<<endl<<"该图不满足握手定理"<<endl;
  70.       
  71.       
  72.       
  73.       
  74.       //判断是否构成欧拉图
  75.        int tmp1=0;
  76.        for(int i=0;i<row;i++){
  77.                if(deg[i]%2==0)
  78.                tmp1++;
  79.                }
  80.        if(tmp1==row)
  81.        cout<<endl<<"该图构成欧拉图"<<endl;
  82.        else
  83.        cout<<endl<<"该图不构成欧拉图"<<endl;
  84.       
  85.       
  86.       
  87.        //判断是否满足哈密尔顿图的充分条件
  88.        int tmp2;
  89.        for(int i=0;i<row;i++){
  90.                if(deg[i]>deg[i++]){
  91.                                    tmp2=deg[i];
  92.                                    deg[i]=deg[i++];
  93.                                    deg[i++]=tmp2;
  94.                                    }
  95.                }
  96.        cout<<endl<<"度数最小的两点的度数和为:"<<(deg[0]+deg[1])<<endl;
  97.        cout<<endl<<"该图共有 "<<row<<" 个点"<<endl;
  98.        if((deg[0]+deg[1])>=row)
  99.        cout<<endl<<(deg[0]+deg[1])<<">="<<row<<"满足哈密尔顿图的充分条件" <<endl;
  100.        else
  101.        cout<<endl<<(deg[0]+deg[1])<<"<"<<row<<"不满足哈密尔顿图的充分条件" <<endl;
  102.        cout<<endl;
  103.    
  104.                system("pause");
  105.             return 0;
  106. }
复制代码

QQ|小黑屋|手机版|知行技术社区 ( 湘ICP备11020288号-1 )

GMT+8, 2020-9-30 05:09 , Processed in 0.033737 second(s), 10 queries , Redis On.

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表