10.9 Euler gráfok
Egy olyan körutat a G gráfban, amely tartalmazza a G összes élét Euler-körnek mondjuk. Egy gráf Euler gráf, ha benne létezik Euler-kör. Az elnevezés L. Euler német matematikusra utal. Ő 1736-ban Königsbergben volt matematika professzor. Kőnigsberg városát átszeli a Pregel folyó, amelyen 7 híd található. Ezek a hidak összekötik a szárazföldet a folyó szigeteivel:
Euler azt a kérdést vetette fel, hogy tervezhető-e egy olyan séta a város hídjain, amely minden hidat egyszer, és csak egyszer érint?
Euler a következőképpen bizonyította egy ilyen séta létezésének lehetőségét:
-
Definiáljuk a következő sorozatot: a sorozatban egy betű azt a szárazföldet jelenti, amelyhez az út során elérkeztünk, és két egymás utáni elem azt a hidat jelenti, amelyen át kell kelni útban az egyik területről a másikra.
-
Ha ilyen út létezne, akkor az leírható lenne 8 betűvel, amelyek mindegyikét az A, B, C és D betűkből választjuk
-
Mivel minden hídon pontosan egyszer szabad átmenni, ezért az A és B betűk ebben a sorozatban kétszer fordulnak úgy elő, hogy ők egymást követik. Ugyanez a helyzet az A és C betűpárral is.
-
Mivel öt híd vezet az A által jelölt területre, ezért A-nak a jó megoldásban háromszor kell megjelenni. (Két pár jelöl egy-egy belépést és kilépést az A területre, egy pedig vagy kilépést vagy belépést A-ra.)
-
Hasonló megfontolásból, B, C és D kétszer jelenik meg a sorozat-ban.
-
Ezért legalább 9 betűből kell állni a sorozatnak. Ez pedig lehetetlen.
Azt tehát látjuk, hogy Kőnigsbergben a felvetett probléma nem oldható meg. Euler azonban nem állt meg itt, hanem megvizsgálta a problémát általánosan, és a következő tételt mondta ki:
Tétel 10.4: Egy összefüggő G gráf akkor és csak Euler gráf, ha a G minden csúcsa páros.
A Königsbergi hidak problémájához tartozó gráf a következő ábrán látható. Itt a sötét színű csúcspontok a szárazföldeket, a világosak a hidakat jelölik.
13.ábra. A Königsbergi hidak problémájának gráf modellje.
Az általános tétel alapján rögtön eldönthető, hogy a problémának nincs megoldása, mert a gráfnak több páratlan csúcspontja is van.