小型微型计算机系统
小型微型計算機繫統
소형미형계산궤계통
MINI-MICRO SYSTEMS
2013年
8期
1862-1865
,共4页
极大独立集%邻接矩阵%二分树
極大獨立集%鄰接矩陣%二分樹
겁대독립집%린접구진%이분수
maximum independent sets%adjacency matrix of graph%binary tree
图的极大独立集在计算机视觉、计算机网络、编码理论和资源配置等领域有着广泛的应用.本文利用图的分解方法给出了一个求简单无向图所有极大独立集的递归公式.定义了图的邻接矩阵的两个变换和点集合的一些运算.在此基础上,利用二分树给出了一个求无向图的所有极大独立集的有效算法.算法的时间复杂度是O(mn),其中m,n分别是图的所有极大独立集数和顶点个数.算法只需对网络的邻接矩阵进行处理,在计算机上实现起来非常方便.最后,通过实例验证了算法的有效性.
圖的極大獨立集在計算機視覺、計算機網絡、編碼理論和資源配置等領域有著廣汎的應用.本文利用圖的分解方法給齣瞭一箇求簡單無嚮圖所有極大獨立集的遞歸公式.定義瞭圖的鄰接矩陣的兩箇變換和點集閤的一些運算.在此基礎上,利用二分樹給齣瞭一箇求無嚮圖的所有極大獨立集的有效算法.算法的時間複雜度是O(mn),其中m,n分彆是圖的所有極大獨立集數和頂點箇數.算法隻需對網絡的鄰接矩陣進行處理,在計算機上實現起來非常方便.最後,通過實例驗證瞭算法的有效性.
도적겁대독립집재계산궤시각、계산궤망락、편마이론화자원배치등영역유착엄범적응용.본문이용도적분해방법급출료일개구간단무향도소유겁대독립집적체귀공식.정의료도적린접구진적량개변환화점집합적일사운산.재차기출상,이용이분수급출료일개구무향도적소유겁대독립집적유효산법.산법적시간복잡도시O(mn),기중m,n분별시도적소유겁대독립집수화정점개수.산법지수대망락적린접구진진행처리,재계산궤상실현기래비상방편.최후,통과실례험증료산법적유효성.
