Ore-tétel

A Wikipédiából, a szabad enciklopédiából

A matematika, azon belül a gráfelmélet területén az 1960-ban Øystein Ore norvég matematikus által bizonyított Ore-tétel elégséges feltételt ad gráfban Hamilton-kör létezésére, lényegében azt állítja, hogy elegendően nagy számú éllel rendelkező gráfnak mindig van Hamilton-köre. Specifikusan a tétel a nem szomszédos csúcspárok fokszámainak összegeit vizsgálja: ha bármely nem szomszédos csúcspár fokszámösszege eléri a gráf csúcsainak számát, akkor a gráfnak van Hamilton-köre.

A tétel megfogalmazása[szerkesztés]

Ore-tétel (1961): Ha egy csúcsú olyan egyszerű gráf, amire teljesül, hogy ha nem alkotnak élt (összekötetlenek), és ekkor , akkor -ben van Hamilton-kör.

Bizonyítás[szerkesztés]

Tegyük fel indirekt, hogy a gráf kielégíti a feltételt, de nincsen benne Hamilton-kör. Ez az ellenpélda gráfunk legyen . Húzzunk be -be további éleket úgy, hogy az új gráf is ellenpélda legyen (továbbra sincs benne Hamilton-kör). Így kapunk egy gráfot, ami továbbra is ellenpélda, hisz új élek behúzásával "rossz pontpárt" nem lehet létrehozni, de ha még egy élet akárhogyan behúzunk, akkor már tartalmaz a gráf Hamilton-kört. Biztosan van két olyan pont, hogy , hiszen egy csúcsú teljes gráfban van Hamilton-kör. Ekkor viszont a gráfban van Hamilton-kör, tehát -ben van Hamilton-út. Legyenek a Hamilton-út csúcsai: , és és . Ha szomszédos a út valamely pontjával, akkor nem lehet összekötve -vel, mert ez esetben () egy Hamilton-kör lenne.

A szaggatottal jelölt él nem lehet éle a gráfnak, mert így egy Hamilton-kört kapnánk

Így tehát nem lehet összekötve legalább darab ponttal, ezért

ami viszont ellentmondás, hiszen volt feltéve.

Megjegyzések[szerkesztés]

  • A fenti feltétel tehát a szomszédos pontpárok fokszámösszegéről nem mond semmit. Ki lehet mondani a tételt kissé más megfogalmazásban is: Ha az csúcsú gráfban nincs olyan pontpár, amelyre és , akkor -ben van Hamilton-kör.
  • A tétel nevét Øystein Ore norvég matematikusról kapta.
  • Ez tehát egy elégséges – de nem szükséges – feltétel Hamilton-kör létezésére.

A Pósa-tétel és az Ore-tétel kapcsolata[szerkesztés]

Állítás[szerkesztés]

Pósa-tétel Ore-tétel

Bizonyítás[szerkesztés]

Azt kell tehát igazolnunk, hogy a Pósa-tétel egy gyengébb feltételből jut ugyanarra a következtetésre (hogy a gráfban van Hamilton-kör), azaz, hogy a Pósa-tételben szereplő feltétel mindig teljesül, ha az Ore-tételbeli feltétel teljesül.

Tegyük fel indirekt, hogy ez nem igaz, azaz létezik olyan csúcsú egyszerű gráf, hogy teljesül rá az Ore-feltétel, de a Pósa-féle nem: , amire . Rögzítsünk le egy ilyen -t! Mivel , így a darab legkisebb fokszámértékhez tartozó csúcsok közül bármelyik kettő fokszámösszege kisebb, mint . Viszont feltettük, hogy az Ore-féle feltétel teljesül, ezért ez azt jelenti, hogy ez a csúcs páronként össze van kötve egymással, azaz egy csúcsú teljes részgráfot alkotnak. Emiatt viszont – mivel fokszámaik nem nagyobbak -nál, de már van db szomszédjuk – mindegyik legfeljebb egy további csúccsal lehet összekötve a maradék csúcs közül. Azonban (hiszen ) a maradék csúcs között maradni fog olyan, amelyiknek nincs az előbbi csúcs közötti szomszédja. Ennek a csúcsnak mindegyik szomszédja a maradék csúcs közül fog kikerülni, így a fokszáma maximum . Ezek szerint ezen csúcs és az első csúcs bármelyike egyrészt összekötetlen, másrészt fokszámaik összege legfeljebb , ami viszont ellentmond az Ore-féle feltételnek, pedig arról feltettük, hogy teljesül. Ez az ellentmondás bizonyítja az állítást.

Hivatkozások[szerkesztés]

  • Katona–Recski–Szabó: A számítástudomány alapjai, Typotex, Budapest, 2003.