離散數(shù)學(xué)實(shí)驗二柏超宇

1、實(shí) 驗 報 告（2015 / 2016 學(xué)年 第 二 學(xué)期）課程名稱離散數(shù)學(xué)實(shí)驗名稱集合上二元關(guān)系性質(zhì)判定的實(shí)現(xiàn)實(shí)驗時間2016年4月26日指導(dǎo)單位計算機(jī)科學(xué)與技術(shù)系指導(dǎo)教師羅衛(wèi)蘭學(xué)生姓名柏超宇班級學(xué)號Q15010125學(xué)院(系)貝爾英才學(xué)院專 業(yè)信息科技英才班實(shí) 驗 報 告實(shí)驗名稱集合上二元關(guān)系性質(zhì)判定的實(shí)現(xiàn)指導(dǎo)教師羅衛(wèi)蘭實(shí)驗類型實(shí)驗學(xué)時4實(shí)驗時間4.26一、 實(shí)驗?zāi)康暮鸵笳_判定任意二元關(guān)系的自反性、對稱性、傳遞性、反自反性和反對稱性。二、實(shí)驗環(huán)境(實(shí)驗設(shè)備)硬件：電腦軟件：操作系統(tǒng)：Windows 7編程軟件：Dev C+三、實(shí)驗原理及內(nèi)容首先輸入關(guān)系中包含元素的個數(shù)，其次輸入各個元素

2、的關(guān)系，以0 0結(jié)束，隨后根據(jù)矩陣的性質(zhì)和相應(yīng)矩陣運(yùn)算得出該二元關(guān)系具有的性質(zhì)。1、問題引入一個有n個頂點(diǎn)的有向圖的傳遞閉包為：有向圖中的初始路徑可達(dá)情況可以參見其鄰接矩陣A，鄰接矩陣中Ai,j表示i到j(luò)是否直接可達(dá)，若直接可達(dá)，則Ai,j記為1，否則記為0；兩個有向圖中i到j(luò)有路徑表示從i點(diǎn)開始經(jīng)過其他點(diǎn)（或者不經(jīng)過其他點(diǎn)）能夠到達(dá)j點(diǎn)，如果i到j(luò)有路徑，則將Ti,j設(shè)置為1，否則設(shè)置為0；有向圖的傳遞閉包表示從鄰接矩陣A出發(fā)，求的所有節(jié)點(diǎn)間的路徑可達(dá)情況，該矩陣就為所要求的傳遞閉包矩陣。例如：有向圖為：由該有向圖可以得到初始的鄰接矩陣為：那么warshall傳遞閉包算法的目的就是由鄰接矩陣

3、出發(fā)，進(jìn)行探索求出最終的傳遞閉包：2、動態(tài)規(guī)劃求解思路動態(tài)規(guī)劃將問題分段，本例warshall算法是通過一系列n階矩陣r（k）來構(gòu)造最終階段n階傳遞閉包矩陣r（n）    R(k) 由它的前趨 R(k-1) 計算得到（分級推進(jìn)計算）。    R(0) 該矩陣不允許它的路徑中包含任何中間頂點(diǎn)，即從該矩陣的任意頂點(diǎn)出發(fā)的路徑不含有中間頂點(diǎn)，此即鄰接矩陣。    R(1) 允許路徑中包含第1個頂點(diǎn)（本例編號 1）作為中間頂點(diǎn)。    R(2) 允許路徑

4、中包含前2個頂點(diǎn)（本例編號1 2）作為中間頂點(diǎn)。    R(k) 允許路徑中包含前k個頂點(diǎn)作為中間頂點(diǎn)。    R(n) 允許路徑中包含全部 n 個頂點(diǎn)作為中間頂點(diǎn)。    每個后繼矩陣 R(k) 對其前趨 R(k-1) 來說，在路徑上允許增加一個頂點(diǎn)， 因此有可能包含更多的1（增加前為1的在增加后依然為1）。3、具體的算法描述1 warshall（A1.n,1.n2 r(0)<-A;3 for(k=1;k<=n;k+)4 for(i=1;i<=n

5、;i+)5 for(j=1;j<=n;j+)6 r(k)i,j=r(k-1)i,j or(r(k-1)i,k and r(k-1)k,j);7 return r(n); 其他幾個性質(zhì)的代碼 ：int zifan()int flag1=1;for(i=1;i<=n;i+)if(aii!=1)flag1=0;break;return flag1;int fanzifan()int flag2=1;for(i=1;i<=n;i+)if(aii=1)flag2=0;break;return flag2;int duichen()int flag3=1;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(aij!=aji)flag3=0;break;return flag3; 最后我們可以通過返回flag來確定該矩陣具有的相應(yīng)性質(zhì)。 四、實(shí)驗小結(jié)（包括問題和解決方法、心得體會、意見與建議等）