A königsbergi hidak problémája

A bizonyítások tanítása című írásunkban megemlítettük ezt a híres problémát, most megadjuk a rá vonatkozó bizonyítást is.
Megoldandó és beküldhető feladatokat is mellékelünk a cikkhez.

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.