弦圖的基本性質(zhì)及其推廣應(yīng)用.pdf

1、上海交通大學(xué)碩士學(xué)位論文弦圖的基本性質(zhì)及其推廣應(yīng)用姓名：何倩申請學(xué)位級別：碩士專業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：吳耀琨20081201ABSTRACTSome Basic Properties of Chordal Graphs and Their Applications and ExtensionsABSTRACTGraphical models are very important representation tools in many

2、fields, such as artificial intelligence, statistics, computational biology and so on. Decomposable models have been characterized as the kind of dependency models isomorphic to chordal graphs that are very useful to the

3、factorization and parameter estimation of the complicated statistical quantities. So the properties of chordal graphs and decompositions of graphs need to be well studied.In this paper, we introduce some basic properties

4、 of chordal graphs, study the corresponding structural chacterizations, including clique tree, minmum vertex separator, perfect elimination order and maximum weight spanning tree of clique graph. We propose the notion of

5、 strong junction property. The existence of clique tree which has the strong junction prop- erty are discussed. Furthermore, we generalize the properties of chordal graphs, study more closely various characterizations of

6、 prime decompo- sition and the algorithm to construct the MPD-trees of arbitrary graphs. We prove that every graph always possesses an MPD-tree which has the strong junction property. At last we investigate the character

7、izations of acyclic hypergraphs, give a direct proof of the fact that a hypergraph E has a cycle defined by the cycle-axiom if and only if E has a chordless hypercycle.KEY WORDS: chordal graph, clique tree, minimum verte