超图理论
图论的分支
超图理论(Hypergraph )图论的分支。超图是有限集合的子集系统,是最一般的离散结构,在信息科学生命科学等领域有着广泛的应用。由于实际的需要,信息科学家提出了无圈超图的概念,他们的定义不同于传统定义,二者相差甚远。
最新进展
2002年,我们国家在超图理论研究中取得了突破进展。王建方和李海珠得到了严格高维连通匀齐无圈超图的技术公式。该公式涵盖了图论中关于树的Cayley公式。Cayley公式是图论中经典公式之一,是Springer出版社1998年出版的“Proofs From The Book”一书中第22章的中心定理,书中称Cayley公式是“计数组合中最漂亮的公式之一”。该书是Paul Erdos生前建议写的一本书。Paul Erdos被誉为二十世纪最伟大的数学家之一。该书的前言说“P.Erdos喜欢读这本书,在这本书中上帝保存着数学定理的完美证明”。这就在理论上证明了信息科学家给出的无圈超图的定义是科学的、合理的。王建方和李东曾于1999年给出了超图实图空间维数的公式,他涵盖了图论中著名的Euler公式。在此基础上,王建方和李海珠2002年证明了当n充分大时,n阶(n-2)-匀齐超图,其实圈空间维数的最大值不在完全超图上达到。这是超图不同于通常图的一个重要特征。王建方和李海珠还给出了无圈超图的系列特征和有圈超图的系列特征。王建方和李海珠得到了无圈超图的边数公式。该公式也显示了信息科学家关于无圈超图定义的科学性。该公式在算法复杂性理论研究中会起重要作用。单志龙和柳伯濂提到严格非匀称线性超树的计数式。
参考资料
最新修订时间:2023-05-18 21:40
目录
概述
参考资料