„Információközlés és gráfelmélet” címen mesél a modern matematika két meglepően összekapcsolódó fejezetéről a
Fővárosi Fazekas Mihály Gimnázium Nagytermében.
Az előadó beharangozója az alábbiakban olvasható.
Hogyan kell ügyesen barkochbázni? Legalább hány eldöntendő kérdést kell például
ahhoz feltennünk, hogy a válaszokból ki tudjuk találni a 8-szor 8-as sakktábla
egyik mezőjét, amire játszótársunk gondolt? Változik-e ez a minimális szám, ha
a kérdéseket előre, a válaszok ismerete nélkül kell feltennünk?
A dolog nyitja, ha észrevesszük, hogy a válaszokat megfeleltethetjük kétféle
jelből, mondjuk 0-kból és 1-esekből álló sorozatoknak. Az így kapott sorozatok
kódolják a gondolt mezőt, minket pedig az érdekel, hogy mennyire hosszú kódra
van feltétlenül szükség.
Akkor is kódolunk, ha írunk vagy beszélünk. Egy beszélőtől is elvárjuk, hogy
lehetőség szerint röviden fejezze ki magát. De ha a rádióban bemondanak egy telefonszámot,
amit föl szeretnénk írni, akkor azért nem bánjuk, ha megismétlik, ez csökkenti
az esélyét, hogy rosszul jegyezzük le.
Hogyan lesz mindebből matematikai elmélet, amiben az információ mennyiségét számszerűen
is kifejezhetjük? Részben erről szól az előadás. Meg arról is, hogy hogyan kerülhetnek
ide a gráfok. Erre nevezetes példa az alábbi.
Tegyük fel, hogy minden közlendőnket a p, n, u, v, b betűkkel, illetve ezek sorozataival kell kódolnunk. Kézírásunk olyan, hogy a
fenti felsorolásban minden leírt betűnk nézhető bármelyik szomszédjának is, emellett
a szélen álló p akár b-nek, a b pedig p-nek is. Vagyis az öt betűt egy gráf pontjainak tekintve és az összekeverhetőket
összekötve egy öt hosszúságú kört kapunk.
Tegyük fel azt is, hogy az összekötetlen párok viszont soha nem téveszthetők
össze. Ekkor, ha egyetlen betű használható valamilyen üzenet átadásához, és azt
akarjuk, hogy az biztosan helyesen legyen értelmezhető, akkor legfeljebb kétféle
üzenetünk lehet, hiszen nincsen három betűnk, amik páronként összekötetlenek volnának
a gráfunkban. Hányféle kétbetűs üzenetünk lehet, amik biztosan nem keverhetők
össze? Kétszer annyi, mint előbb, azaz négy, vagy akár több is? Igyekszem majd
vázolni, milyen messzire vezetett ez az ártatlannak látszó kérdés.
