A kérdés
Bejárhatók-e a königsbergi hidak úgy, hogy minden hidat pontosan egyszer érintünk?
A probléma vizsgálata
A feladat átfogalmazása
Vizsgáljuk meg Königsberg térképének a feladat szempontjából fontos elemeit. A hidakon való áthaladás az érdekes számunkra, a szárazföldön való közlekedés mikéntje nem. Ezért megtehetjük, hogy a térképvázlat azon pontjait, amelyeket a folyó érintése nélkül össze tudunk kötni egymással, azonos színnel befestjük.
A következő lépésben az azonos színű pontok közül kiválasztunk egyet-egyet, azok fogják képviselni az összes többi, megfelelő színű pontot.
Ha két, betűvel jelölt pontra igaz az, hogy egyetlen hídon történő átkeléssel eljuthatunk az egyikből a másikba, akkor összekötjük azokat egy vonallal.
A gráfelméleti probléma
Ez az ábra már csak pontokat, és azok közötti összekötő vonalakat ábrázol. Gráfelméleti elnevezéssel a pontokat szögpontoknak, az összekötő vonalakat éleknek nevezzük. Az eredeti feladatot a gráfok nyelvére lefordítva a következő kérdéshez jutunk:
Megrajzolható-e egy vonallal a gráf úgy, hogy minden élen pontosan egyszer haladunk át?
Vizsgáljuk meg, milyenek lehetnek egy, a fenti módon megrajzolható gráf szögpontjai!
Ha sikerült a gráfot egyetlen zárt vonallal megrajzolnunk, akkor ez csakis úgy történhetett, ha minden szögpontba páros sok él futott be. Hiszen zárt vonalról van szó, valahányszor beérkeztünk egy pontba, mindannyiszor tovább is kellett haladnunk, tehát ki is kellett onnan jönnünk, tehát minden élnek kell lennie egy párjának, vagyis minden szögpontban párosával kell előfordulniuk az éleknek. Ez azt jelenti, hogy az egy zárt vonallal megrajzolható gráfoknak minden szögpontjába páros sok él fut be. Ezt a tényt röviden úgy nevezzük, hogy a szögpont fokszáma páros, még rövidebben: minden szögpont páros.
Érdemes külön is megfogalmazni a definíciót: Fokszámnak nevezzük a gráfok egy szögpontjába összefutó élek számát.
Írjuk be a vizsgált gráfba a szögpontok fokszámát!
Esetünkben az összes fokszám páratlan. A gráf tehát nem rajzolható meg egyetlen zárt vonallal. Ha csak egyetlen páratlan szögpontja lenne, akkor sem tudnánk megrajzolni, a fenti érvelés alapján.
Tovább kell vizsgálnunk a kérdést. Nem zárt vonallal megrajzolható-e a gráf? Megrajzolható-e egy olyan vonallal, amelyiknek van kezdőpontja, van végpontja, de ezek nem esnek egybe? A kezdőpontnak páratlannak kell lennie, hiszen induláskor nem egy élen jövünk be, hanem a pontból indulunk, hasonlóképpen befejezéskor az utolsó pontból nem egy élen jövünk ki, hanem egyszerűen felemeljük a ceruzát. Ezek szerint egyetlen, nem zárt vonallal, csak azok a gráfok rajzolhatók meg, amelyeknek pontosan két páratlan szögpontjuk van.
Bebizonyítottuk, hogy csak azok a gráfok rajzolhatók meg egy zárt vonallal, amelyeknek minden szögpontja páros. Ha nem kötjük ki a zárt vonalat, akkor a szögpontok között pontosan kettő páratlan fokszámú pont lehet.
Ebben a bizonyításban azt vizsgáltuk, milyenek az egy vonallal megrajzolható gráfok. Ebből megállapíthattuk, hogy ha egy gráf nem tesz eleget a feltételeknek, akkor az nem rajzolható meg.
Igaz az is, hogy minden, a feltételeknek megfelelő, gráf tényleg megrajzolható egy vonallal, de erre a válaszadáshoz nincs szükségünk.
A válasz
A königsbergi hidak nem járhatók úgy, hogy minden hídon pontosan egyszer haladunk át. Vagy ki kell hagynunk valamelyiket, vagy pedig lesz olyan, amelyiken többször is át kell haladnunk, mire az összest bejárjuk.
Megjegyzések
- A bizonyítást olvasva nehezebben követhető, élőszóban meghallgatva, megbeszélve, az ábrák megfelelő részére rámutatva sokkal egyszerűbben megérthető.
- A megfelelő gráfelméleti tétel akkor és csak akkor típusú: a gráfok akkor és csak akkor rajzolhatók meg egy zárt vonallal, ha minden szögpontjuk páros. Az előbbiekben e tételnek csak az egyik felével foglalkoztunk: Ha egy gráf egy zárt vonallal megrajzolható, akkor a szögpontjai párosak. Az állítás nem bizonyított másik fele: Ha egy gráfnak minden szögpontja páros, akkor megrajzolható egyetlen zárt vonallal.
- A königsbergi probléma megoldásához Euler nem használta a gráfelméleti terminológiát, hiszen a gráfelmélet éppen e probléma vizsgálata következményeképpen született meg.
Feladatok
- Vizsgáljátok meg, megrajzolható-e a házikó, vagy más elnevezéssel a boríték egyetlen vonallal?
- Számít-e, hogy a gráfok pontjait hogyan helyezzük el a papíron? Számít-e, hogy hogyan, milyen vonallal kötjük össze azokat a szögpontokat, amelyek között él van, más szóval: amelyek szomszédosak?
- Küldjetek be olyan gráfokat, amelyek megrajzolhatók: a., egy zárt vonallal, b., egy nem zárt vonallal! Lehet rajzban és táblázattal is
