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

摘要

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