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.