Graph entropy: Difference between revisions

Revision as of 22:52, 21 September 2017

Revision as of 22:48, 26 December 2017

Line 16:

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

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

* Complete balanced [[Multipartite graph|k-partite graphs]] have entropy <math>\lg rk</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]].