離散數(shù)學(xué)實(shí)驗(yàn)四

PAGE實(shí)驗(yàn)報(bào)告（2014/2015學(xué)年第一學(xué)期）課程名稱離散數(shù)學(xué)實(shí)驗(yàn)名稱圖的隨機(jī)生成及歐拉（回）路的確定實(shí)驗(yàn)時(shí)間2014年12月12日指導(dǎo)單位南京郵電大學(xué)指導(dǎo)教師羅衛(wèi)蘭學(xué)生姓名沈一州班級(jí)學(xué)號(hào)B12040920學(xué)院(系)計(jì)算機(jī)軟件學(xué)院專(zhuān)業(yè)NIIT（軟嵌）5-實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱圖的隨機(jī)生成及歐拉（回）路的確定指導(dǎo)教師羅衛(wèi)蘭實(shí)驗(yàn)類(lèi)型驗(yàn)證型實(shí)驗(yàn)學(xué)時(shí)4實(shí)驗(yàn)時(shí)間12.12實(shí)驗(yàn)?zāi)康暮鸵髢?nèi)容：編程隨機(jī)生成n個(gè)結(jié)點(diǎn)的無(wú)向圖并能進(jìn)行（半）歐拉圖的判定，若是則給出歐拉（回）路。要求：對(duì)給定n個(gè)結(jié)點(diǎn)，隨機(jī)生成鄰接矩陣以確定某無(wú)向簡(jiǎn)單圖并進(jìn)行歐拉圖和半歐拉圖的判定，若符合則給出至少一條歐拉回路或歐拉路。實(shí)驗(yàn)環(huán)境(實(shí)驗(yàn)設(shè)備)硬件：CPU：3.0Ghz內(nèi)存：1.00GB軟件：操作系統(tǒng)：WindowsXPSP3編程軟件：VisualC++6.0實(shí)驗(yàn)原理及內(nèi)容總體思想：這次題目要求是根據(jù)隨機(jī)生成的圖求歐拉（回）路，先要隨機(jī)生成一個(gè)鄰接矩陣，然后判定是否是歐拉回路只要根據(jù)奇數(shù)度結(jié)點(diǎn)的個(gè)數(shù)。再用一個(gè)遞歸函數(shù)找出歐拉路。核心代碼：1、根據(jù)結(jié)點(diǎn)數(shù)生成鄰接矩陣： for(i=0;i<n;i++) for(j=0;j<n;j++) { if(i==j)//同一個(gè)結(jié)點(diǎn)間沒(méi)有邊 a[i][j]=0; elseif(i>j)//邊沒(méi)有方向性 a[i][j]=a[j][i]; else{//隨機(jī)賦值，0代表沒(méi)有邊，1代表有邊 a[i][j]=rand()%2; } } cout<<"";//輸出該鄰接矩陣 for(i=0;i<n;i++){ cout<<""<<i+1; } cout<<endl; for(i=0;i<n;i++){ cout<<i+1; for(j=0;j<n;j++){ cout<<""<<a[i][j]; } cout<<endl; }2、根據(jù)奇數(shù)度結(jié)點(diǎn)數(shù)判定是否含有歐拉(回)路： odd=0; for(i=0;i<n;i++){ count=0; for(j=0;j<n;j++){ count+=a[i][j];//統(tǒng)計(jì)每個(gè)結(jié)點(diǎn)的度數(shù) } if(count%2==1) odd++;//若為奇數(shù)，則總數(shù)+1 } if(odd==0) cout<<"該圖沒(méi)有奇數(shù)度結(jié)點(diǎn)，具有歐拉回路，是歐拉圖。"<<endl; elseif(odd==2) cout<<"該圖有兩個(gè)奇數(shù)度結(jié)點(diǎn)，具有歐拉路，是半歐拉圖。"<<endl; else cout<<"該圖奇數(shù)度結(jié)點(diǎn)的個(gè)數(shù)為"<<odd<<"，所以不具有歐拉路。"<<endl;3、半歐拉圖中找出奇數(shù)度結(jié)點(diǎn)標(biāo)號(hào)： flag1=flag2=-1;//分別代表兩個(gè)奇數(shù)度結(jié)點(diǎn)的標(biāo)號(hào) for(i=0;i<n;i++){ count=0; for(j=0;j<n;j++){ count+=a[i][j]; } if(count%2==1){ if(flag1==-1) flag1=i+1; else flag2=i+1; } }4、求歐拉(回)路：voidfind(intfound,inttime){ inti,j,flag; for(i=0;i<n;i++){ if(a[found][i]==1){ flag=0; for(j=0;j<time;j++){//表示是否已經(jīng)存在 if(b[j]==i){ flag=1;break; } } if(!flag){ b[time]=i; time++; if(time<exist){//如果還沒(méi)走完 find(i,time);//遞歸 } else{ return; } } } }}四、運(yùn)行結(jié)果：首先是輸入結(jié)點(diǎn)數(shù)：然后隨機(jī)打印出鄰接矩陣：根據(jù)性質(zhì)判斷并求出歐拉圖：再試3次：實(shí)驗(yàn)報(bào)告五、實(shí)驗(yàn)小結(jié)這次題目要求是根據(jù)隨機(jī)生成的圖求歐拉（回）路，首先難點(diǎn)是如何隨機(jī)生成一個(gè)圖，這要考慮到3個(gè)細(xì)節(jié)：第1個(gè)是同一個(gè)結(jié)點(diǎn)之間沒(méi)有邊，第2個(gè)就是這是無(wú)向圖，一旦一個(gè)結(jié)點(diǎn)有了一條邊，對(duì)應(yīng)的另一個(gè)結(jié)點(diǎn)也要有一條邊，第3個(gè)是要考慮到孤立結(jié)點(diǎn)。在此基礎(chǔ)上生成了鄰接矩陣，歐拉圖判斷就好弄多了，只要判斷奇數(shù)度結(jié)點(diǎn)的個(gè)數(shù)。然后再用遞歸函數(shù)找到一條可行路即可。通過(guò)這次實(shí)驗(yàn)，加深了我對(duì)圖的相關(guān)知識(shí)的理解，也提高了我動(dòng)手編程的能力。五、指導(dǎo)教師評(píng)語(yǔ)