Pojemność grafu Shannona

W teorii grafów pojemność grafu Shannona jest niezmiennikiem grafu zdefiniowanym na podstawie liczby niezależnych zestawów silnych iloczynów grafu . Został nazwany na cześć amerykańskiego matematyka Claude'a Shannona . Mierzy przepustowość Shannona kanału komunikacyjnego określonego na podstawie wykresu i jest ograniczona górną liczbą Lovásza , którą można obliczyć w czasie wielomianowym . Jednak złożoność obliczeniowa samej pojemności Shannona pozostaje nieznana.

Grafowe modele kanałów komunikacyjnych

Cykl pięciu wierzchołków, modelujący zestaw pięciu wartości, które mogą być przesyłane przez hałaśliwy kanał komunikacyjny oraz pary wartości, które można ze sobą pomylić

Pojemność Shannona modeluje ilość informacji, które mogą być przesyłane przez zaszumiony kanał komunikacyjny, w którym pewne wartości sygnału mogą być ze sobą mylone. W tej aplikacji wykres pomyłki lub wykres pomyłki opisuje pary wartości, które można pomylić. Załóżmy na przykład, że kanał komunikacyjny ma pięć dyskretnych wartości sygnału, z których każda może być transmitowana w pojedynczym kroku czasowym. Te wartości można modelować matematycznie jako pięć liczb 0, 1, 2, 3 lub 4 w modułowej arytmetyce modulo 5. Załóżmy jednak, że gdy wartość ${\ displaystyle i}$$jest$ wysyłany przez kanał, odbierana wartość to $)$ gdzie reprezentuje na kanale i może być liczba rzeczywista w przedziale otwartym od -1 do 1. Tak więc, jeśli odbiorca otrzyma wartość taką jak 3,6, nie można ustalić, czy pierwotnie została przesłana jako 3, czy jako 4; dwie wartości 3 i 4 można ze sobą pomylić. Tę sytuację można modelować za pomocą wykresu, cyklu ${\ displaystyle C_ {5}}$ o długości 5, w którym wierzchołki odpowiadają pięciu wartościom, które można przesłać, a krawędzie grafu reprezentują wartości, które można ze sobą pomylić.

W tym przykładzie możliwe jest wybranie dwóch wartości, które mogą być przesyłane w każdym kroku czasowym bez dwuznaczności, na przykład wartości 1 i 3. Wartości te są na tyle od siebie oddalone, że nie można ich pomylić ze sobą: kiedy odbiorca otrzyma wartość między 0 a 2, może wywnioskować, że wysłana wartość musiała wynosić 1, a gdy odbiorca otrzyma wartość między $2$ a 4, może $displaystyle x}$ wywnioskować, że przesłana wartość musiała wynosić 3. W ten sposób w ${\ displaystyle n}$ etapów komunikacji, nadawca może przekazać do ${\ displaystyle 2 ^ {n}}$ różnych wiadomości. Dwa to maksymalna liczba wartości, które odbiorca może odróżnić od siebie: każdy podzbiór trzech lub więcej wartości 0, 1, 2, 3, 4 zawiera co najmniej jedną parę, które można ze sobą pomylić. Chociaż kanał ma pięć wartości, które mogą być wysyłane na krok czasowy, w rzeczywistości tylko dwie z nich mogą być użyte w tym schemacie kodowania.

Jednak bardziej skomplikowane schematy kodowania umożliwiają przesyłanie większej ilości informacji tym samym kanałem przy użyciu słów kodowych o długości większej niż jeden. Załóżmy na przykład, że w dwóch kolejnych krokach nadawca przesyła jedno z pięciu słów kodowych „11”, „23”, „35”, „54” ​​lub „42”. (Tutaj cudzysłowy wskazują, że słowa te należy interpretować jako ciągi znaków symboli, a nie liczb dziesiętnych.) Każda para tych słów kodowych zawiera co najmniej jedną pozycję, w której jej wartości różnią się o dwa lub więcej modulo 5; na przykład „11” i „23” różnią się o dwa na swojej drugiej pozycji, podczas gdy „23” i „42” różnią się o dwa na swojej pierwszej pozycji. Dlatego odbiorca jednego z tych słów kodowych zawsze będzie mógł jednoznacznie określić, które z nich zostało wysłane: żadne dwa z tych słów kodowych nie mogą się ze sobą pomylić. Korzystając z tej metody, w $komunikacji$ nadawca może komunikować się do ${\ Displaystyle 5 ^ {n/2}}$$,$ znacznie więcej niż te które można przesłać za pomocą prostszego jednocyfrowego kodu. Efektywna liczba wartości, które można przesłać na jednostkę czasu, wynosi ${\ textstyle (5 ^ {n/2}) ^ {1/n} = {\ sqrt {5} }}$ . Z punktu widzenia teorii grafów oznacza to, że pojemność Shannona w 5-cyklu wynosi co najmniej ${\ displaystyle {\ sqrt {5}}}$ . Jak Lovász (1979) pokazał, że ta granica jest ścisła: nie jest możliwe znalezienie bardziej skomplikowanego systemu słów kodowych, który pozwala na wysłanie jeszcze większej liczby różnych wiadomości w tym samym czasie, więc pojemność Shannona 5-cyklu wynosi dokładnie 5 $\ styl wyświetlania {\ sqrt {5}}}$ .

Stosunek do zbiorów niezależnych

