Capacidad de Shannon de un gráfico

En teoría de grafos , la capacidad de Shannon de un grafo es un invariante definido a partir del número de conjuntos independientes de productos fuertes de grafos . Recibe su nombre del matemático estadounidense Claude Shannon . Mide la capacidad de Shannon de un canal de comunicaciones definido a partir del grafo y está limitada superiormente por el número de Lovász , que puede calcularse en tiempo polinomial . Sin embargo, la complejidad computacional de la capacidad de Shannon en sí misma sigue siendo desconocida.

La capacidad de Shannon modela la cantidad de información que se puede transmitir a través de un canal de comunicación ruidoso en el que ciertos valores de señal pueden confundirse entre sí. En esta aplicación, el gráfico de confusión ^{[ 1 ]} o gráfico de confusabilidad describe los pares de valores que pueden confundirse. Por ejemplo, supongamos que un canal de comunicación tiene cinco valores de señal discretos, cualquiera de los cuales puede transmitirse en un solo paso de tiempo. Estos valores pueden modelarse matemáticamente como los cinco números 0, 1, 2, 3 o 4 en aritmética modular módulo  5. Sin embargo, supongamos que cuando un valor${\displaystyle i}$se envía a través del canal, el valor que se recibe es${\displaystyle i+\xi }$(módulo 5) donde${\displaystyle \xi }$representa el ruido en el canal y puede ser cualquier número real en el intervalo abierto de −1 a 1. Por lo tanto, si el receptor recibe un valor como 3.6, es imposible determinar si se transmitió originalmente como un  3 o como un  4; los dos valores 3 y 4 pueden confundirse entre sí. Esta situación se puede modelar mediante un gráfico, un ciclo.${\displaystyle C_{5}}$de longitud  5, en la que los vértices corresponden a los cinco valores que se pueden transmitir y las aristas del grafo representan valores que se pueden confundir entre sí.

Para este ejemplo, es posible elegir dos valores que se puedan transmitir en cada paso de tiempo sin ambigüedad, por ejemplo, los valores 1 y 3. Estos valores están lo suficientemente separados como para que no se puedan confundir entre sí: cuando el receptor recibe un valor${\displaystyle x}$entre 0 y 2, se puede deducir que el valor que se envió debe haber sido 1, y cuando el destinatario recibe un valor${\displaystyle x}$entre 2 y 4, se puede deducir que el valor que se envió debe haber sido 3. De esta manera, en${\displaystyle n}$pasos de comunicación, el remitente puede comunicarse hasta${\displaystyle 2^{n}}$mensajes diferentes. Dos es el número máximo de valores que el receptor puede distinguir entre sí: cada subconjunto de tres o más valores (0, 1, 2, 3, 4) incluye al menos un par que puede confundirse entre sí. Aunque el canal dispone de cinco valores que pueden enviarse por intervalo de tiempo, en la práctica solo dos de ellos pueden utilizarse con este esquema de codificación.

Sin embargo, los esquemas de codificación más complejos permiten enviar una mayor cantidad de información a través del mismo canal, mediante el uso de palabras clave de longitud mayor que uno. Por ejemplo, supongamos que en dos pasos consecutivos el remitente transmite una de las cinco palabras clave "11", "23", "35", "54" o "42". (Aquí, las comillas indican que estas palabras deben interpretarse como cadenas de símbolos, no como números decimales). Cada par de estas palabras clave incluye al menos una posición donde sus valores difieren en dos o más módulos  5; por ejemplo, "11" y "23" difieren en dos en su segunda posición, mientras que "23" y "42" difieren en dos en su primera posición. Por lo tanto, un receptor de una de estas palabras clave siempre podrá determinar inequívocamente cuál se envió: no se pueden confundir dos de estas palabras clave entre sí. Al utilizar este método, en${\displaystyle n}$pasos de comunicación, el remitente puede comunicarse hasta${\displaystyle 5^{n/2}}$mensajes, significativamente más que los${\displaystyle 2^{n}}$que podrían transmitirse con el código más simple de un dígito. El número efectivo de valores que se pueden transmitir por unidad de paso de tiempo es${\textstyle (5^{n/2})^{1/n}={\sqrt {5}}}$En términos de teoría de grafos, esto significa que la capacidad de Shannon del ciclo de 5 es al menos${\displaystyle {\sqrt {5}}}$Como demostró Lovász (1979) , este límite es estricto: no es posible encontrar un sistema de palabras clave más complejo que permita enviar aún más mensajes diferentes en el mismo lapso de tiempo, por lo que la capacidad de Shannon del ciclo de 5 es exactamente${\displaystyle {\sqrt {5}}}$.

