弦图的基本性质及其推广应用

论文摘要

图模型在人工智能、统计学、计算生物学等领域都是非常重要的模型工具。弦图作为可分解的一种图模型被引入,在复杂统计量的分解和参数估计方面有着极大的应用,因此我们需要深入地研究弦图以及图分解的相关性质。本文首先介绍了弦图的基本性质,主要研究了从极小点分离集,团树,完美消去排序,赋权团图的极大支撑树等角度对弦图结构的刻画。接着我们提出了关于团树强连接性的概念,并且证明了具有强连接性质的团树的存在性。然后将弦图的性质进行推广,重点研究了关于图的素分解的几个等价刻画,介绍了图的极大素子图树TMPD的生成算法并利用该算法证明了极大素子图树也能具有强连接性质。最后讨论了无圈超图的一些特征,给出了超图ε含有由圈公理定义的圈当且仅当ε含有无弦的超圈的直接证明。

论文目录

• 中文摘要
• 英文摘要
• 目录
• 符号说明
• 第一章 弦图的基本性质
• §1.1 引言
• §1.2 基本概念
• §1.3 弦图的树表示
• §1.4 完美消去排序
• §1.5 极小分离集的一些基本性质
• §1.6 G 的极小三角化（minimum triangulation）
• 第二章 图的分解
• §2.1 引言
• §2.2 极大素子图（maximal prime subgraph）
• §2.3 P-分解
• §2.4 图分解的算法
• §2.5 极大素子图树（MPD-tree）
• 第三章 超图的有关性质
• §3.1 引言
• §3.2 无圈超图的刻画
• 第四章 总结与展望
• §4.1 工作总结
• §4.2 展望
• 参考文献
• 致谢
• 攻读硕士学位期间已发表或录用的论文