Feladat: Pontversenyen kívüli P.351 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Csikós Zsolt ,  Megyesi Gábor 
Füzet: 1982/november, 143 - 145. oldal  PDF  |  MathML 
Témakör(ök): Részgráfok, Euler-gráfok (unikurzalitás), Pontversenyen kívüli probléma
Hivatkozás(ok):Feladatok: 1981/október: Pontversenyen kívüli P.351

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Az állítást 20 város helyett tetszőleges n számú városra bizonyítjuk. Feleltessünk meg minden városnak egy-egy pontot, és kössünk össze két pontot, ha a nekik megfelelő városok között van közvetlen járat. Így egy gráfhoz jutunk, a városoknak megfelelő n pont lesz a gráf n szögpontja, a járatokat jelző szakaszok pedig az élek. Minden szögpontból négy él indul ki. Tegyük fel, hogy az egyik légitársaság járatait piros, a másikét kék színű élek jelzik gráfunkon. Ez esetben a következő tételt kell belátnunk.
Tétel. Ha egy gráf minden szögpontjából négy él indul ki, akkor az élek kiszínezhetők pirossal és kékkel úgy, hogy minden szögpontból két piros és két kék él induljon ki.
Ennek az állításnak a bizonyításához két további tételt használunk fel.

 

A Tétel. Tetszőleges gráf szögpontjai beoszthatók úgy osztályokba, hogy bármely két szögpont pontosan akkor legyen egy osztályban, ha az éleken haladva el lehet jutni az egyikből a másikba.
Ezt a tételt könnyen bebizonyíthatjuk.
Vegyünk egy tetszőleges a szögpontot, a neki megfelelő város legyen A. Válasszuk ki az összes olyan várost, ahova A-ból repülőn (esetleg többszöri átszállással) el lehet jutni. Soroljuk ezeket a városokat A-val egy osztályba.
 

1. ábra
 

Nyilvánvaló, hogy ha B és C két ilyen város, akkor B-ből (A-n keresztül) el tudunk jutni C-be is (esetleg többszöri átszállással). Másrészt semelyik ebben az osztályban szereplő városból nem vezet járat az osztályon kívülre, mert ha valamely D városba el lehet jutni A-ból, akkor A-ból azokba a városokba is el lehet jutni, amelyekbe D-ből indul járat (1. ábra).
Ha most a fennmaradó (A-val egy osztályba nem kerülő) városok közül kiválasztunk egy tetszőleges A'-t, arra ezt az eljárást megismételhetjük. Az A'-vel egy osztályba sorolt városok egy újabb (az előzőtől diszjunkt) osztályt adnak. Ezt az eljárást addig folytatjuk, amíg a városok el nem fogynak. A városok így kapott osztályozását a nekik megfelelő szögpontokon végrehajtva éppen a kívánt osztályozáshoz jutunk.
Persze előfordulhat, hogy minden szögpont (ill. város) belekerül már az első osztályba. Ez az eset akkor áll elő, ha A-ból minden városba el lehet jutni. Ilyenkor a gráfot összefüggőnek nevezzük. Általában pedig az igaz, hogy az egy-egy osztályba került szögpontok és a köztük futó élek egy ilyen összefüggő (rész)gráfot alkotnak.
Láttuk, hogy két különböző osztályba tartozó pont között nem vezet él, így feladatunkban egy-egy osztály által meghatározott részgráfon belül is minden szögpontból négy él indul ki.
Gráfunkat tehát olyan összefüggő részgráfokra bontottuk, ahol minden pont pontosan egy részhez tartozik, és minden részgráfban az összes végpontból négy él indul ki. A tételt elég külön-külön az ilyen összefüggő osztályokra bizonyítani. Más szavakkal ez azt jelenti, hogy feltehetjük: a gráfunk összefüggő. Ezután rátérhetünk második felhasználandó tételünkre. Ez így szól:
 

B Tétel. Ha egy összefüggő gráfban minden szögpontból páros sok él indul ki, akkor a gráf éleit végigjárhatjuk úgy, hogy minden élt pontosan egyszer érintünk és az első él végpontja a második kiindulópontja, a második végpontja a harmadik kiindulópontja stb., végül az utolsó él végpontja az első kiindulópontja lesz. (2. ábra. Az ilyen élvégigjárást a gráf Euler-körének nevezik.)
 

2. ábra
 

Minden élt pontosan egyszer érintünk, de a szögpontokat szükségképpen többször is érintjük: ha pl. ‐ mint esetünkben ‐ minden szögpontból négy él indul, akkor minden szögpontot kétszer kell érinteni, kivéve az elsőt, azt háromszor. Általában: ha egy szögpontból 2k él indul ki, akkor ezt a pontot k-szor kell érinteni, kivéve ha ez a kezdőpont, amely esetben (k+1)-szer.
 

