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. I. megoldás. Ha , akkor nyilván , hiszen a gráfban nem lehet irányított kör. Tegyük fel ezután, hogy . Ekkor , mivel például egy irányított hosszú kör megfelelő színezéséhez legalább két szín szükséges. Megmutatjuk, hogy szín már mindig elegendő. Számozzuk meg a gráf csúcsait az számokkal, és egy csúcsból egy csúcsba mutató irányított él legyen piros, ha , és legyen kék, ha . Ekkor, ha az csúcsok ebben a sorrendben egy egyszínű irányított kör csúcsai lennének, akkor vagy -nek, vagy -nek kellene teljesülnie, azonban világos, hogy ezek egyike sem állhat fenn. Ezzel mutattunk olyan színezést 2 színnel, ami megfelelő. Tehát esetén , esetén pedig . II. megoldás. Az szerinti indukcióval igazoljuk, hogy esetén . A kezdeti feltételek nyilvánvalóan teljesülnek. Tegyük fel, hogy az állítás minden csúcsú gráfra igaz, és tekintsünk egy csúcsú gráfot. Válasszuk ki ennek egyik, csúcsát. A csúcsot és a vele szomszédos éleket elhagyva, a kapott csúcsú gráf az indukciós feltevés szerint megfelelően kiszínezhető két színnel. A -vel szomszédos élek közül pedig a -be menőket színezzük pirosra, a -ből indulókat pedig kékre. Így az egész gráf színezése megfelelő: ha egy irányított kör nem megy át -n, akkor az indukciós feltevés szerint nem lehet egyszínű. Ha pedig átmegy -n, akkor tartalmaz egy -be menő és egy -ből induló élt is, és ezek különböző színűek.
Argay Zsolt (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 11. évf.)
III. megoldás. Egy szín biztosan nem lesz elég, hiszen lehet a gráfban irányított kör. Megmutatjuk, hogy egyébként pedig két szín elég lesz. Kezdjük el az egyik színnel (piros) beszínezni az éleket, és legyen a színezésünk olyan értelemben maximális, hogy jelenleg még nincs piros irányított kör, de ha bármelyik további élt színeznénk pirosra, akkor már lenne. Színezzük ezért a többi élt kékre. Megmutatjuk, hogy ekkor nincs kék irányított kör. Tegyük fel indirekt, hogy van kék irányított kör: . A él nem lévén piros, a -et -vel irányított piros út köti össze (minden -re). Legyen ez az út: . Tekintsük a következő piros irányított utakat: | | Ezeket összefűzve egy piros irányított kört kapunk a csúcsokon keresztül. Elképzelhető, hogy az összefűzött utaknak volt közös csúcsa vagy éle, de ez csak annyit jelent, hogy több piros irányított kört is kaptunk. Ez azonban ellentmond a piros szín használatával kapcsolatban megfogalmazott feltételünknek, azaz ellentmondásra jutottunk, tehát bizonyításunk teljes.
Kerekes Boldizsár (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 9. évf.) |
|