Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 5105. feladat (2020. május)

B. 5105. Legyen \(\displaystyle n\) pozitív egész. Határozzuk meg azt a legkisebb \(\displaystyle k\) számot, ahány színnel bármilyen \(\displaystyle n\) csúcsú irányított egyszerű gráf élei színezhetők úgy, hogy ne legyen benne egyszínű kör.

Javasolta: Szabó Kornél (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 11. évf.)

(4 pont)

A beküldési határidő 2020. június 10-én LEJÁRT.


Megoldás. Ha \(\displaystyle n=1\) vagy \(\displaystyle n=2\), akkor egyetlen szín elegendő, hiszen a gráfban nem lehet irányított kör. Tehát ekkor \(\displaystyle k=1\).

Tegyük fel, hogy \(\displaystyle n\geq 3\). Ekkor \(\displaystyle k\geq 2\) kell legyen, hiszen ha például a gráf egy irányított \(\displaystyle k\) hosszú kör, akkor egy szín nem elég. Megmutatjuk, hogy \(\displaystyle k=2\) szín már igen. Számozzuk meg a gráf csúcsait az \(\displaystyle 1,2,\dots,n\) számokkal, és egy \(\displaystyle i\) csúcsból egy \(\displaystyle j\) csúcsba mutató irányított él legyen piros, ha \(\displaystyle i<j\), és legyen kék, ha \(\displaystyle i>j\). Ha az \(\displaystyle i_1,i_2,\dots,i_l\) csúcsok ebben a sorrendben egy egyszínű irányított kör csúcsai lennének, akkor vagy \(\displaystyle i_1<i_2<\dots<i_l<i_1\)-nek, vagy \(\displaystyle i_1>i_2>\dots>i_l>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 \(\displaystyle n=1,2\) esetén \(\displaystyle k=1\) szín elég, \(\displaystyle n\geq 3\) esetén pedig \(\displaystyle k=2\) szín elég (de 1 nem biztosan).


Statisztika:

A B. 5105. feladat értékelése még nem fejeződött be.


A KöMaL 2020. májusi matematika feladatai