Feladat:	B.5105	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Argay Zsolt ,  Kerekes Boldizsár
Füzet:	2020/szeptember, 351 - 352. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Irányított gráfok, Matematika
Hivatkozás(ok):	Feladatok: 2020/május: B.5105

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 $n\le 2$, akkor nyilván $k=1$, hiszen a gráfban nem lehet irányított kör. Tegyük fel ezután, hogy $n\ge 3$. Ekkor $k\ge 2$, mivel például egy irányított $n$ hosszú kör megfelelő színezéséhez legalább két szín szükséges. Megmutatjuk, hogy $k=2$ szín már mindig elegendő. Számozzuk meg a gráf csúcsait az $\mathrm{1,2,}\text{...}\mathrm{,}n$ számokkal, és egy $i$ csúcsból egy $j$ csúcsba mutató irányított él legyen piros, ha $i<j$, és legyen kék, ha $i>j$. Ekkor, ha az $i_1\mathrm{,}{i}_2\mathrm{,}\text{...}\mathrm{,}{i}_t$ csúcsok ebben a sorrendben egy egyszínű irányított kör csúcsai lennének, akkor vagy $i_1<i_2<\text{...}<i_t<i_1$-nek, vagy $i_1>i_2>\text{...}>i_t>i_1$-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 $n=\mathrm{1,2}$ esetén $k=1$, $n\ge 3$ esetén pedig $k=2$.     II. megoldás. Az $n$ szerinti indukcióval igazoljuk, hogy $n\ge 3$ esetén $k=2$. A kezdeti feltételek nyilvánvalóan teljesülnek. Tegyük fel, hogy az állítás minden $n$ csúcsú gráfra igaz, és tekintsünk egy $n+1$ csúcsú gráfot. Válasszuk ki ennek egyik, $P$ csúcsát. A $P$ csúcsot és a vele szomszédos éleket elhagyva, a kapott $n$ csúcsú gráf az indukciós feltevés szerint megfelelően kiszínezhető két színnel. A $P$-vel szomszédos élek közül pedig a $P$-be menőket színezzük pirosra, a $P$-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 $P$-n, akkor az indukciós feltevés szerint nem lehet egyszínű. Ha pedig átmegy $P$-n, akkor tartalmaz egy $P$-be menő és egy $P$-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: $B_1\mathrm{,}{B}_2\mathrm{,}\text{...}\mathrm{,}{B}_t\mathrm{,}{B}_1$. A $B_i{B}_{i+1}$ él nem lévén piros, a $B_{i+1}$-et $B_i$ -vel irányított piros út köti össze (minden $i=\mathrm{1,}\text{...}\mathrm{,}t$-re). Legyen ez az út: $B_{i+1}{A}_1^i{A}_2^i\text{...}{A}_{k_i}^i{B}_i$. Tekintsük a következő piros irányított utakat: $\begin{array}{c}{\displaystyle \left(B_1{A}_1^t{A}_2^t\text{...}{A}_{k_t}^t{B}_t\right)\mathrm{,}\left(B_t{A}_1^{t-1}{A}_2^{t-1}\text{...}{A}_{k_{t-1}}^{t-1}{B}_{t-1}\right)\mathrm{,}\text{...}\mathrm{,}\left(B_2{A}_1^1{A}_2^1\text{...}{A}_{k_1}^1{B}_1\right)\mathrm{.}}\end{array}$ Ezeket összefűzve egy piros irányított kört kapunk a $B_v$ 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.)