entropía de grafos

En teoría de la información , la entropía de grafos es una medida de la tasa de información alcanzable al comunicar símbolos a través de un canal en el que ciertos pares de valores pueden confundirse. ^{[ 1 ]} Esta medida, introducida por primera vez por Körner en la década de 1970, ^{[ 2 ] [ 3 ]} también ha demostrado ser útil en otros ámbitos, incluida la combinatoria. ^{[ 4 ]}

Dejar${\displaystyle G=(V,E)}$sea ​​un grafo no dirigido . La entropía del grafo de${\displaystyle G}$, denotado${\displaystyle H(G)}$se define como

${\displaystyle H(G)=\min _{X,Y}I(X;Y)}$

dónde${\displaystyle X}$se elige uniformemente de${\displaystyle V}$,${\displaystyle Y}$abarca sobre conjuntos independientes de G, la distribución conjunta de${\displaystyle X}$y${\displaystyle Y}$es tal que${\displaystyle X\in Y}$con probabilidad uno, y${\displaystyle I(X;Y)}$es la información mutua de${\displaystyle X}$y${\displaystyle Y}$. ^{[ 5 ]}

Es decir, si dejamos${\displaystyle {\mathcal {I}}}$denotemos los conjuntos de vértices independientes en${\displaystyle G}$, deseamos encontrar la distribución conjunta${\displaystyle X,Y}$en${\displaystyle V\times {\mathcal {I}}}$con la información mutua más baja tal que (i) la distribución marginal del primer término es uniforme y (ii) en muestras de la distribución, el segundo término contiene al primer término casi con seguridad. La información mutua de${\displaystyle X}$y${\displaystyle Y}$entonces se llama la entropía de${\displaystyle G}$.

• Monotonicidad. Si${\displaystyle G_{1}}$es un subgrafo de${\displaystyle G_{2}}$en el mismo conjunto de vértices, entonces${\displaystyle H(G_{1})\leq H(G_{2})}$.
• Subaditividad. Dados dos gráficos${\displaystyle G_{1}=(V,E_{1})}$y${\displaystyle G_{2}=(V,E_{2})}$en el mismo conjunto de vértices, la unión del grafo${\displaystyle G_{1}\cup G_{2}=(V,E_{1}\cup E_{2})}$Satisface${\displaystyle H(G_{1}\cup G_{2})\leq H(G_{1})+H(G_{2})}$.
• Media aritmética de uniones disjuntas. Sea${\displaystyle G_{1},G_{2},\cdots ,G_{k}}$sea ​​una secuencia de grafos sobre conjuntos disjuntos de vértices, con${\displaystyle n_{1},n_{2},\cdots ,n_{k}}$vértices, respectivamente.${\displaystyle H(G_{1}\cup G_{2}\cup \cdots G_{k})={\tfrac {1}{\sum _{i=1}^{k}n_{i}}}\sum _{i=1}^{k}{n_{i}H(G_{i})}}$.

Además, existen fórmulas sencillas para ciertas familias de clases de gráficos.

• Los grafos k-partitos equilibrados completos tienen entropía.${\displaystyle \log _{2}k}$. En particular,
  • Los grafos sin aristas tienen entropía.${\displaystyle 0}$.
  • Gráficos completos sobre${\displaystyle n}$Los vértices tienen entropía.${\displaystyle \log _{2}n}$.
  • Los grafos bipartitos equilibrados completos tienen entropía.${\displaystyle 1}$.
• Grafos bipartitos completos con${\displaystyle n}$vértices en una partición y${\displaystyle m}$en el otro tienen entropía${\displaystyle H\left({\frac {n}{m+n}}\right)}$, dónde${\displaystyle H}$es la función de entropía binaria .

Aquí, utilizamos propiedades de la entropía de grafos para proporcionar una prueba simple de que un grafo completo${\displaystyle G}$en${\displaystyle n}$Los vértices no pueden expresarse como la unión de menos de${\displaystyle \log _{2}n}$grafos bipartitos.

Demostración Por monotonicidad, ningún grafo bipartito puede tener una entropía de grafo mayor que la de un grafo bipartito completo, que está acotada por${\displaystyle 1}$. Por lo tanto, por subaditividad, la unión de${\displaystyle k}$Los grafos bipartitos no pueden tener una entropía mayor que${\displaystyle k}$Ahora dejemos...${\displaystyle G=(V,E)}$ser un gráfico completo en${\displaystyle n}$vértices. Por las propiedades enumeradas anteriormente,${\displaystyle H(G)=\log _{2}n}$Por lo tanto, la unión de menos de${\displaystyle \log _{2}n}$Los grafos bipartitos no pueden tener la misma entropía que${\displaystyle G}$, entonces${\displaystyle G}$no puede expresarse como tal unión.${\displaystyle \blacksquare }$

• Matthias Dehmer; Frank Emmert-Streib; Zengqiang Chen; Xueliang Li; Yongtang Shi (25 de julio de 2016). Fundamentos matemáticos y aplicaciones de la entropía de grafos . Wiley. ISBN 978-3-527-69325-2.