Graph entropy: Difference between revisions

Revision as of 02:50, 2 July 2018

Revision as of 15:28, 9 March 2019

Line 15:

Additionally, simple formulas exist for certain families classes of graphs.

* Edge-less graphs have entropy <math>0</math>.

* [[Complete graph]]s on <math>n</math> vertices have entropy <math>\lglog_2 n</math>, where <math>\lglog_2</math> is the [[binary logarithm]].

* Complete balanced [[Multipartite graph|k-partite graphs]] have entropy <math>\lg k</math> where <math>lg</math> is the binary logarithm. In particular, complete balanced [[bipartite graphs]] have entropy <math>1</math>.

* Complete [[bipartite graphs]] with <math>n</math> vertices in one partition and <math>m</math> in the other have entropy <math>H\left(\frac{n}{m+n}\right)</math>, where <math>H</math> is the [[binary entropy function]].