Page 101 - vol1

12. Az okostelefonok és gráfelmélet II.

Az előző paragrafusban számos olyan játékot mutattunk be,
amelyeket tulajdonképpen didaktikai játékoknak nevezhetünk, mert ezek egyes
gráfelméleti fogalmak, tulajdonságok és eredmények gyakorlati kivitelezésére,
modellezésére szolgáltak, mint például az egyvonalas megrajzolhatósági
problémák, az izomorf gráf fogalma és síkgráfok, a Hamilton utak fogalma. Ezek
a játékok az okostelefonokon és a táblagépeken, az Androidos rendszereken
futnak, így a használatuk a diákok keze ügyében vannak.

Ebben a részben egy újabb témakört veszünk nagyító alá, az
egyvonalas bejárhatósági problémákat, amelyeknek az elméleti hátterét
vizsgáljuk meg.

Egyvonalas bejárhatósági problémák
Az egyik legrégebbi bejárhatósági probléma az úgynevezett Königsbergi
hidak problémája. A probléma története az, hogy a poroszországi Königsberg
(most Kalinyingrád, Oroszország) városban 7 híd ívelt át a várost átszelő Prégel
folyón úgy, hogy ezek a folyó két szigetét is érintették. A königsbergiek azzal a

kérdéssel fordultak Eulerhez, vajon végig lehet-e menni az összes hídon úgy,
hogy mindegyiken csak egyszer haladjanak át, és egyúttal visszaérjenek a
kiindulópontba.
1736-ban Euler bebizonyította, hogy ez lehetetlen. A történethez hozzátartozik
az a legenda is, hogy 1750 körül állítólag a königsbergi elit tagjai rendszeresen
sétálgattak vasárnaponként a hidakon, hogy egy olyan útvonalat találjanak,
amely megfelel a fenti feltételeknek.

101