Some Basic Properties Of Chordal Graphs And Their Applications And Extensions

Graphical models are very important representation tools in many 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 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 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 strong junction property.The existence of clique tree which has the strong junction property are discussed.Furthermore,we generalize the properties of chordal graphs,study more closely various characterizations of prime decomposition 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 characterizations of acyclic hypergraphs,give a direct proof of the fact that a hypergraphεhas a cycle defined by the cycle-axiom if and only ifεhas a chordless hypercycle.