A B. 4518. feladat (2013. február)

B. 4518. Legyen n $\ge$ 2 páros szám, 0<k<n egész. Melyik az a legkisebb e szám, amelyre teljesül a következő: ha egy n pontú egyszerű gráfnak legalább e éle van, akkor van benne k páronként éldiszjunkt teljes párosítás?

Javasolta: Maga Péter (Budapest)

(5 pont)

A beküldési határidő 2013. március 11-én LEJÁRT.

Megoldási ötlet: Teljes körmérkőzés.

Megoldás. Megmutatjuk hogy

$e = \binom{n-1}2+k.$

Először konstruálunk egy gráfot, aminek e-1 éle van, és nem tartalmaz k éldiszjunkt teljes párosítást. Vegyünk egy n-1 csúcsú teljes gráfot (a csúcsai legyenek $v_1,\ldots,v_{n-1}$ ), és még egy v₀ csúcsot, amiből k-1 él indul ki (mondjuk v₀-t kössük össze a $v_1,\ldots,v_{k-1}$ csúcsokkal.) A kapott gráfnak $\binom{n-1}2+k-1=e-1$ éle van. Mivel v₀ foka csak k-1, nem szerepelhet k éldiszjunkt párosításban.

Másodszor negmutatjuk, hogy ha egy tetszőleges n csúcsú G egyszerű gráfnak legalább e éle van, akkor tartalmaz k éldiszjunkt teljes párosítást. Egészítsük ki G-t teljes gráffá úgy, hogy behúzzuk a hiányzó éleket; ezek száma legfeljebb $\binom{n}2-e=\binom{n}2-\binom{n-1}2-k = n-k-1$ . Az új éleket jelöljük meg, mondjuk színezzük pirosra.

Ismert, hogy minden páros n-re az n csúcsú teljes gráf felbontható n-1 éldiszjunkt teljes párosításra. (Lásd a Gy. 2097. gyakorlat megoldását, KöMaL 1983. május, 215-217. oldal.) A n-1 teljes párosításból legfeljebb n-k-1 tartalmaz piros élt, mert legfeljebb ennyi a piros élek száma. Tehát a többi, legalább (n-1)-(n-k-1)=k párosításban nincs piros él, ezek mind részgráfjai G-nek.

A 2012/13. évi spanyol bajnokság menetrendje

Statisztika:

35 dolgozat érkezett.

5 pontot kapott: Ágoston Péter, Baran Zsuzsanna, Csernák Tamás, Di Giovanni Márk, Fehér Zsombor, Havasi 0 Márton, Herczeg József, Janzer Barnabás, Janzer Olivér, Kúsz Ágnes, Maga Balázs, Mócsy Miklós, Nagy Gergely, Nagy-György Pál, Németh Gergely, Schwarcz Tamás, Seress Dániel, Tardos Jakab, Tossenberger Tamás, Venczel Tünde.

4 pontot kapott: Katona Dániel.

3 pontot kapott: 7 versenyző.

2 pontot kapott: 3 versenyző.

1 pontot kapott: 2 versenyző.

0 pontot kapott: 2 versenyző.

A KöMaL 2013. februári matematika feladatai

35 dolgozat érkezett.
5 pontot kapott:	Ágoston Péter, Baran Zsuzsanna, Csernák Tamás, Di Giovanni Márk, Fehér Zsombor, Havasi 0 Márton, Herczeg József, Janzer Barnabás, Janzer Olivér, Kúsz Ágnes, Maga Balázs, Mócsy Miklós, Nagy Gergely, Nagy-György Pál, Németh Gergely, Schwarcz Tamás, Seress Dániel, Tardos Jakab, Tossenberger Tamás, Venczel Tünde.
4 pontot kapott:	Katona Dániel.
3 pontot kapott:	7 versenyző.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	2 versenyző.

Már regisztráltál?
Új vendég vagy?