第
32
卷第
3
期 唐山学院学报
Vol.32No.3
2019
年
05
月
JournalofTan
g
shanUniversit
y
Ma
y
2019
作者简介
:
孙翠先
(
1963-
),
男
,
河北丰南人
,
教授
,
主要从事数理统计研究
.
传递闭包的
Matlab
实现
孙翠先
,
张
健
,
吴焕春
(
唐山学院 基础教学部
,
河北 唐山
063000
)
摘要
:
在
Warshall
算法基础上
,
基于
Matlab
软件
,
编写出求传递闭包的计算程序
,
并得到了新
添加的序偶矩阵
.
关键词
:
Matlab
;
序偶矩阵
;
传递闭包
;
计算程序
中图分类号
:
O144.1
文献标志码
:
A
文章编号
:
1672 349X
(
2019
)
03 0008 02
DOI
:
10.16160
/
j
.cnki.tsx
y
xb.2019.03.002
TheRealizationofTransitiveClosuresb
y
Matlab
SUNCuiGxian
,
ZHANGJian
,
WUHuanGchun
(
De
p
artmentofFundamentalScienceTeachin
g
,
Tan
g
shanUniversit
y
,
Tan
g
shan063000
,
China
)
Abstract
:
BasedonWarshallal
g
orithm
,
thecalculation
p
ro
g
ramforsolvin
g
transitiveclosure
is
p
resentedwithMatlabsoftware.Inthisstud
y
,
theadditionalmatrixofordered
p
airisalG
soobtained.
Ke
y
Words
:
Matlab
;
ordered
p
airmatrix
;
transitiveclosure
;
p
ro
g
ram
0
引言
集合
A
上 的 二 元 关 系
R
的 传 递 性 描 述 了
序偶之间的内在联系
.
当
A
的元数
|
A
|
比较小
(
|
A
|≤4
)
时
,
可 通 过 序 偶 法
、
关 系 矩 阵 法 或 关
系图法判定
,
计 算 量 不 大
,
人 工 判 定 可 以 完 成
.
但当
|
A
|
较大时
,
不论上述 三 种方法哪 一 种
,
人
工计算量都非常巨大
,
基 本 上 不 可 能 完 成
.
而
求关系
R
的传递闭包
t
(
R
)
时
,
当
R
不具有传递
性
,
就需要通过 不 断 添 加 新 序 偶 使 之 具 备 传 递
性为止
.
因此当
|
A
|
较大时
,
求
t
(
R
)
变得非常
困难
.
此 时
Warshall
提 出 了 一 种 算 法
[
1
]
.
本
文在
Warshall
算 法 基 础 上
,
利 用 关 系 矩 阵
,
借
助数学软件
Matlab
,
给 出 求
t
(
R
)
的 优 化 算 法
.
此法实现了传递闭包的
Matlab
计算
,
最大优 点
是对
|
A
|
无限制
,
程序简便 易 操作
,
最重要的 一
点是给出了新添加的序偶矩阵
.
1
算法
1.1
符号引入
给定集 合
A
上 的 一 个 二 元 关 系
R
,
设
M
R
为
R
的关系 矩阵
,
M
R
=
(
r
i
j
),
这里
r
i
j
只取
0
或
1
,
它是一个布尔矩 阵
.
设集合
A
=
{
a
1
,
a
2
,,
a
n
},
t
(
R
)
的关系矩阵为
M
t
(
R
)
.
1.2
传递闭包的矩阵性质
文献
[
2
]
给出了传递闭包的关系矩阵
M
t
(
R
)
=
M
R
+
M
2
R
+
+
M
n
R
,
对此
Warshall
提出了一种
算法
,
适合用
C
语言方式编译求
M
t
(
R
)
.
下面借
助
Matlab
给出一种新优化算法
,
优越性在于求
出了
M
NR
.
1.3 Matlab
程序
Mt=R
;
a=size
(
R
);
fork=1∶a