Ezt az állítást felhasználva most már könnyen bebizonyíthatjuk tételünket összefüggő gráfokra. A feltétel szerint minden szögpontból négy él indul, így a B tétel alkalmazható. Járjuk végig az ott szereplő módon az éleket, és közben fessük be őket. Az első élt fessük pirosra, a másodikat kékre, és általában a páratlanadik lépésben érintett éleket fessük pirosra, a párosadik lépésben érintetteket kékre: A kezdőpont kivételével minden szögpontot kétszer érintünk, s egy érintésnél két élt festünk meg: egyet pirosra, egyet kékre. Így végülis minden szögpontból két piros, két kék él fog indulni ‐ legalábbis a kezdőpont kivételével. A kezdőpontot háromszor érintjük: induláskor egy belőle induló élen kezdünk neki, ezt pirosra festjük. Menet közben egyszer áthaladunk rajta, ekkor két élét festjük ki, egyet pirosra, egyet kékre. Végül az utolsó lépésben ide érünk vissza. Ha ez az él páros sorszámú, akkor kékre festjük, s ez esetben a kezdőpontnál is két él lett piros, két él pedig kék. De vajon páros lesz-e az utolsó él sorszáma? Szerencsére igen, mert páros sok él van gráfunkban. Számoljuk ugyanis össze az éleket: n szögpont van, mindegyikből 4 él indul ki, ez 4n élt jelent. De így minden élt megszámoltunk mindkét végpontjánál, az élek száma tehát ennek a fele: 2n, s ez páros. Tehát a kezdőpontból is két kék és két piros él indul ki. Ezzel dőlt betűs állításunkat bebizonyítottuk.
Már csak a felhasznált B tételt kell belátnunk. Legyen tehát adva egy gráf, amelyben minden szögpontból páros sok él indul ki. Induljunk el egy tetszőleges, a0 pontból egy e1 él mentén egy a1 pontba, onnan egy e1-től különböző e2 él mentén egy a2 pontba, onnan egy még nem használt él mentén egy a3 pontba, amíg el nem akadunk. (a1 megegyezhet valamely korábbi ai-vel, csak a használt éleknek kell mindig különbözőknek lenniük. Tegyük fel, hogy egy aj pontnál elakadunk. Belátjuk, hogy aj=a0, azaz nem akadhatunk el a0-tól különböző pontnál. Nézzük meg ugyanis, hogy hány aj-ből induló élt használtunk fel. Ha aj nem a kezdőpont, akkor minden előző érintésekor egy élen elértünk aj-be, egy másik élen pedig kijöttünk belőle, viszont az utolsó alkalommal csak bementünk aj-be, ki még nem jöttünk belőle. Ez azt jelenti, hogy páratlan sok aj-ből induló élt használtunk. A feltétel szerint viszont páros sok ilyen él van, tehát biztosan maradt még olyan aj-ből induló él, amelyen továbbmehetünk aj-ből. Ezzel beláttuk, hogy csak a0-nal akadhattunk el. (Ez nyilvánvalóan azt is jelenti, hogy minden szögpontban páros sok élet használtunk fel.)
Vegyük most a leghosszabb ilyen körutat! Belátjuk, hogy ha az a szögpont szerepel az úton, akkor az összes belőle induló él is szerepel rajta. Tegyük fel ugyanis, hogy a szerepel az úton, de az a-ból b-be induló él nem. Hagyjuk el az úton szereplő éleket a gráfból. Minden szögpontból páros (esetleg 0 ) élt hagytunk el, a visszamaradt gráfban tehát megint minden szögpontból páros sok él indul. A fenti gondolatmenetet alkalmazva kaphatunk a visszamaradt gráfban egy olyan a-ból, az ab él mentén induló és a-ba visszatérő körutat, amelyben kizárólag még fel nem használt élek szerepelnek. Másrészt a az előbb kiválasztott körútnak is pontja. A két út tehát nyugodtan összekapcsolható egyetlen körúttá: megtehetjük, hogy amikor az elsőnek kiválasztott körúton először a0-ba érünk, előbb a-ból elindulva a második körutat járjuk végig, majd visszaérve a-ba, folytatjuk az előbbit. Így azonban egy, az elsőnek kiválasztottnál hosszabb körúthoz jutnánk, ami ellentmond annak, hogy az első körút maximális hosszúságú.
Ezzel beláttuk, hogy ha egy szögpont szerepel a kiválasztott úton, akkor az összes belőle induló él is szerepel rajta. De a gráfunk összefüggő, vagyis a0-ból élek mentén bármely szögpontjába eljuthatunk, tehát a kiválasztott úton minden szögpont szerepelni fog.
Ha viszont minden szögpont szerepel rajta, és minden szögponttal együtt az összes belőle induló él is szerepel rajta, akkor az összes él is szerepel a körúton, tehát ez a körút éppen megfelel állításunknak.
 

Megjegyzések. 1. Könnyen belátható, hogy ha egy gráfnak van Euler-köre, akkor minden szögpontjából páros sok él indul, vagyis ez a feltétel szükséges és elégséges az Euler-kör létezéséhez.
 

2. A feladat megoldását (és állítását) érdemes összevetni a P. 342. feladat megoldásával (és állításaival) (1981. 8‐9. szám, 146‐150. oldal).