图的树分解算法及其应用

• 作者: 许道云 雷莹
• 来源期刊: 计算机科学
• 关键词: 树分解 CNF公式 树宽度 求解难度
• 年，卷（期）: 2020,（5）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 51-58
• 页数: 8页
• 字数: 9714字
• 语种: 中文
• DOI: 10.11896/jsjkx.191100118

摘要

一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中.将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度.一个合取范式(Conj unctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示.忽略公式因子图中边上的符号,得到一个二分图.文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解.通过实验观察公式因子图的树宽度与求解难度之间的联系.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学与技术学院	125	460	12.0	16.0
2	雷莹	贵州大学计算机科学与技术学院	1	0	0.0	0.0