从基本割集矩阵综合有向图的分解法
来源期刊:工程科学学报1994年第2期
论文作者:黄汝激
关键词:网络综合;超图;有向图;Q矩阵;
摘 要:引入了有向基本割集矩阵Qf的二分解和分解树的概念,导出了Qf可实现的充分必要条件和所实现图G在有向二同构意义上的唯一性,应用超图理论解决了如何求Qf的二分解问题,提出了用分解法直接实现Qf的原理和算法.该原理可计算复杂度为O(v ̄2l ̄2)、v和l为Qf的树路子阵Qfp的行数和列数.
黄汝激
北京科技大学自动化系
摘 要:引入了有向基本割集矩阵Qf的二分解和分解树的概念,导出了Qf可实现的充分必要条件和所实现图G在有向二同构意义上的唯一性,应用超图理论解决了如何求Qf的二分解问题,提出了用分解法直接实现Qf的原理和算法.该原理可计算复杂度为O(v ̄2l ̄2)、v和l为Qf的树路子阵Qfp的行数和列数.
关键词:网络综合;超图;有向图;Q矩阵;