Graph Pairs and their Entropies: Modularity Problems
Graph Pairs and their Entropies: Modularity Problems
复制标题
DOI：
10.1007/s004930070022
复制
发表时间：
2000-02
期刊：
影响因子：
1.1
通讯作者：
J. Körner;G. Simonyi
中科院分区：
文献类型：
--
作者：
J. Körner;G. Simonyi
图熵是图的信息论泛函，是图的顶点集上的概率分布。它是关于图并的次可加的，但一般不是次模的。本文给出了图偶的并是完全的情况下，图熵关于每个概率分布的次模性和超模性的充要条件。这类不等式中的等式可以刻画重要的图类，如我们用I.奇萨尔湖洛瓦斯湾马顿和僵尸图的边不交图对的图。
Graph entropy is an information theoretic functional on a graph and a probability distribution on its vertex set. It is sub-additive with respect to graph union but not submodular in general. Here we give necessary and sufficient conditions for submodularity and supermodularity of graph entropy with respect to every probability distribution in case of those couples of graphs whose union is complete. Equality in this kind of inequalities can characterize important classes of graphs as shown by our earlier results with I. Csiszar, L. Lovasz, K. Marton and Zs. Tuza for couples of edge-disjoint graphs.