Numret på en riktad graf (digraf), som motsvarar digrafens entropi, infördes som ett direkt kriterium på en nätkodningsinstanss löslighet. Detta dokument ger två bidrag till gissningsnumret. För det första introducerar vi en oriktad graf om alla möjliga konfigurationer av digrafen, kallad gissningskurvan, som inkapslar kärnan i beroendet mellan konfigurationer. Vi bevisar att gissningstalet för en digraf är lika med logaritmen för självständighetstalet för dess gissningsdiagram. Därför är nätkodningslösning inte längre ett problem för de operationer som görs av varje nod, utan förenklas till ett problem på de meddelanden som kan passera genom nätverket. Genom att studera gissningsdiagrammet i en given digraf, och hur man kombinerar digrafer eller alfabet, kan vi på så sätt härleda gränser på gissningsantalet digrafer. För det andra, vi konstruerar specifika digrafer med höga gissningsnummer, vilket ger nätverk kodande instanser där en stor mängd information kan passera. Vi föreslår först en konstruktion av digrafer med finita parametrar baserade på cykliska koder, med gissningsnummer lika med graden av generatorn polynom. Vi konstruerar sedan en oändlig klass av digrafer med godtycklig omkrets för vilken förhållandet mellan det linjära gissningstalet och antalet hörn tenderar till en, trots att dessa digrafer är godtyckligt glesa. Dessa konstruktioner ger solvable nätverk kodande instanser med ett relativt litet antal mellanliggande noder för vilka nodoperationer är kända och linjära, även om dessa fall är glesa och källorna är godtyckligt långt från deras motsvarande sänkor.
Detta arbete utökas ytterligare av Gadouleau och Riis REF genom att föreslå begreppet gissningsdiagram och hitta specifika riktade grafer med högt gissningsnummer som kan överföra stora mängder information.
Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Mathematics', 'Computer Science']}