Page 106 - vol1

A feladat gráfja a mellékelt ábrán látható. Ezúttal irányított gráfról van szó, de
ebben is érvényes az Euler tétele. Mivel a gráf minden fokszáma páros, és
minden csúcsnál a bemenő élek száma egyenlő a kijövő élek számával (vagyis a
befok egyenlő a kifokkal) ezért Euler-gráf, tehát a kért bejárás elvégezhető. Az
ábrán 1-től 18-ig számozva a bejárási sorrendet jelöltük meg.

10. Egy majomcsalád az
erdőben öt fán él. Két fa közötti nyíl
jelentése: erről a fáról arra a fára
ment a majomcsalád. A nyilak
segítségével állapítsd meg, hogy hol
töltötték az éjszakájukat, és jelenleg
hol tartózkodnak! Indokold meg a válaszodat!

Ahol a bemenő nyilak száma megegyezik a kimenő nyilakéval, ott nem
lehetnek, mert ahányszor az adott fára mentek, ugyanannyiszor el is hagyták azt.
Most azon a fán vannak, ahol több a bemenő, mint a kimenő nyíl. Azon a fán
éjszakáztak, ahol több a kimenő nyíl, mint a bemenő nyíl. Tehát az 5. fán
éjszakáztak, és most az 4. fán vannak.

Szintén bejárhatósági problémák közé tartoznak a következő
konstruktív megoldáson alapuló példák is:

11. A következő rajzon egy palota alaprajza látható, amely alagsorába
két bejáraton (az A-n és a B-n) keresztül lehet bejutni. A jobb felső sarokban levő
K-val jelölt kamrában található a kincs.

106