Kőnig-lemma

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

A gráfelméletben a Kőnig Dénes nevét viselő lemma a következőképpen hangzik:

Legyen G egy végtelen sok csúcspontot tartalmazó összefüggő gráf, amelynek minden csúcsa véges fokú. Ekkor G bármely csúcsához található olyan végtelen út, mely áthalad ezen a csúcson.

Egy gyakran előforduló speciális eset a következő:

Minden olyan végtelen fagráf, melynek minden csúcsa véges fokú, tartalmaz végtelen utat.

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

A bizonyításhoz két állításra van szükség.

1. Állítás: Ha egy gráf végtelen, akkor benne végtelen sok olyan pont van, amik vagy teljes végtelen részgráfot alkotnak, vagy izoláltak egymástól.

Ez a végtelen Ramsey-tétel legegyszerűbb esete.

2. Állítás: Egy végtelen számsorozatban van vagy végtelen csökkenő, vagy végtelen növekvő részsorozat.

Az első állítás bizonyítása[szerkesztés | forrásszöveg szerkesztése]

Veszünk egy pontot a gráfból, és elnevezzük x1-nek. Ha ennek foka véges, akkor szomszédait elhagyva kapjuk a csúcsok egy részhalmazát; ezt Y1-gyel jelöljük, és ellátjuk az x1 pontot egy mínusz címkével. Ha x1 foka végtelen, akkor azokat a pontokat hagyjuk el, amik nem szomszédosak vele. Az így keletkezett halmazt elnevezzük Y1-nek.

Ezután választunk egy x2 pontot Y1-ből, és megvizsgáljuk, hogy végtelen-e a foka. Ha végtelen, akkor kidobjuk a nem szomszédos pontokat, és a pontot ellátjuk egy plusz címkével; ha véges, akkor a szomszédait dobjuk ki, és az adott pontot egy mínusz címkével látjuk el. Így kapjuk az Y2 halmazt.

Hasonlóan folytatva az eljárást kapunk egy végtelen pontsorozatot, aminek minden elemére vagy egy plusz, vagy egy mínusz van írva. Innen már látszik, hogy valamelyikből végtelen soknak kell lennie, mert ha az egyikből véges sok van, akkor ezeket elhagyva is véges sok pont marad. Ha a pluszosakból van végtelen, akkor végtelen teljes részgráf van; ha mínuszosakból, akkor végtelen él nélküli részgráf van.

A második állítás bizonyítása[szerkesztés | forrásszöveg szerkesztése]

Az első állítás segítségével a második is könnyen belátható.

Tekintsük ugyanis azt a gráfot, amiben a csúcsok a sorozat elemeinek felel meg, és egy él akkor létezik, ha a nagyobb sorszámú elem nagyobb. Az első állítást erre a gráfra alkalmazva kapjuk, hogy vagy van egy végtelen teljes részgráf, vagy van egy végtelen üres részgráf. A végtelen teljes részgráf végtelen növekvő, a végtelen üres részgráf végtelen csökkenő részsorozatot jelent.

A Kőnig-lemma bizonyítása[szerkesztés | forrásszöveg szerkesztése]

Tekintsük a fát szélességi bejárás szerint, és induljunk el a gyökérből!

Mivel véges sok pont van az első szinten, azért ha az első szintből induló utak mindegyike véges hosszú lenne, akkor lenne maximális úthossz, tehát a fa véges magasságú, így véges lenne. Válasszuk ki azt a pontot, amiből akármilyen messze el lehet jutni!

Hasonlóan folytatva látszik, hogy mindig lesz olyan pont, amiből tovább lehet lépni, mivel minden pontnak véges sok szomszédja van. Tehát kapunk egy végtelen pontsorozatot, ami kijelöl egy végtelen hosszú utat.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Forrás[szerkesztés | forrásszöveg szerkesztése]