只减少边的数目的一般性骨架矩阵的求法


此处输入要素的个数:

返回首页



一般性骨架矩阵:指的是系统里存在环路,在不进行缩点处理的情况下,把其它向前边全部删除。回路元素用一个回环表示!

骨架矩阵求解基本上都是利用代数方法,该方法好理解但是操作起来的计算量要更大,主要是处理缩点的时候:

对于有向无环图(DAG),其骨架矩阵可以用简单的代数方法求解,就是R-(R-I)^2-I;对DAG来说。所减掉的边,都为向前边。

对于有环图的缩减,主要是在环路边的缩减替换上。其中环路内部的边都用一条方向代替。环路的出边,与入边可以多种方式处理。一种是指定出边或者入边的节点。一种是不指定。也可以单独指定出边的结点。

此处使用的骨架矩阵算法利用最小并集进行计算:

第一:求出强连通子集,返回一个有序的结点集合,边都朝上。

第二:判断当前层的要素数量,如果大于2个要素表示有环路。计算每个要素的可达集合,其并集减去本层要素的结点,就是环路所有的出边。也就是环路所有的出边。

第三:判断当前所有的出边,访问到的每个层级只记录第一次的访问,获得第一次缩边,因为当前层(环路),可能有两次出边指向同一个节点,或者同一个环路。

第四:经过第一次缩边后,判断当前出边Now数目是否大于2条,大于2的话,计算每条向上边,该向上边到达的结点的可达集合R+,如果R+与包含本层级的向上的边也就是Now有交集,这个交集就是有公共祖先的边,也就是该条边为向前边,在Now中删除所有公共祖先的边。

第五:最后得到的Now是最少出边,这个时候,如果当前层是个大于二的环路。要给环路每个要素构建最小出边集。方式有2种。

A、第一种方法 指定一个环路一个结点的出边为所有的Now+指向环路下一个结点,环路最后一个结点指向环路第一个结点。

B、第二种方法,根据原始矩阵中要素的出边与当前向上边Now里面的交集,然后删除Now里面已有的交集,加上指向环内下个结点的边,就为当前要素所有的出边。

C、第三种方法,保留环内的边,计算自身与总出边的并集,再并自己在环内的边。

具有环路的有向图其最小骨架矩阵不唯一,这图都有相似性。最核心的特征有三。

A:边的数目最小

B:不改变系统的可达关系,本矩阵与原始矩阵互为等可达关系。

C:不缩点的骨架矩阵不具有唯一性,大部分变化与环有关系。

 

 



显示的是一个随机 12 * 12 的方阵



  
                     1            
1                               1
1             1          1 1   
1    1                           
                        1         
1 1                      1      
      1                1         
      1                           
                                   
                                   
   1                   1 1      
      1                           

第一步,获得所有的环路



子要素
丑要素
寅要素
卯要素
辰要素
巳要素
午要素
未要素
申要素
酉要素
戌要素
亥要素
第0层
第1层
第2层
第3层
第4层
第5层

第一种,利用公共祖先的的最小并集进行求解,得到不缩点的骨架矩阵的,本处指定了环路的出边



子要素
丑要素
寅要素
卯要素
辰要素
巳要素
午要素
未要素
申要素
酉要素
戌要素
亥要素
第0层
第1层
第2层
第3层
第4层
第5层

第二种,本处没有环路的出边,环路中的出边都在原始矩阵中存在



子要素
丑要素
寅要素
卯要素
辰要素
巳要素
午要素
未要素
申要素
酉要素
戌要素
亥要素
第0层
第1层
第2层
第3层
第4层
第5层

第三种,保证环内信息,环外进行缩边



子要素
丑要素
寅要素
卯要素
辰要素
巳要素
午要素
未要素
申要素
酉要素
戌要素
亥要素
第0层
第1层
第2层
第3层
第4层
第5层

化学加平台
解释结构模型
感谢化学加提供单独服务器服务器!请大家多支持化学加平台,可以多介绍人关注化学加!
对解释结构模型在线计算有什么意见与建议请发电子邮件到, hwstu #sohu.com 把#替换成 @