In [[information theory]], the '''graph entropy''' is a measure of the information rate achievable by communicating symbols over a channel in which certain pairs of values may be confused.<ref name="DehmerMowshowitz2013">{{cite book|author1=Matthias Dehmer|author2=Abbe Mowshowitz|author3=Frank Emmert-Streib|title=Advances in Network Complexity|url=https://books.google.com/books?id=fHxARaCPTKwC&pg=PT186|date=21 June 2013|publisher=John Wiley & Sons|isbn=978-3-527-67048-2|pages=186–}}</ref> This measure, first introduced by Körner in the 1970s,,<ref>{{cite journal|last=Körner|first=János||date=1973|title=Coding of an information source having ambiguous alphabet and the entropy of graphs.|journal=6th Prague conference on information theory|pages= 411–425}}</ref><ref name="LoboKasparis2008">{{cite book|author1=Niels da Vitoria Lobo|author2=Takis Kasparis|author3=Michael Georgiopoulos|title=Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, SSPR & SPR 2008, Orlando, USA, December 4-6, 2008. Proceedings|url=https://books.google.com/books?id=DWZc9Ti_vBwC&pg=PA237|date=24 November 2008|publisher=Springer Science & Business Media|isbn=978-3-540-89688-3|pages=237–}}</ref> has since also proven itself useful in other settings, including combinatorics.<ref name="BouchonSaitta1988">{{cite book|author1=Bernadette Bouchon|author2=Lorenza Saitta|author3=Ronald R. Yager|title=Uncertainty and Intelligent Systems: 2nd International Conference on Information Processing and Management of Uncertainty in Knowledge Based Systems IPMU '88. Urbino, Italy, July 4-7, 1988. Proceedings|url=https://books.google.com/books?id=V5-6G433s_wC&pg=PA112|date=8 June 1988|publisher=Springer Science & Business Media|isbn=978-3-540-19402-6|pages=112–}}</ref>
==Definition==
Line 6:
::<math>H(G) = \min_{X,Y} I(X ; Y)</math>
where <math>X</math> is chosen [[Discrete uniform distribution|uniformly]] from <math>V</math>, <math>Y</math> isranges anover [[Independent set (graph theory)|independent setsets]] inof G, the joint distribution of <math>X</math> and <math>Y</math> is such that <math>X\in Y</math> with probability one, and <math>I(X ; Y)</math> is the [[mutual information]] of <math>X</math> and <math>Y</math> <ref>G. Simonyi, "Perfect graphs and graph entropy. An updated survey," Perfect Graphs, John Wiley and Sons (2001) pp. 293-328, Definition 2”</ref>
