離散實驗報告四

1、一、實驗?zāi)康呐袛嚯S機生成的鄰接矩陣是否為歐拉圖或歐拉半圖，若是，求取其歐拉回路或歐拉路。二、問題分析本實驗的最終目的是要求取歐拉圖的歐拉回路或歐拉半圖的歐拉路，那么在這之前我們需要完成的是鄰接矩陣的生成，圖的連通性判別，如若連通，再判斷其是否為歐拉圖或歐拉半圖，最終求取歐拉回路或歐拉路。1.生成隨機矩陣定義數(shù)組二維數(shù)組l，用以存儲鄰接矩陣的信息。再定義結(jié)點數(shù)目n，從鍵盤鍵入之。根據(jù)n的大小，在嵌套的for循環(huán)中，每次循環(huán)都利用rand函數(shù)隨機生成某數(shù)并對2取余，將結(jié)果賦值給lij。當然在for循環(huán)之前需要調(diào)用srand函數(shù)取計算機當前時間作為種子，防止rand函數(shù)生成偽隨機數(shù)。2.判斷連通性考

2、慮到在上述步驟中已經(jīng)有圖的鄰接矩陣生成，可以考慮用可達性矩陣來判斷圖的連通性。這樣，問題的關(guān)鍵就變成了求取可達性矩陣的問題。為了不影響原鄰接矩陣信息，定義新二維數(shù)組p復(fù)制鄰接矩陣數(shù)據(jù)來進行運算操作，并定義二維數(shù)組s，初始化為全0，用來存儲最終可達性矩陣。具體操作應(yīng)為：首先將利用for循環(huán)將p與l相乘，結(jié)果存于p中；而后將p加上s，結(jié)果存于s中。再將以上步驟整體置于一個循環(huán)n次的for循環(huán)下。執(zhí)行完之后，檢查s，將非零值都修正為1，這樣我們可以得到可達性矩陣s。最后，遍歷檢查s中每個元素的值，如果發(fā)現(xiàn)有元素值為0，那么該圖不具有連通性；否則，該圖具有連通性，可以進行下面步驟的判斷。3.判斷是否為

3、歐拉圖或歐拉半圖定義數(shù)組deg，用來存儲每個結(jié)點的度。依行檢查l，將第i行的值相加可得degi。再依據(jù)deg來判斷該圖是否為歐拉圖或歐拉半圖：如果每個結(jié)點的度均為偶數(shù)，該圖為歐拉圖；如果奇數(shù)度結(jié)點個數(shù)為2，該圖為歐拉半圖；否則，兩者均不是。4.歐拉路或歐拉回路的求取對于歐拉路或歐拉回路的求取，我們依舊利用鄰接矩陣來求。（1）求取歐拉回路時，我們可以任意選擇起點開始。按行搜索鄰接矩陣，若果檢查第i行時發(fā)現(xiàn)lij非0，將其修正為0后，輸出i->j，搜索第j行，如此循環(huán)，可得歐拉回路。當然在此之前我們需要求得每個結(jié)點的度數(shù)之和sum，來控制上述循環(huán)次數(shù)不超過sum/2，使得循環(huán)可以適時結(jié)束。（

4、2）在求取歐拉路時，只要控制循環(huán)起點為奇數(shù)度結(jié)點即可。其他步驟與上述求取歐拉回路步驟一致。三、具體程序?qū)崿F(xiàn)#include <iostream>#include <cstdlib>#include <ctime>using namespace std;int main()int n,l2020,p2020,s2020;int deg20;/用于存儲每個結(jié)點的度數(shù)int count1=0;/用于存儲奇數(shù)度結(jié)點個數(shù)int start=0;srand(int)time(0);cout<<"請輸入結(jié)點個數(shù):"cin>>n;

5、for(int i=0;i<n;i+)for(int j=i;j<n;j+)if(i=j)lij=0;elselij=rand()%2;lji=lij;cout<<"隨機生成領(lǐng)接矩陣："<<endl;for(i=0;i<n;i+)degi=0;for(int j=0;j<n;j+)cout<<lij<<" "cout<<endl;/通過可達性矩陣判斷連通性for(i=0;i<n;i+)for(int j=0;j<n;j+)pij=lij;sij=0;for(i

6、nt y=0;y<n;y+) for(i=0;i<n;i+) for(int j=0;j<n;j+) sij+=pij; for(i=0;i<n;i+) for(int j=0;j<n;j+) for(int k=0;k<n;k+) pij+=pik*lkj; for(i=0;i<n;i+)for(int j=0;j<n;j+)if(sij!=0)sij=1;cout<<"可達性矩陣為:"<<endl;for(i=0;i<n;i+)for(int j=0;j<n;j+)cout<<

7、;sij<<" "cout<<endl;/歐拉（半）圖的判斷和歐拉（回）路的的求取int sum=0;for(i=0;i<n;i+)for(int j=0;j<n;j+)if(lij=1)degi+;for(i=0;i<n;i+)if(degi%2!=0)count1+;start=i;for(i=0;i<n;i+)sum=sum+degi;for(i=0;i<n;i+)for(int j=0;j<n;j+)if(sij=0)cout<<"此圖不連通"<<endl;cou

8、t<<"既不是歐拉圖也不是歐拉半圖"<<endl;return 0;int x=0;int j=100;cout<<"此圖連通"<<endl;if(count1=0)cout<<"是歐拉圖，歐拉回路如下："<<endl;for(i=0;x<sum/2;i=j)for(j=0;j<n;j+)if(lij=1)cout<<i+1<<"->"<<j+1<<endl;lij=0;lji=0;x+;break;else if(count1=2)cout<<"是歐拉半圖，歐拉路如下："<<endl;for(i=start;x<sum/2;i=j)for(j=0;j<n;j+)if(lij=1)cout<<i+1<<&qu