Shannon kapacitet för en graf

I grafteorin är Shannon -kapaciteten hos en graf en grafinvariant definierad från antalet oberoende uppsättningar av starka grafprodukter . Den är uppkallad efter den amerikanske matematikern Claude Shannon . Den mäter Shannon-kapaciteten för en kommunikationskanal definierad från grafen och är övre gränsad av Lovász-talet , som kan beräknas i polynomtid . Dock beräkningskomplexiteten hos själva Shannon-kapaciteten okänd.

Grafiska modeller av kommunikationskanaler

En cykel med fem vertex, som modellerar en uppsättning av fem värden som kan sändas över en bullrig kommunikationskanal och de värdepar som kan förväxlas med varandra

Shannon-kapaciteten modellerar mängden information som kan sändas över en bullrig kommunikationskanal där vissa signalvärden kan förväxlas med varandra. I den här applikationen förvirringsgrafen eller förväxlingsgrafen de värdepar som kan förväxlas. Anta till exempel att en kommunikationskanal har fem diskreta signalvärden, varav vilket som helst kan sändas i ett enda tidssteg. Dessa värden kan modelleras matematiskt som de fem siffrorna 0, 1, 2, 3 eller 4 i modulär aritmetik modulo 5. Antag dock att när ett värde $i$ skickas över kanalen, är det värde som tas emot är $i+\xi$ (mod 5) där $\xi$ representerar bruset på kanalen och kan vara vilket reellt tal som helst i det öppna intervallet från −1 till 1. Således, om mottagaren tar emot ett värde som 3,6, är det omöjligt att avgöra om det ursprungligen sändes som en 3 eller som en 4; de två värdena 3 och 4 kan förväxlas med varandra. Denna situation kan modelleras av en graf, en cykel $C_{5}$ med längd 5, där hörnen motsvarar de fem värden som kan överföras och kanterna på grafen representerar värden som kan förväxlas med varandra.

För det här exemplet är det möjligt att välja två värden som kan överföras i varje tidssteg utan tvetydighet, till exempel värdena 1 och 3. Dessa värden är tillräckligt långt ifrån varandra för att de inte kan förväxlas med varandra: när mottagaren får ett värde $x$ mellan 0 och 2, den kan härleda att värdet som skickades måste ha varit 1, och när mottagaren får ett värde $x$ mellan 2 och 4 kan den härleda att värdet som skickades måste ha varit 3. På detta sätt, i $n$ kommunikationssteg, kan avsändaren kommunicera upp till $2^{n}$ olika meddelanden. Två är det maximala antalet värden som mottagaren kan skilja från varandra: varje delmängd av tre eller fler av värdena 0, 1, 2, 3, 4 innehåller minst ett par som kan förväxlas med varandra. Även om kanalen har fem värden som kan skickas per tidssteg, kan i praktiken endast två av dem användas med detta kodningsschema.

Mer komplicerade kodningsscheman tillåter emellertid att en större mängd information skickas över samma kanal, genom att använda kodord som är längre än ett. Anta till exempel att avsändaren i två på varandra följande steg sänder ett av de fem kodorden "11", "23", "35", "54" eller "42". (Här anger citattecken att dessa ord ska tolkas som strängar av symboler, inte som decimaltal.) Varje par av dessa kodord inkluderar minst en position där dess värden skiljer sig med två eller flera modulo 5; till exempel skiljer sig "11" och "23" med två i sin andra position, medan "23" och "42" skiljer sig med två i sin första position. Därför kommer en mottagare av ett av dessa kodord alltid att entydigt kunna avgöra vilket som skickades: inga två av dessa kodord kan förväxlas med varandra. Genom att använda denna metod, i $n$ kommunikationssteg, kan avsändaren kommunicera upp till $5^{n/2}$ meddelanden, betydligt fler än de $2^ {n}$ som skulle kunna överföras med den enklare ensiffriga koden. Det effektiva antalet värden som kan överföras per tidsenhetssteg är ${\textstyle (5^{n/2})^{1/n}={\sqrt {5} }}$ . I grafteoretiska termer betyder detta att Shannon-kapaciteten för 5-cykeln är minst ${\sqrt {5}}$ . Som Lovász (1979) visade är denna gräns snäv: det är inte möjligt att hitta ett mer komplicerat system av kodord som tillåter att ännu fler olika meddelanden skickas på samma tid, så Shannon-kapaciteten för 5-cykeln är exakt ${\sqrt {5}}$ .

Relation till oberoende uppsättningar

