En la teoría de la información , la entropía del gráfico es una medida de la velocidad de información que se puede lograr mediante la comunicación de 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] desde entonces también ha demostrado su utilidad en otros entornos, incluida la combinatoria. [4]
Definición
Dejar ser un gráfico no dirigido . La entropía gráfica de, denotado Se define como
dónde se elige uniformemente de, rangos sobre conjuntos independientes de G, la distribución conjunta de y es tal que con probabilidad uno, y es la información mutua de y . [5]
Es decir, si dejamos denotar los conjuntos de vértices independientes en , deseamos encontrar la distribución conjunta en 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 el primer término casi con seguridad. La información mutua de y entonces se llama la entropía de .
Propiedades
- Monotonicidad. Si es un subgrafo de en el mismo conjunto de vértices, entonces .
- Subaditividad. Dados dos gráficos y en el mismo conjunto de vértices, la unión del grafo satisface .
- Media aritmética de uniones disjuntas. Dejar ser una secuencia de gráficos en conjuntos disjuntos de vértices, con vértices, respectivamente. Luego.
Además, existen fórmulas simples para ciertas clases de familias de gráficos.
- Los gráficos sin bordes tienen entropía .
- Gráficos completos en los vértices tienen entropía .
- Los gráficos completos equilibrados de k-partitas tienen entropía. En particular, los gráficos bipartitos balanceados completos tienen entropía.
- Completas grafos bipartitos con vértices en una partición y en el otro tienen entropía , dónde es la función de entropía binaria .
Ejemplo
Aquí, usamos las propiedades de la entropía de la gráfica para proporcionar una prueba simple de que una gráfica completa en Los vértices no se pueden expresar como la unión de menos de gráficos bipartitos.
Prueba Por monotonicidad, ningún gráfico bipartito puede tener una entropía de gráfico mayor que la de un gráfico bipartito completo, que está limitado por. Así, por subaditividad, la unión de Los gráficos bipartitos no pueden tener una entropía mayor que . Ahora deja ser un gráfico completo en vértices. Por las propiedades enumeradas anteriormente,. Por tanto, la unión de menos de Los gráficos bipartitos no pueden tener la misma entropía que , entonces no se puede expresar como tal unión.
Referencias generales
- 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 gráfica . Wiley. ISBN 978-3-527-69325-2.
Notas
- ^ Matthias Dehmer; Abbe Mowshowitz; Frank Emmert-Streib (21 de junio de 2013). Avances en la complejidad de la red . John Wiley e hijos. págs. 186–. ISBN 978-3-527-67048-2.
- ^ Körner, János (1973). "Codificación de una fuente de información con alfabeto ambiguo y entropía de gráficos". 6ª Conferencia de Praga sobre teoría de la información : 411–425.
- ^ Niels da Vitoria Lobo; Takis Kasparis; Michael Georgiopoulos (24 de noviembre de 2008). Reconocimiento de patrones estructurales, sintácticos y estadísticos: Taller internacional conjunto de IAPR, SSPR & SPR 2008, Orlando, EE. UU., 4-6 de diciembre de 2008. Actas . Springer Science & Business Media. págs. 237–. ISBN 978-3-540-89688-3.
- ^ Bernadette Bouchon; Lorenza Saitta; Ronald R. Yager (8 de junio de 1988). Incertidumbre y Sistemas Inteligentes: II Congreso Internacional sobre Procesamiento de la Información y Gestión de la Incertidumbre en Sistemas Basados en Conocimiento IPMU '88. Urbino, Italia, 4-7 de julio de 1988. Actas . Springer Science & Business Media. págs. 112–. ISBN 978-3-540-19402-6.
- ^ G. Simonyi, "Gráficos perfectos y entropía gráfica. Una encuesta actualizada," Gráficos perfectos, John Wiley and Sons (2001) págs. 293-328, Definición 2 "