多边修正算法中的换顶原理及复杂性分析  

The Vertex-exchange Principles in Multilateral Amending Algorithmand the Complexity Analysis

作　　者：田艳芳[1] 汪益川[2] 吴松林[1] 杨秀文[1] 

机构地区：[1]后勤工程学院基础部,重庆401311 [2]后勤工程学院科研部,重庆401311

出　　处：《后勤工程学院学报》2010年第3期86-91,共6页Journal of Logistical Engineering University

摘　　要：对于无向赋权图,利用换顶过程中矩阵翻转与数据块调换时上三角部分数据的变化规律,对权值矩阵的数据进行处理,以完成无向完全图中H圈（H路类似）的修正过程。事实上,多边修正的原理最终是通过变换顶点达到的,而其主要用到的换顶规则是矩阵数据的块调换与翻转,该思想还可以推广到有向图的情形。最后利用换顶原理对多边修正算法进行了复杂性分析,讨论修正边数对复杂性的影响。For undirected weighted digraphs,in thispaper the data of weight matrix is processed with the transforming law of upper triangular part of the matrix datainmatrix inversionand data-blockexchanging of vertex-exchange process,to amend the complete undirected H-cycle（similar to H-path）.In fact,the principle of multilateral amendment is ultimately achieved through the transforming of vertexes.And it mainlyuses the block-exchanging and reversion of the matrix data.This ideacan also be extended to the case of directed graph.Finally,the vertex-exchange principle is used to give thecomplexity analysis of multilateral amending algorithmand the impact of the amending edge＇s number to the algorithmcomplexity.

关 键 词：赋权图 H圈 权值矩阵 换顶 翻转 调换 复杂性分析 

分 类 号：O157.5[理学—数学]