Om en graf $G$ representerar en uppsättning symboler och de symbolpar som kan förväxlas med varandra, undviker en delmängd $S$ av symboler alla förväxlande par om och endast om $S$ är en oberoende uppsättning i grafen, en delmängd av hörn som inte inkluderar båda ändpunkterna för någon kant. Den maximala möjliga storleken på en delmängd av symbolerna som alla kan särskiljas från varandra är oberoendetalet α $\displaystyle \alpha (G)}$ i grafen, storleken på dess maximala oberoende uppsättning . Till exempel, ' $\alpha (C_{5})=2$ : 5-cykeln har oberoende uppsättningar av två hörn, men inte större.

För kodord av längre längder kan man använda oberoende uppsättningar i större grafer för att beskriva de uppsättningar av kodord som kan överföras utan förvirring. Till exempel, för samma exempel på fem symboler vars förvirringsgraf är $C_{5}$ , finns det 25 strängar med längd två som kan användas i ett längd-2-kodningsschema. Dessa strängar kan representeras av hörnen i en graf med 25 hörn. I den här grafen har varje vertex åtta grannar, de åtta strängarna som den kan förväxlas med. En delmängd av längd-två strängar bildar en kod utan möjlig förvirring om och endast om den motsvarar en oberoende uppsättning av denna graf. Uppsättningen kodord {"11", "23", "35", "54", "42"} bildar en av dessa oberoende uppsättningar med maximal storlek.

Om $G$ är en graf som representerar signalerna och förväxlande par av en kanal, då är grafen som representerar längden-två kodorden och deras förväxlande par G $\displaystyle G\boxtimes G}$ , där symbolen $\boxtimes$ representerar den starka produkten av grafer . Detta är en graf som har en vertex för varje par $(u,v)$ av en vertex i produktens första argument och en vertex i produktens andra argument. Två distinkta par $(u_{1},v_{1})$ och $(u_{2},v_{2})$ ligger intill varandra i den starka produkten om och endast om $u_{1}$ och $u_{2}$ är identiska eller angränsande, och $v_{1}$ och ${\ displaystyle v_{2}}$ är identiska eller intilliggande. Mer generellt kan kodorden med längden $k$ representeras av grafen $G_{k}$ , den $k$ -faldiga starka produkten av $G$ med sig själv , och det maximala antalet kodord av denna längd som kan överföras utan förvirring ges av oberoendetalet $\alpha (G_{k})$ . Det effektiva antalet signaler som sänds per tidsenhetssteg är ${\displaystyle k}:$ te roten av detta tal, $\alpha (G_{k})^{1/k}$ .

Med hjälp av dessa begrepp kan Shannon-kapaciteten definieras som

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

gränsen (eftersom $k$ blir godtyckligt stor) för det effektiva antalet signaler per tidssteg för godtyckligt långa förväxlingsfria koder.

Beräkningskomplexitet

Olöst problem i matematik :

Vad är Shannon-kapaciteten för en 7-cykel?

(fler olösta problem i matematik)

Beräkningskomplexiteten för Shannonkapaciteten är okänd, och till och med värdet på Shannonkapaciteten för vissa små grafer såsom $C_{7}$ ( en cykelgraf med sju hörn) förblir okänt.

Ett naturligt tillvägagångssätt för detta problem skulle vara att beräkna ett ändligt antal potenser för den givna grafen ${\displaystyle G} ,$ hitta deras oberoendetal och från dessa tal sluta sig till viss information om det begränsande beteendet hos sekvensen från vilken Shannon-kapaciteten är definierad. Emellertid (även om man bortser från beräkningssvårigheten att beräkna oberoendesiffrorna för dessa grafer, ett NP-hårt problem) innebär det oförutsägbara beteendet hos sekvensen av oberoende antal potenser för $G$ att detta tillvägagångssätt inte kan användas för att exakt approximera Shannon-kapaciteten.

Övre gränser

Delvis eftersom Shannon-kapaciteten är svår att beräkna, har forskare letat efter andra grafinvarianter som är lätta att beräkna och som ger gränser för Shannon-kapaciteten.

Lovász nummer

Lovász -talet ϑ( G ) är en annan grafinvariant, som kan beräknas numeriskt med hög noggrannhet i polynomtid med en algoritm baserad på ellipsoidmetoden . Shannonkapaciteten för en graf G begränsas underifrån av α( G ), och ovanifrån av ϑ( G ). I vissa fall sammanfaller ϑ( G ) och Shannon-kapaciteten; till exempel för grafen för en femhörning är båda lika med √ 5 . Det finns dock andra grafer för vilka Shannon-kapaciteten och Lovász-talet skiljer sig åt.

Haemers bunden

Haemers gav en annan övre gräns för Shannon-kapaciteten, som ibland är bättre än Lovász-gränsen:

$\Theta (G)\leq R(G)=\min _{B}\operatörsnamn {rank} (B),$

där B är en n × n matris över något fält , så att b _ii ≠ 0 och b _ij = 0 om hörn i och j inte ligger intill varandra.