基于图分解的最优三角化图及连接树的构建

来源：应用数学学报杂志2017年第4期北京时间：

作者：徐平峰, 王福友, 邓文礼, 马文卿, 董小刚

单位：1. 长春工业大学统计系, 长春 130012;2. 恒生管理学院数学与统计系, 香港 999077;3. 东北师范大学数学与统计学院, 长春 130024

摘要：本文基于分解贝叶斯网道义图改进了传播算法的三角化图及连接树的构建.证明了寻找最优三角化图问题可以分解为素块上独立的小的子问题.于是，所有素块的最优三角化图的并即为贝叶斯网的最优三角化图.进一步，我们给出了一个算法，通过连接各个素块的最优三角化图的团树来构建全局最优三角化图的团树.我们进行了模拟实验来展示分解对于求三角化图及连接树的效果.

关键词：贝叶斯网,传播算法,分解,连接树,最优三角化图

基金资助：国家自然科学基金（11571050，11401047，11371083，11631003，11690012，11571051），吉林省科技发展计划项目（No.20140520059JH）资助项目.