Vi introducerar (privat) entropi av en riktad graf (i en ny nätverkskodning betydelse) samt ett antal relaterade begrepp. Vi visar att entropin i en riktad graf är identisk med dess gissningsnummer och kan begränsas underifrån med antalet hörn minus storleken på grafens kortaste indexkod. Vi visar att Network Coding solvability för varje specifik multipel unicast nätverk är helt bestäms av entropi (samt av den kortaste indexkod) i den riktade grafen som uppstår genom att identifiera varje källa nod med varje motsvarande mål nod. Shannons informationsojämlikhet kan användas för att beräkna övre gränser på en grafs entropi samt beräkna storleken på den minimala indexkoden. Nyligen har ett antal nya familjer av så kallade icke-shannon-liknande informationsojämlikheter upptäckts. Det har visat sig att det finns kommunikationsnät med en kapacitet som är strikt nödvändig för löslighet, men där detta faktum inte kan härledas med hjälp av Shannons klassiska informationsojämlikhet. Baserat på detta resultat visar vi att det finns grafer med entropi som inte kan beräknas med bara Shannons klassiska informationsojämlikhet, och visar att bättre uppskattning kan erhållas med hjälp av vissa icke-shannon-liknande informationsojämlikheter.
Riis introducerar privat entropi av en riktad graf och relaterar den till gissningsnummer av grafen REF.
Graph Entropy, Network Coding and Guessing games
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}