Jeśli wykres przedstawia zestaw symboli $S}$ pary symboli, które można ze sobą pomylić, to podzbiór symboli pozwala uniknąć wszystkich mylących par wtedy i tylko wtedy, gdy ${$$S}$$displaystyle$ jest niezależnym zbiorem grafu, podzbiorem wierzchołków, który nie zawiera obu punktów końcowych żadnej krawędzi. Maksymalny możliwy rozmiar podzbioru symboli, które można od siebie odróżnić, to liczba niezależności ${\ displaystyle \ alpha (G)}$ wykresu, rozmiar jego maksymalnego niezależnego zestawu . Na przykład ' ${\ Displaystyle \ alpha (C_ {5}) = 2}$ : cykl 5 ma niezależne zestawy dwóch wierzchołków, ale nie większe.

W przypadku słów kodowych o większej długości można użyć niezależnych zestawów na większych grafach, aby opisać zestawy słów kodowych, które można przesłać bez pomyłek. Na przykład w tym samym przykładzie pięciu symboli, których wykres zamieszania to $,$ istnieje 25 ciągów o długości dwa, których można użyć w schemacie kodowania o długości Ciągi te mogą być reprezentowane przez wierzchołki grafu z 25 wierzchołkami. Na tym grafie każdy wierzchołek ma ośmiu sąsiadów, osiem ciągów, z którymi można go pomylić. Podzbiór ciągów o długości dwóch tworzy kod bez możliwości pomyłki wtedy i tylko wtedy, gdy odpowiada niezależnemu zestawowi tego grafu. Zestaw słów kodowych {"11", "23", "35", "54", "42"} tworzy jeden z tych niezależnych zestawów o maksymalnym rozmiarze.

Jeśli jest wykresem reprezentującym sygnały i mylące $\ displaystyle G \ boxtimes G}$ kanału, to wykresem reprezentującym słowa kodowe o długości dwóch i ich mylące pary jest , $gdzie$ symbol ${\ displaystyle \ boxtimes}$ reprezentuje silny iloczyn wykresów . To jest wykres, który ma wierzchołek dla każdej pary ${\ Displaystyle (u, v)}$ wierzchołka w pierwszym argumencie produktu i wierzchołka w drugim argumencie produktu. ${\ Displaystyle (u_ {1}, v_ {1})}$ i $(u_ {2}, v_ {2})$ u Displaystyle w silnym produkcie wtedy i tylko wtedy, gdy $do$$identyczne$ przylegają i ${\ displaystyle v_ {1}}$ i ${\ displaystyle v_ {2}}$ są identyczne lub sąsiadują ze sobą. Bardziej ogólnie, słowa kodowe o długości ${$ być reprezentowane przez wykres , krotnie silny iloczyn k $displaystyle G}$$z$ samym sobą $\ displaystyle k$ , a maksymalna liczba słów kodowych o tej długości, które można przesłać bez pomyłki, jest określona przez liczbę niezależności ${\ Displaystyle \ alfa (G_ {k})}$ . Efektywna $to$$.$ pierwiastek .

Korzystając z tych pojęć, pojemność Shannona można zdefiniować jako

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

granica (gdy $)$ efektywnej liczby sygnałów na krok czasowy dowolnie długich kodów bez pomyłek.

Złożoność obliczeniowa

Nierozwiązany problem z matematyki :

Jaka jest pojemność Shannona 7-cyklowego?

(więcej nierozwiązanych problemów z matematyki)

Złożoność obliczeniowa pojemności Shannona $.$ nawet wartość pojemności Shannona dla niektórych małych grafów, takich jak ( wykres cyklu siedmiu wierzchołków), pozostaje nieznana

Naturalnym podejściem do tego problemu byłoby obliczenie skończonej liczby potęg danego wykresu , znalezienie ich liczb niezależności i wywnioskowanie z tych liczb pewnych informacji o ograniczającym zachowaniu sekwencji, z której pojemność Shannona jest sol {\ displaystyle $}$ definiuje. Jednak (nawet pomijając trudności obliczeniowe związane z obliczeniem liczb niezależności tych wykresów, NP-trudny ) nieprzewidywalne zachowanie ciągu liczb niezależności potęg ${\ displaystyle G}$ sugeruje, że tego podejścia nie można zastosować do dokładnego przybliżenia pojemności Shannona.

Górne granice

Po części dlatego, że pojemność Shannona jest trudna do obliczenia, badacze szukali innych niezmienników grafu, które są łatwe do obliczenia i które zapewniają granice pojemności Shannona.

Numer Lovásza

Liczba Lovásza ϑ( G ) jest innym niezmiennikiem wykresu, który można obliczyć numerycznie z dużą dokładnością w czasie wielomianowym za pomocą algorytmu opartego na metodzie elipsoidy . Pojemność Shannona grafu G jest ograniczona od dołu przez α( G ), a od góry przez ϑ( G ). W niektórych przypadkach ϑ( G ) i pojemność Shannona pokrywają się; na przykład dla wykresu pięciokąta oba są równe √ 5 . Istnieją jednak inne wykresy, dla których pojemność Shannona i liczba Lovásza różnią się.

Granica Haemersa

Haemers podał kolejną górną granicę pojemności Shannona, która czasami jest lepsza niż granica Lovásza:

${\ Displaystyle \ Theta (G) \ równoważnik R (G) = \ min _ {B} \ operatorname {ranga} (B),}$

gdzie B jest macierzą n × n na pewnym polu , taką, że b _ii ≠ 0 oraz b _ij = 0, jeśli wierzchołki i oraz j nie sąsiadują ze sobą.