Si un gráfico${\displaystyle G}$representa un conjunto de símbolos y los pares de símbolos que pueden confundirse entre sí, entonces un subconjunto${\displaystyle S}$de símbolos evita todos los pares confusos si y solo si${\displaystyle S}$es un conjunto independiente en el grafo, un subconjunto de vértices que no incluye ambos extremos de ninguna arista. El tamaño máximo posible de un subconjunto de los símbolos que se pueden distinguir entre sí es el número de independencia.${\displaystyle \alpha (G)}$del gráfico, el tamaño de su conjunto independiente máximo . Por ejemplo, '${\displaystyle \alpha (C_{5})=2}$: el ciclo de 5 vértices tiene conjuntos independientes de dos vértices, pero no mayores.

Para palabras clave de mayor longitud, se pueden usar conjuntos independientes en grafos más grandes para describir los conjuntos de palabras clave que se pueden transmitir sin confusión. Por ejemplo, para el mismo ejemplo de cinco símbolos cuyo grafo de confusión es${\displaystyle C_{5}}$Hay 25 cadenas de longitud dos que se pueden usar en un esquema de codificación de longitud 2. Estas cadenas se pueden representar mediante los vértices de un grafo con 25 vértices. En este grafo, cada vértice tiene ocho vecinos, las ocho cadenas con las que puede confundirse. Un subconjunto de cadenas de longitud dos forma un código sin posibilidad de confusión si y solo si corresponde a un conjunto independiente de este grafo. El conjunto de palabras clave {"11", "23", "35", "54", "42"} forma uno de estos conjuntos independientes, de tamaño máximo.

Si${\displaystyle G}$es un gráfico que representa las señales y los pares confusibles de un canal, entonces el gráfico que representa las palabras clave de longitud dos y sus pares confusibles es${\displaystyle G\boxtimes G}$donde el símbolo${\displaystyle \boxtimes }$representa el producto fuerte de grafos . Este es un grafo que tiene un vértice para cada par.${\displaystyle (u,v)}$de un vértice en el primer argumento del producto y un vértice en el segundo argumento del producto. Dos pares distintos${\displaystyle (u_{1},v_{1})}$y${\displaystyle (u_{2},v_{2})}$son adyacentes en el producto fuerte si y solo si${\displaystyle u_{1}}$y${\displaystyle u_{2}}$son idénticos o adyacentes, y${\displaystyle v_{1}}$y${\displaystyle v_{2}}$son idénticas o adyacentes. De manera más general, las palabras clave de longitud ${\displaystyle k}$puede representarse mediante el gráfico${\displaystyle G_{k}}$, el${\displaystyle k}$-producto resistente de pliegues${\displaystyle G}$con sí mismo, y el número máximo de palabras clave de esta longitud que se pueden transmitir sin confusión viene dado por el número de independencia.${\displaystyle \alpha (G_{k})}$. El número efectivo de señales transmitidas por unidad de paso de tiempo es el${\displaystyle k}$raíz enésima de este número,${\displaystyle \alpha (G_{k})^{1/k}}$.

Utilizando estos conceptos, la capacidad de Shannon puede definirse como

${\displaystyle \Theta (G)=\sup _{k}{\sqrt[{k}]{\alpha (G_{k})}}=\lim _{k\rightarrow \infty }{\sqrt[{k}]{\alpha (G_{k})}},}$

el límite (como${\displaystyle k}$se vuelve arbitrariamente grande) del número efectivo de señales por paso de tiempo de códigos libres de confusión arbitrariamente largos.

Se desconoce la complejidad computacional de la capacidad de Shannon, e incluso el valor de la capacidad de Shannon para ciertos grafos pequeños como${\displaystyle C_{7}}$(un grafo cíclico de siete vértices) sigue siendo desconocido. ^{[ 2 ] [ 3 ]}

Un enfoque natural para este problema sería calcular un número finito de potencias del grafo dado.${\displaystyle G}$, encontrar sus números de independencia e inferir de estos números alguna información sobre el comportamiento límite de la secuencia a partir de la cual se define la capacidad de Shannon. Sin embargo (incluso ignorando la dificultad computacional de calcular los números de independencia de estos grafos, un problema NP-difícil ) el comportamiento impredecible de la secuencia de números de independencia de potencias de${\displaystyle G}$implica que este enfoque no puede utilizarse para aproximar con precisión la capacidad de Shannon. ^{[ 4 ]}

En parte debido a que la capacidad de Shannon es difícil de calcular, los investigadores han buscado otros invariantes de grafos que sean fáciles de calcular y que proporcionen límites para la capacidad de Shannon.