Page 102 - vol1

A bizonyítása során Euler a problémát a gráfelmélet nyelvén fogalmazta meg,
azaz leegyszerűsítette azt: a földeket, azaz a folyó partjait beleértve a szigeteket
is csomópontoknak, a hidakat pedig éleknek tekintette a mai megfogalmazás
szerint. Az így létrehozott csomópontok és élek pedig egy gráfot határoznak
meg.

Vegyük észre, hogy a gráfnak mind a 4 csúcsának a fokszáma páratlan szám, ami
azt jelenti, hogy a gráfban nincs sem zárt sem nyílt Euler út. Ez tulajdonképpen
azt is jelenti, hogy a kért séta nem valósítható meg.

Nézzünk most néhány bejárhatósági problémát:

1. Két szigetet az alábbi ábrán látható módon 15 híd köt össze
egymással és a parttal. Bejárható-e a 15 híd úgy, hogy mindegyiken pontosan
egyszer haladjunk át?

Ha az A, B, C, D, E és F szárazföldeket egy gráf csúcsainak, az a, b, c, d, e,
f, g, h, i, k, l, m, n, p és q hidakat egy gráf éleinek tekintjük, láthatjuk, hogy
minden csúcs fokszáma páros, kivéve a D és az E csúcsot, melyek fokszáma
páratlan. Így Euler 2. tétele értelmében (v.ö.: MatLap 1/2016, 3. oldal) létezik
nyílt Euler-út. Egy ilyen nyílt Euler út az élek (hidak) szerint az
[abcdefghikmnpqt].

102