强连通子集判断，回路判断，系统的回路缩减，矩阵的缩减，矩阵缩点缩减法以及其表示方法

论文写作或者计算需要帮助可发邮件到 hwstu # sohu.com 把 #替换成@，请说清来意，不必拐弯抹角，浪费相互之间的时间。

返回首页

此处输入要素的个数：

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


   子丑寅卯辰巳午未申酉戌亥
子          1    1 1               
丑                            1      
寅                                  1
卯             1 1                  
辰       1 1          1 1         
巳                            1      
午                                    
未 1                                 
申                                    
酉    1       1                     
戌       1                           
亥       1       1                  

对于系统里面的强连通子集，可以用一个缩点来表示


什么是强连通分量(StronglyConnected Component)(或者，被称为强连通子图，Strongly Connected Subgraph)
首先需要明白的是，强连通分量只可能存在于有向图中，无向图中是不存在强连通分量的，当然，无向图中也有对应物，被称为连通分量(Connected Component)，
求解无向图中的连通分量，根据具体要求，可以选择使用并查集或者DFS。
强连通分量是图论中的概念。图论中，强连通图指每一个顶点皆可以经由该图上的边抵达其他的每一个点的有向图。
意即对于此图上每一个点对(Va,Vb)，皆存在路径Va→Vb以及Vb→Va。强连通分量则是指一张有向图 G 的极大强连通子图 G'。
如果将每一个强连通分量缩成一个点，则原图 G 将会变成一张有向无环图。
一张图被称为有向无环图当且仅当此图不具有点集合数量大于一的强连通分量，因为有向环也就是回路即是一个强连通分量，
而且任何的强连通分量皆具有至少一个回路。
Kosaraju算法、Tarjan算法、Gabow算法皆为寻找有向图强连通分量的有效算法。这三种算法的时间复杂度都是一样，为O(V+E)V为顶点，E为边。
这三个算法都是一个线性算法。
但是由于在Tarjan 算法和 Gabow 算法的过程中，只需要进行一次的深度优先搜索，因而相对 Kosaraju 算法较有效率。
原始矩阵 对所有的强连通分量着色显示 对所有的强连通分量着色显示
   子丑寅卯辰巳午未申酉戌亥
子          1    1 1               
丑                            1      
寅                                  1
卯             1 1                  
辰       1 1          1 1         
巳                            1      
午                                    
未 1                                 
申                                    
酉    1       1                     
戌       1                           
亥       1       1                  
   申 午 子 丑 寅 卯 辰 巳 未 酉 亥 戌
申                                   
午                                   
子   1          1    1            
丑                           1      
寅                              1   
卯                  1 1            
辰1          1 1       1         
巳                           1      
未      1                           
酉         1       1               
亥            1       1            
戌            1                     
   申 午 子 丑 寅 卯 辰 巳 未 酉 亥 戌
申                                   
午                                   
子   1          1    1            
丑                           1      
寅                              1   
卯                  1 1            
辰1          1 1       1         
巳                           1      
未      1                           
酉         1       1               
亥            1       1            
戌            1                     

原始矩阵缩点显示

“缩点”的概念： 由于强连通分量的特殊性，在一些实际应用中，会将每个强连通分量看成一个点，然后进行处理。
这样做主要是为了降低图的复杂度，特别是在强连通分量规模大、数量多的情况中，利用“缩点”能大幅度降低图的复杂度，其对应系统的复杂程度也大大降低。
缩点后得到的图，必定是DAG也就是有向无环图。
用反证法能够很方便的进行证明：因为若图中含有环路，即意味着至少有两个点彼此可达，那么按照强连通分量的定义，这两个点应该属于一个分量中，因而在缩点发生后，会被一个点所代表。
原始矩阵 强连通分量的数目 缩减环路后的方阵显示 缩减环路后链表表示
   申 午 子 丑 寅 卯 辰 巳 未 酉 亥 戌
申                                   
午                                   
子   1          1    1            
丑                           1      
寅                              1   
卯                  1 1            
辰1          1 1       1         
巳                           1      
未      1                           
酉         1       1               
亥            1       1            
戌            1                     
环包含：
申
环包含：
午
环包含：
子,丑,寅,卯,辰,巳,未,酉,亥
环包含：
戌
   子＋丑＋寅＋卯＋辰＋巳＋未＋酉＋亥午申戌
子＋丑＋寅＋卯＋辰＋巳＋未＋酉＋亥 1 1 1   
午            
申            
戌 1         
子＋丑＋寅＋卯＋辰＋巳＋未＋酉＋亥 子＋丑＋寅＋卯＋辰＋巳＋未＋酉＋亥、午、申、
戌 子＋丑＋寅＋卯＋辰＋巳＋未＋酉＋亥、

独立系统与它们的环分析


矩阵的分拆结果如下

独立系统序号 独立系统的组成元素 独立系统的 方阵表示 该系统的换着色标识 最终矩阵标识
第1个系统中包含：
子,丑,寅,卯,辰,巳,午,未,申,酉,戌,亥
   子丑寅卯辰巳午未申酉戌亥
子          1    1 1               
丑                            1      
寅                                  1
卯             1 1                  
辰       1 1          1 1         
巳                            1      
午                                    
未 1                                 
申                                    
酉    1       1                     
戌       1                           
亥       1       1                  
   申 午 子 丑 寅 卯 辰 巳 未 酉 亥 戌
申                                   
午                                   
子   1          1    1            
丑                           1      
寅                              1   
卯                  1 1            
辰1          1 1       1         
巳                           1      
未      1                           
酉         1       1               
亥            1       1            
戌            1                     
   子＋丑＋寅＋卯＋辰＋巳＋未＋酉＋亥午申戌
子＋丑＋寅＋卯＋辰＋巳＋未＋酉＋亥 1 1 1   
午            
申            
戌 1         

原始矩阵图形化表示如下


子要素
丑要素
寅要素
卯要素
辰要素
巳要素
午要素
未要素
申要素
酉要素
戌要素
亥要素

所有环路缩点后的图形表示


子＋丑＋寅＋卯＋辰＋巳＋未＋酉＋亥要素
午要素
申要素
戌要素

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