Capacidad de Shannon de un grafo - Enciclopedia
En la teoría de grafos, la capacidad de Shannon de un grafo es un invariant de grafo definido a partir del número de conjuntos independientes de productos gráficos fuertes. Se llama así en honor al matemático estadounidense Claude Shannon. Mide la capacidad de Shannon de un canal de comunicación definido a partir del grafo y está acotada por el número de Lovász, que se puede calcular en tiempo polinomial. Sin embargo, la complejidad computacional de la capacidad de Shannon en sí sigue siendo desconocida.
Modelos de grafo de canales de comunicación
La capacidad de Shannon modela la cantidad de información que se puede transmitir a través de un canal de comunicación con ruido, en el que ciertos valores de señal pueden confundirse entre sí. En esta aplicación, el grafo de confusión o grafo 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 ser transmitido en un solo paso de tiempo. Estos valores se pueden modelar matemáticamente como los cinco números 0, 1, 2, 3 o 4 en el cálculo modular módulo 5. Sin embargo, supongamos que cuando se envía un valor
i
{\displaystyle i}
a través del canal, el valor recibido es
i
+
ξ
{\displaystyle i+\xi }
(mod 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 destinatario recibe un valor como 3.6, es imposible determinar si originalmente se envió 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 grafo, un ciclo
C
5
{\displaystyle C_{5}}
de longitud 5, en el que los vértices corresponden a los cinco valores que se pueden transmitir y los bordes del grafo representan valores que se pueden confundir entre sí.
Para este ejemplo, es posible elegir dos valores que se pueden transmitir en cada paso de tiempo sin ambigüedad, por ejemplo, los valores 1 y 3. Estos valores están lo suficientemente separados para no poder confundirse entre sí: cuando el destinatario recibe un valor
x
{\displaystyle x}
entre 0 y 2, puede deducir que el valor que se envió debe haber sido 1, y cuando el destinatario recibe un valor
x
{\displaystyle x}
entre 2 y 4, puede deducir que el valor que se envió debe haber sido 3. De esta manera, en
n
{\displaystyle n}
pasos de comunicación, el remitente puede comunicar hasta
2
n
{\displaystyle 2^{n}}
mensajes diferentes. Dos es el número máximo de valores que el destinatario puede distinguir entre sí: cada subconjunto de tres o más de los valores 0, 1, 2, 3, 4 incluye al menos un par que se puede confundir entre sí. A pesar de que el canal tiene cinco valores que se pueden enviar por paso de tiempo, efectivamente solo se pueden usar dos de ellos con este esquema de codificación.
Sin embargo, esquemas de codificación más complicados permiten enviar una mayor cantidad de información a través del mismo canal, utilizando códigos de longitud mayor que uno. Por ejemplo, supongamos que en dos pasos consecutivos el remitente transmite uno de los cinco códigos "11", "23", "35", "54" o "42". (Aquí, las comillas indican que estos palabras deben interpretarse como cadenas de símbolos, no como números decimales). Cada par de estos códigos incluye al menos una posición donde sus valores difieren en dos o más módulo 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 destinatario de uno de estos códigos siempre será capaz de determinar inequívocamente cuál fue enviado: ningún par de estos códigos se puede confundir entre sí. Utilizando este método, en
n
{\displaystyle n}
pasos de comunicación, el remitente puede comunicar hasta
5
n
/
2
{\displaystyle 5^{n/2}}
mensajes, significativamente más de los
2
n
{\displaystyle 2^{n}}
que podrían transmitirse con el código de un solo dígito más simple. El número efectivo de valores que se pueden transmitir por unidad de paso de tiempo es
(
5
n
/
2
)
1
/
n
=
5
{\textstyle (5^{n/2})^{1/n}={\sqrt {5}}}
.
En términos teóricos de grafo, esto significa que la capacidad de Shannon del ciclo de 5 es al menos
5
{\displaystyle {\sqrt {5}}}
. Como Lovász (1979) mostró, este límite es estricto: no es posible encontrar un sistema más complicado de códigos que permita enviar incluso más mensajes diferentes en la misma cantidad de tiempo, por lo que la capacidad de Shannon del ciclo de 5 es exactamente
5
{\displaystyle {\sqrt {5}}}
.
Relación con conjuntos independientes
Si un grafo
G
{\displaystyle G}
representa un conjunto de símbolos y los pares de símbolos que se pueden confundir entre sí, entonces un subconjunto
S
{\displaystyle S}
de símbolos evita todos los pares confusables si y solo si
S
{\displaystyle S}
es un conjunto independiente en el grafo, un subconjunto de vértices que no incluye ambos extremos de cualquier arco. El tamaño máximo posible de un subconjunto de símbolos que se pueden distinguir entre sí es el número de independencia
α
(
G
)
{\displaystyle \alpha (G)}
del grafo, el tamaño de su conjunto independiente máximo. Por ejemplo, '
α
(
C
5
)
=
2
{\displaystyle \alpha (C_{5})=2}
: el ciclo de 5 tiene conjuntos independientes de dos vértices, pero no más grandes.
Para códigos de longer longitudes, se puede usar conjuntos independientes en grafos más grandes para describir los conjuntos de códigos que se pueden transmitir sin confusión. Por ejemplo, para el mismo ejemplo de cinco símbolos cuyo grafo de confusión es
C
5
{\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 por 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 se puede confundir. Un subconjunto de cadenas de longitud dos forma un código sin posible confusión si y solo si corresponde a un conjunto independiente de este grafo. El conjunto de códigos {"11", "23", "35", "54", "42"} forma uno de estos conjuntos independientes, de tamaño máximo.
Si
G
{\displaystyle G}
es un grafo que representa las señales y los pares confusables de un canal, entonces el grafo que representa los códigos de longitud dos y sus pares confusables es
G
⊠
G
{\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
(
u
,
v
)
{\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 distantes
(
u
1
,
v
1
)
{\displaystyle (u_{1},v_{1})}
y
(
u
2
,
v
2
)
{\displaystyle (u_{2},v_{2})}
son adyacentes en el producto fuerte si y solo si
u
1
{\displaystyle u_{1}}
y
u
2
{\displaystyle u_{2}}
son identicos o adyacentes, y
v
1
{\displaystyle v_{1}}
y
v
2
{\displaystyle v_{2}}
son identicos o adyacentes. En términos más generales, los códigos de longitud
k
{\displaystyle k}
se pueden representar por el grafo
G
k
{\displaystyle G_{k}}
, el producto fuerte
k
{\displaystyle k}
veces de
G
{\displaystyle G}
con sí mismo, y el número máximo de códigos de esta longitud que se pueden transmitir sin confusión es dado por el número de independencia
α
(
G
k
)
{\displaystyle \alpha (G_{k})}
. El número efectivo de señales transmitidas por unidad de paso de tiempo es la raíz
k
{\displaystyle k}
-ésima de este número,
α
(
G
k
)
1
/
k
{\displaystyle \alpha (G_{k})^{1/k}}
.
Usando estos conceptos, la capacidad de Shannon puede definirse como
Θ
(
G
)
=
sup
k
α
(
G
k
)
k
=
lim
k
→
∞
α
(
G
k
)
k
,
{\displaystyle \Theta (G)=\sup _{k}{\sqrt[{k}]{\alpha (G_{k})}}=\lim _{k\rightarrow \infty }{\sqrt[{k}]{\alpha (G_{k})}},}
el límite (a medida que
k
{\displaystyle k}
se hace arbitrariamente grande) del número efectivo de señales por paso de tiempo de códigos de confusión sin error arbitrariamente largos.
Complejidad computacional
La complejidad computacional de la capacidad de Shannon es desconocida, y hasta el valor de la capacidad de Shannon para ciertos grafos pequeños como
C
7
{\displaystyle C_{7}}
(un grafo de ciclo de siete vértices) sigue siendo desconocido.
Un enfoque natural para este problema sería calcular un número finito de potencias del grafo dado
G
{\displaystyle G}
, encontrar sus números de independencia e inferir de estos números alguna información sobre el comportamiento limitante de la secuencia de la que 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-hard) el comportamiento impredecible de la secuencia de números de independencia de potencias de
G
{\displaystyle G}
implica que este enfoque no puede utilizarse para approximar de manera precisa la capacidad de Shannon.
Límites superiores
Debido a que la capacidad de Shannon es difícil de calcular, los investigadores han buscado otros invariantes de grafo que sean fáciles de calcular y que proporcionen límites sobre la capacidad de Shannon.
= Número de Lovász =
El número de Lovász ϑ(G) es un invariant de grafo diferente, que se puede calcular numéricamente con alta precisión en tiempo polinomial mediante un algoritmo basado en el método de elipses. La capacidad de Shannon de un grafo G está acotada desde abajo por α(G) y desde arriba por ϑ(G). En algunos casos, ϑ(G) y la capacidad de Shannon coinciden; por ejemplo, para el grafo de un pentágono, ambos son igual a √5. Sin embargo, existen otros grafos para los que la capacidad de Shannon y el número de Lovász difieren.
= Límite de Haemers =
Haemers proporcionó otro límite superior sobre la capacidad de Shannon, que a veces es mejor que el límite de Lovász:
Θ
(
G
)
≤
R
(
G
)
=
min
B
rank
(
B
)
,
{\displaystyle \Theta (G)\leq R(G)=\min _{B}\operatorname {rank} (B),}
donde B es una matriz n × n sobre algún campo, tal que bii ≠ 0 y bij = 0 si los vértices i y j no son adyacentes.
Referencias