離散數學傳遞閉包是什麼意思

⑴ 離散數學中傳遞閉包怎麼求 通俗一點

方法：warshall法，即運行n次，每次使得MR[n][i],MR[i][n]都為1時使得MR[i][j]為1,否則還是為MR[i][j]。
傳遞閉包的計算過程一般可以用Warshell演算法描述： 
For 每個節點i Do
For 每個節點j Do
If j能到i Then
For 每個節點k Do
a[j, k] := a[j, k] Or ( a[j, i] And a[ i, k] ) 
其中a數組為布爾數組，用來描述兩個節點是否相連，可以看做一個無權圖的鄰接矩陣。演算法過程跟Floyd很相似，三重循環，枚舉每個中間節點。不過傳遞閉包只需要求出兩個節點是否相連，而不用求其間的最短路徑長。
傳遞性：對於一個節點i，如果j能到i，i能到k，那麼j就能到k。求傳遞閉包，就是把圖中所有滿足這樣傳遞性的節點都弄出來，計算完成後，就知道任意兩個節點之間是否相連。 
傳遞閉包的定義：R』是R（不具有傳遞性質）變動最少的步驟得到的具有傳遞性質的關系。
(1)離散數學傳遞閉包是什麼意思擴展閱讀
演算法實例：
#include
#define
 N
10 
int
judge(int
k,int
i,int
j)
{
if(i==1
&&
j==1){
return
1;
}
return
k;
}
void
warShall(int
MR[N][N],int
n)
{
for(int
k=0;k<n;k++){
for(int
i=0;i<n;i++){
for(int
j=0;j<n;j++){
if(i!=k
||
j!=k){
MR[i][j]=judge(MR[i][j],MR[k][j],MR[i][k]);
}
}
}
}
} 
int
main()
{
int
MR[10][10];
int
mul;
scanf("%d",&mul);
for(int
i=0;i<mul;i++){
for(int
j=0;j<mul;j++){
scanf("%d",&MR[i][j]);
}
}
printf("求傳遞閉包為:\n");
warShall(MR,mul);
for(int
i=0;i<mul;i++){
for(int
j=0;j<mul;j++){
printf("%d
",MR[i][j]);
}
printf("\n");
}
return
0;
}
運行結果：
參考資料：網路-傳遞閉包

⑵ 離散數學r的自反閉包，傳遞閉包和對稱閉包該怎麼算

自反閉包，是在原關系基礎上，加上所有自反關系。
類似地，傳遞閉包，是在原關系基礎上，補充符合傳遞性要求的關系。
對稱閉包，是在原關系基礎上，補充符合對稱性要求的關系。

⑶ 閉包的離散數學中

「關系」的閉包（Closure)
離散數學中，一個關系R的閉包，是指加上最小數目的有序偶而形成的具有自反性，對稱性或傳遞性的新的有序偶集，此集就是關系R的閉包。
設R是集合A上的二元關系，R的自反（對稱、傳遞）閉包是滿足以下條件的關系R'：
（i）R'是自反的（對稱的、傳遞的）；
（ii）R'⊇R；
（iii）對於A上的任何自反（對稱、傳遞）關系R，若R⊇R，則有R⊇R'。
R的自反、對稱、傳遞閉包分別記為r(R）、s(R) 和t(R）。
性質1
集合A上的二元關系R的閉包運算可以復合，例如：
ts(R)=t(s(R))
表示R的對稱閉包的傳遞閉包，通常簡稱為R的對稱傳遞閉包。而tsr(R)則表示R的自反對稱傳遞閉包。
性質2
設R是集合A上的二元關系，則有
（a）如果R是自反的，那麼s(R）和t(R）也是自反的；
（b）如果R是對稱的，那麼r(R）和t(R）也是對稱的；
（c）如果R是傳遞的，那麼r(R）也是傳遞的。
性質3
設R是集合A上的二元關系，則有
（a）rs(R)=sr(R）；
（b）rt(R)=tr(R）；
（c）ts(R)⊇ st(R）。

⑷ 傳遞閉包是什麼意思

設R是X上的二元關系，如果另一個關系R1滿足：R1是傳遞的，R是R1的子集，對於任何可傳遞關系R11如果有R是R11的子集，就有R1是R11的子集。則稱R1是R的傳遞閉包。我的理解就是對於一個關系的一個最小的傳遞關系。
一個數學概念，在某些領域有應用，我以前是在離散數學裡面學的，後來在計算理論裡面又遇到了。

⑸ 等價關系的傳遞閉包是什麼

R={,,,,,,,};
因為R是傳遞的,所以t(R)=R.
我是正在學離散數學的學生,

⑹ 關系的傳遞(離散數學）

傳遞關系判斷離散數學中有定理可以判斷，通過矩陣變換等。
按定理算比較麻煩，可以如下計算,其實是計算傳遞閉包與原關系是否一樣,一樣則是傳遞關系,否則不是傳遞關系.
就是關系中一個元素的第二個分量若與另外一個元素的第一個分量相同,則把前者的第一分量與後者的第二個分量組成元素加入關系中.
直到所有這樣的情形找出,計算完畢.
例如:R2計算傳遞閉包如下:
R2={(1,2),(2,3)}
存在上述情況,把(1,3)加入形成R2'
R2'={(1,2),(2,3),(1,3)}
所有計算結束與R2不同,所以不是傳遞關系.若R2是{(1,2),(2,3),(1,3)}則是傳遞關系.
而R和R1計算結果不變,所以是傳遞的.

⑺ 離散數學傳遞閉包證明

因為∅∪∅=∅
所以∀n∅ⁿ=∅
t(∅)=∪∅ⁿ=∅

t(R)=∪Rⁿ
(t(R))²=∪R²ⁿ ⊆ ∪Rⁿ
⋮
(t(R))ⁿ=∪Rⁿⁿ ⊆ ∪Rⁿ
從而t(R)∪(t(R))²∪(t(R))³⋯
=∪Rⁿ
即t(t(R))=∪Rⁿ = t(R)

⑻ 離散數學當中的"閉包"有什麼實際應用，能否舉例

關系閉包在數學中,在日常生活中均有廣泛的應用,比如在數學中,小於()關系均沒有自反性,但它們的的自反閉包是小於等於(≤)或大於等於((≥),卻有自反性,在數學中經常要用到小於關系表示量之間的關系,但是有時感到用小於關系不方便,而用小於等於關系,實際上是將量之間的關系進行擴大,不自覺地用了小於的自反閉包,日常生活中我們按同齡或同班或同鄉關系將人分組,一般來說同齡,同班,同鄉關系指兩個不同的人之間的一種關系,這種關系就不具有自反性,如果我們約定了自已與自已同齡,同班,同鄉,此時它們就有了自反性,如果僅有一個人和其他人年齡均不同,此時他自已就可構成一組.
小於關系是不對稱,它的逆關系大於關系也是不對稱,但將兩者關系並起來(將關系看成集合),得不等關系卻是的對稱的,不等關系是小於或大於關系的對稱閉包,夫對妻的關系是不對稱的,妻對夫的關系也是不對稱的,但對稱閉包婚姻關系卻是對稱的(考慮到男女平等,即對稱性).大於1的關系是不傳遞的,大於2的關系也是不傳遞的,…將大於1,大於2,大於3,…全部並起來得到大於關系卻是傳遞的,大於關系是大於1的關系的傳遞閉包,父子關系是不傳遞的,但它的傳遞閉包是長輩對後輩關系卻是傳遞的.