Matematika | Középiskola » Euler- és Hamilton-kör

1. Euler- és Hamilton körök C folyo ’ A sziget C B sziget A B D D Az egyik legrégibb gráfelméleti feladat, a königsbergi-hidak problémája még a 18. századból származik Königsberg -ma Kalinyingrád- városának lakói megkérdezték Eulertől, a svájci matematikustól, hogy lehet-e olyan sétát tenni, mely a város összes hı́dján pontosan egyszer megy át, és ugyanoda érkezik vissza. A hidak elhelyezkedését az ábra mutatja Euler belátta, hogy ez nem lehetséges. Innen ered a következő definı́ció és tétel Definı́ció: Egy G gráfban Euler-körnek (Euler-útnak) nevezünk egy körsétát (sétát), ha az a gráf minden élét pontosan egyszer tartalmazza. Tétel: Egy összefüggő G gráfban pontosan akkor létezik Euler-kör, ha minden pont fokszáma páros. Bizonyı́tás: Először belátjuk, hogy ha G-ben van Euler-kör, akkor minden pont fokszáma páros. A gráf egy

tetszőleges pontjából kiindulva járjuk végig az Euler-kört. Ekkor minden pontba ugyanannyiszor ’megyünk be mint ki’, és a ki -és bemenések száma éppen a pont fokszáma, ezért minden pont fokszáma páros. A másik irány bizonyı́tásához legyen G egy összefüggő gráf melyben minden pontnak páros a fokszáma. Induljunk el egy tetszőleges pontból, és haladjunk élek mentén úgy, hogy egy élen csak egyszer megyünk. Mivel minden pontnak páros a fokszáma, ezért ha egy olyan pontba érünk, melyből nem vezet ki több él, akkor ez a pont csak a kiinduló pont lehet. Így kapunk egy C körsétát. Ha C még nem tartalmazza a gráf összes élét (vagyis C még nem Euler-kör), akkor a G gráf összefüggősége miatt a C-ben van olyan pont, melyből indul ki G − C-beli él. Legyen v egy ilyen pont Induljunk el v-ből, és haladjunk G − C-beli éleken úgy, hogy egy élt csak egyszer

használunk. Mivel G − C-ben továbbra is páros minden pontnak a fokszáma, ezért csak a v pontban akadhatunk el, vagyis kapunk egy C1 körsétát. A C és C1 körsétákból csinálunk egy C 0 körsétát mely tartalmazza a C és C1 -beli éleket is: kezdjük el bejárni a C körsétát; amikor először a v ponthoz érünk, akkor menjünk végig a C1 körsétán; mikor C1 -en végigmentünk, akkor haladjunk ismét C mentén. 1 Ha a kapott C 0 körséta nem Euler-kör, akkor ismételjük meg a fenti eljárást. Mivel az eljárás során egyre nagyobb körsétákat kapunk, vagyis a kimaradó élek száma egyre csökken, ezért végül egy Euler-körhöz jutunk. Ugyanı́gy bizonyı́tható, hogy egy összefüggő G gráfban pontosan akkor létezik Euler-út, ha a páratlan fokú pontok száma 0 vagy kettő. A bizonyı́tás során megadtunk egy módszert is arra, hogyan lehet egy Eulerkört megtalálni,

ha minden pontnak páros a fokszáma. Nézzük a következő gráfot: A B C E F H D Vegyük a gráf egyik pontját, mondjuk A-t, és induljunk el belőle élek mentén, amı́g el nem akadunk. Mondjuk kapjuk az A−D−E −F −C −B −A körsétát. Ez még nem Euler-kör, az E pontból még lép ki él; most induljunk el az E pontból, és menjünk a még nem használt éleken, ı́gy kapjuk az E − B − H − E körsétát. Ha most összetesszük a két körsétát, akkor megkapjuk az A − D − E − B − H − E − F − C − B − A Euler-kört. Definı́ció: Egy G gráfban Hamilton-körnek nevezünk egy kört, ha a gráf összes pontját tartalmazza. Egy utat Hamilton-útnak nevezünk, ha a gráf összes pontját tartalmazza. Hamilton-kör létezésére nem ismert szükséges és elégséges feltételt adó tétel. Mi itt két elégséges feltételt adó tételt ismertetünk Tétel: [Ore]

Legyen G = (V, E) egy egyszerű gráf, melyben teljesül a következő (?) feltétel: bármely két x, y ∈ V pontra, melyekre d(x)+d(y) < n, teljesül, hogy (x, y) ∈ E. Ekkor G-ben létezik Hamilton-kör Tétel: [Dirac] Ha egy n pontú egyszerű gráfban minden pontnak legalább n/2 a fokszáma, akkor a gráfban van Hamilton-kör. Bizonyı́tás: Következik az Ore-tételből, mert a (?) feltétel triviálisan teljesül. Arra, hogy az Ore-tételben illetve a Dirac tételben szereplő feltételek nem szükségesek, egyszerű példát mutatni. Legyen G egy öt hosszú kör Ekkor G maga egy Hamilton-kör, de a két feltétel egyike sem teljesül. 2 Tétel: Ha a G gráfban valamely k darab pont elhagyása után a gráf legalább k + 1 komponensre esik szét, akkor G-ben nincs Hamilton-kör. 3