弦图的基本性质及其推广应用
|
摘要
图模型在人工智能、统计学、计算生物学等领域都是非常重要的模型工具。弦图作为可分解的一种图模型被引入,在复杂统计量的分解和参数估计方面有着极大的应用,因此我们需要深入地研究弦图以及图分解的相关性质。
本文首先介绍了弦图的基本性质,主要研究了从极小点分离集,团树,完美消去排序,赋权团图的极大支撑树等角度对弦图结构的刻画。接着我们提出了关于团树强连接性的概念,并且证明了具有强连接性质的团树的存在性。然后将弦图的性质进行推广,重点研究了关于图的素分解的几个等价刻画,介绍了图的极大素子图树T_(MPD)的生成算法并利用该算法证明了极大素子图树也能具有强连接性质。最后讨论了无圈超图的一些特征,给出了超图ε含有由圈公理定义的圈当且仅当ε含有无弦的超圈的直接证明。
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.
本文首先介绍了弦图的基本性质,主要研究了从极小点分离集,团树,完美消去排序,赋权团图的极大支撑树等角度对弦图结构的刻画。接着我们提出了关于团树强连接性的概念,并且证明了具有强连接性质的团树的存在性。然后将弦图的性质进行推广,重点研究了关于图的素分解的几个等价刻画,介绍了图的极大素子图树T_(MPD)的生成算法并利用该算法证明了极大素子图树也能具有强连接性质。最后讨论了无圈超图的一些特征,给出了超图ε含有由圈公理定义的圈当且仅当ε含有无弦的超圈的直接证明。
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.
引文
1.Barrett,W.W.,Johnson,C.R.,& Lundquist,M.,Determinantal formulae for matrices with sparce inverses[J],Linear Algebra Appl.121(1989),265-289.
2.Beeri,C.,Fagin,R.,Maier,D.,& Yannakakis,M.,On the desirability of acyclic database systems[J],J.Assoc.Comput.Mach.30(1983),479-513.
3.Berge,C.,Graphs and Hypergraphs,Amsterdam:North-Holland Publishing Company,1973.
4.Bernstein,P.A.,& Goodman,N.,Power of natural semjoins[J],SIAM J.Comput.10(1981),751-771.
5.Berry,A.,D(?)sarticulation d'un graphe,Ph.D.Thesis,LIRMM,Montpellier,France,1998.6.Berry,A.,Bodat,J.P.,& Cogis,O.,Generating all the minimal separators of a graph[J],Internat.J.Foundations Comput.Sci.11(2000),397-404.
7.Bouchitt(?),V.,& Todinca,I.,Treewidth and minimum fill in:grouping the minimum separators[J],SIAM J.Comput.31(2001),212-232.
8.Brandst(a|¨)dt,A.,Le,V.B.,& Spinrad,J.P.,Graph classes:A Survey,Philadelphia:SIAM,1999.
9.Buneman,P.,A characterisation of rigid circuit graphs[J],Discrete Math.9(1974),205-212.
10.Chandran,L.S.,Ibarra,F.,Ruskey,F.,& Sawada,J.,Generating and characterizing the perfect elimination orderings of a chordal graph[J],Theoret.Comput.Sci.307(2003),303-317.
11.Chung,F.R.K.,& Mumford,D.,Chordal completions of planar graphs[J],J.Symbolic Comput.31(1994),96-106.
12.Dacar,F.,The cyclicity of a hypergraph[J],Discrete Math.182(1998),53-67.
13.Darroch,J.N.,Lauritzen,S.L.,& Speed,T.P,Markov field and loglinear intersection models for contingency tables[J],Ann.Statist.8(1980),522-539.
14.de Campos,L.M.,Characterizations of decomposable dependency models[J],Artificial Intelligence Research,5(1996),289-300.
15.Diestel,R.,Graph Decomposition-A Study in Infinite Graph Theory,Oxford:Clarendon Press,1990.
16.Dirac,G.A.,On rigid circuit graphs[J],Abhandlungen Mathematis- ches Semonar Hamburg.25(1961),71-76.
17.Dobra,A.,Markov bases for decomposable graphical models[J],Bernoulli 9(2003),1093-1108.
18.Jensen,F.V.,Bayesian Networks and Decision Graphs,New York:Springer,2002.
19.Fulkerson,D.R.,& Gross,O.A.,Incidence matrices and interval graphs[J],Pacific J.Math.15(1965),835-855.
20.Fukuda,M.,Murota,K.,& Nakata,K.,Exploiting sparsity in semidefinite programming via matrix completion[J],SIAM J.Optim.11(2000),647-674.
21.Gavril,F.,The intersection graphs of subtrees in trees are exactly the chordal graphs[J],J.Combin.Theoy Ser.B 16(1974),47-56.
22.Gilmore,P.C.,& Hoffman,A.J.,A characterization of comparability graphs and of interval graphs,Canad.J.Math.16(1964),539-548.
23.Golumbic,M.C.,Algorithmic Graph Theory and Perfect Graphs,New York:Academic Press,1980.
24.Goodman,N.,& Shmueli,O.,Syntactic characterization of tree database schemes[J],Assoc.Comput.Mach.30(1983),767-786.
25.Grone,C.R.,Johnson,C.R.,Sá E.M.,& Wolkowicz,H.,Positive definite completions of partial Hermitian matrices[J],Linear Algebra Appl.58(1984),109-124.
26.Ho,C.W.,& Lee,R.C.T.,Counting clique trees and computing perfect elimination schemes in parallel[J],Inform.Process.lett.31(1989),61-68.
27.Kloks,T.,& Spinrad,J.,On treewidth and minimum fill-in of asteroidal triple-free graphs[J],Fraphs Comput.Sci.175(1997),309-335.
28.Kristian,G.O.,& Anders L.M.,Maximal Prime Subgraph Decomposition of Bayesian Networks[J],IEEE Transactions on Systems 32(2002),21-31.
29.Kumar,P.S.,& Madhavan,C.E.V.,Minimal vertex separators of chordal graphs[J],Discrete.Appl.Math.89(1998),155-168.
30.Lauritzen,S.L.,Graphical Models,Oxford:Clarendon Press,1996.
31.Lauritzen,S.L.,& Sheehan,N.A.,Graphical models for genetic analyses[J],Statistical Sci.18(2003),489-514.
32.Leimer,H.G.,Optimal decomposition by clique separators[J],Discrete Math.113(1993),99-123.
33.Li,H.Z.,& Wang,J.F.,On size of unicycle of hypergraphs[J],Systems Sci.and Systems Engin.9(2000),245-250.
34.Li,H.Z.,& Wang,J.F.,The upper bound of hypergraphs[J],Discrete Math.254(2002),555-564.
35.McKee,T.A.,& McMorris,F.R.,Topics in Intersection Graph Theory,Philadelphia:SIAM,(1978).
36.McKee,T.A.,How chordal graphs work[J],Bull.Inst.Combin.Appl.9(1993),27-39.
37.Olesen,K.G.,& Madsen,A.L.,Maximal prime subgraph decomposition of Bayesian networks[J],IEEE Trans.Syst.Man Cybern.B 32(2002),21-31.
38.Parra A,& Scheffler,P.,Characterizations and algorithmic applications of chordal graph embeddings[J],Discrete Appl.Math.79(1997),171-188.
39.Rose,D.J.,A graph-theoretic study of the numerical solusion of sparse positive definite systems of linear equations,New York:Academic Press,1972.
40.Rose,D.J.,Triangulated graphs and the elimination process[J],Math.Anal.Appl.32(1970),597-609.
41.Rose,D.J.,Tarjan,R.E.,& Leuker,G.S.,Algorithmic aspects of vertex elimination in graphs[J],SIAM.J.Comput.5(1976),266-283.
42.Tarjan,R.E.,Decomposition by clique separators[J],Discrete Math.55(1985),221-232.
43.Tarjan,R.E.,& Yannakakis,M.,Simple linear-time algorithms to test chordality of graphs,test acyclicity of hypergraphs,and selectively reduce acyclic hypergraphs[J],SIAM J.Comput.13(1984),566-579.
44.Lee,T.T.,The Euler number of cyclomatic number of hypergraphs [J],Southeast Asian Bulletin of mathematics 21(1997),113-138.
45.Waki,H.,Kim,S.,Kojima,M.,& Muramatsu,M.,Sums of squres and semidefinite program relaxations for polynomial optimization problems with structures sparsity[J],SIAM J.Optim.17(2006),218-242.
46.Walter,J.R.,Pepresentations of chordal graphs as subtrees of a tree [J],J.Graph Theory 2(1978),265-267.
47.Wang,J.F.,The Information Hypergraph Theory,Beijing:Science Press,2008.
48.Wang,J.F.,On the axiom constituting foundation of hypergraph theorem[J],Acta Mathematicae Applicatae Sinica.English Series 21(2005),495-498.
49.Wang,J.F.,& Lee,T.T.,An invarant for hypergraphs[J],Acta Math.Appl.Sinica 12(1996),113-120.
50.Wang,X.F.,& Guo,J.H.,Junction trees of general graphs[J],Frontiers of Math.in China 3(2008),399-413.
51.Whittaker,J.,Graphical Models in Applied Multivariate Statistics,New York:Wiley,1990.
2.Beeri,C.,Fagin,R.,Maier,D.,& Yannakakis,M.,On the desirability of acyclic database systems[J],J.Assoc.Comput.Mach.30(1983),479-513.
3.Berge,C.,Graphs and Hypergraphs,Amsterdam:North-Holland Publishing Company,1973.
4.Bernstein,P.A.,& Goodman,N.,Power of natural semjoins[J],SIAM J.Comput.10(1981),751-771.
5.Berry,A.,D(?)sarticulation d'un graphe,Ph.D.Thesis,LIRMM,Montpellier,France,1998.6.Berry,A.,Bodat,J.P.,& Cogis,O.,Generating all the minimal separators of a graph[J],Internat.J.Foundations Comput.Sci.11(2000),397-404.
7.Bouchitt(?),V.,& Todinca,I.,Treewidth and minimum fill in:grouping the minimum separators[J],SIAM J.Comput.31(2001),212-232.
8.Brandst(a|¨)dt,A.,Le,V.B.,& Spinrad,J.P.,Graph classes:A Survey,Philadelphia:SIAM,1999.
9.Buneman,P.,A characterisation of rigid circuit graphs[J],Discrete Math.9(1974),205-212.
10.Chandran,L.S.,Ibarra,F.,Ruskey,F.,& Sawada,J.,Generating and characterizing the perfect elimination orderings of a chordal graph[J],Theoret.Comput.Sci.307(2003),303-317.
11.Chung,F.R.K.,& Mumford,D.,Chordal completions of planar graphs[J],J.Symbolic Comput.31(1994),96-106.
12.Dacar,F.,The cyclicity of a hypergraph[J],Discrete Math.182(1998),53-67.
13.Darroch,J.N.,Lauritzen,S.L.,& Speed,T.P,Markov field and loglinear intersection models for contingency tables[J],Ann.Statist.8(1980),522-539.
14.de Campos,L.M.,Characterizations of decomposable dependency models[J],Artificial Intelligence Research,5(1996),289-300.
15.Diestel,R.,Graph Decomposition-A Study in Infinite Graph Theory,Oxford:Clarendon Press,1990.
16.Dirac,G.A.,On rigid circuit graphs[J],Abhandlungen Mathematis- ches Semonar Hamburg.25(1961),71-76.
17.Dobra,A.,Markov bases for decomposable graphical models[J],Bernoulli 9(2003),1093-1108.
18.Jensen,F.V.,Bayesian Networks and Decision Graphs,New York:Springer,2002.
19.Fulkerson,D.R.,& Gross,O.A.,Incidence matrices and interval graphs[J],Pacific J.Math.15(1965),835-855.
20.Fukuda,M.,Murota,K.,& Nakata,K.,Exploiting sparsity in semidefinite programming via matrix completion[J],SIAM J.Optim.11(2000),647-674.
21.Gavril,F.,The intersection graphs of subtrees in trees are exactly the chordal graphs[J],J.Combin.Theoy Ser.B 16(1974),47-56.
22.Gilmore,P.C.,& Hoffman,A.J.,A characterization of comparability graphs and of interval graphs,Canad.J.Math.16(1964),539-548.
23.Golumbic,M.C.,Algorithmic Graph Theory and Perfect Graphs,New York:Academic Press,1980.
24.Goodman,N.,& Shmueli,O.,Syntactic characterization of tree database schemes[J],Assoc.Comput.Mach.30(1983),767-786.
25.Grone,C.R.,Johnson,C.R.,Sá E.M.,& Wolkowicz,H.,Positive definite completions of partial Hermitian matrices[J],Linear Algebra Appl.58(1984),109-124.
26.Ho,C.W.,& Lee,R.C.T.,Counting clique trees and computing perfect elimination schemes in parallel[J],Inform.Process.lett.31(1989),61-68.
27.Kloks,T.,& Spinrad,J.,On treewidth and minimum fill-in of asteroidal triple-free graphs[J],Fraphs Comput.Sci.175(1997),309-335.
28.Kristian,G.O.,& Anders L.M.,Maximal Prime Subgraph Decomposition of Bayesian Networks[J],IEEE Transactions on Systems 32(2002),21-31.
29.Kumar,P.S.,& Madhavan,C.E.V.,Minimal vertex separators of chordal graphs[J],Discrete.Appl.Math.89(1998),155-168.
30.Lauritzen,S.L.,Graphical Models,Oxford:Clarendon Press,1996.
31.Lauritzen,S.L.,& Sheehan,N.A.,Graphical models for genetic analyses[J],Statistical Sci.18(2003),489-514.
32.Leimer,H.G.,Optimal decomposition by clique separators[J],Discrete Math.113(1993),99-123.
33.Li,H.Z.,& Wang,J.F.,On size of unicycle of hypergraphs[J],Systems Sci.and Systems Engin.9(2000),245-250.
34.Li,H.Z.,& Wang,J.F.,The upper bound of hypergraphs[J],Discrete Math.254(2002),555-564.
35.McKee,T.A.,& McMorris,F.R.,Topics in Intersection Graph Theory,Philadelphia:SIAM,(1978).
36.McKee,T.A.,How chordal graphs work[J],Bull.Inst.Combin.Appl.9(1993),27-39.
37.Olesen,K.G.,& Madsen,A.L.,Maximal prime subgraph decomposition of Bayesian networks[J],IEEE Trans.Syst.Man Cybern.B 32(2002),21-31.
38.Parra A,& Scheffler,P.,Characterizations and algorithmic applications of chordal graph embeddings[J],Discrete Appl.Math.79(1997),171-188.
39.Rose,D.J.,A graph-theoretic study of the numerical solusion of sparse positive definite systems of linear equations,New York:Academic Press,1972.
40.Rose,D.J.,Triangulated graphs and the elimination process[J],Math.Anal.Appl.32(1970),597-609.
41.Rose,D.J.,Tarjan,R.E.,& Leuker,G.S.,Algorithmic aspects of vertex elimination in graphs[J],SIAM.J.Comput.5(1976),266-283.
42.Tarjan,R.E.,Decomposition by clique separators[J],Discrete Math.55(1985),221-232.
43.Tarjan,R.E.,& Yannakakis,M.,Simple linear-time algorithms to test chordality of graphs,test acyclicity of hypergraphs,and selectively reduce acyclic hypergraphs[J],SIAM J.Comput.13(1984),566-579.
44.Lee,T.T.,The Euler number of cyclomatic number of hypergraphs [J],Southeast Asian Bulletin of mathematics 21(1997),113-138.
45.Waki,H.,Kim,S.,Kojima,M.,& Muramatsu,M.,Sums of squres and semidefinite program relaxations for polynomial optimization problems with structures sparsity[J],SIAM J.Optim.17(2006),218-242.
46.Walter,J.R.,Pepresentations of chordal graphs as subtrees of a tree [J],J.Graph Theory 2(1978),265-267.
47.Wang,J.F.,The Information Hypergraph Theory,Beijing:Science Press,2008.
48.Wang,J.F.,On the axiom constituting foundation of hypergraph theorem[J],Acta Mathematicae Applicatae Sinica.English Series 21(2005),495-498.
49.Wang,J.F.,& Lee,T.T.,An invarant for hypergraphs[J],Acta Math.Appl.Sinica 12(1996),113-120.
50.Wang,X.F.,& Guo,J.H.,Junction trees of general graphs[J],Frontiers of Math.in China 3(2008),399-413.
51.Whittaker,J.,Graphical Models in Applied Multivariate Statistics,New York:Wiley,1990.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |