Kőnig-lemma
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
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, amelyek 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
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, amelyek 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, amelynek 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
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
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, amelyből tovább lehet lépni, mivel minden pontnak véges sok szomszédja van. Tehát kapunk egy végtelen pontsorozatot, amely kijelöl egy végtelen hosszú utat.
Lásd még szerkesztés
Források szerkesztés
|
Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle! |
