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. 4518. feladat (2013. február)

B. 4518. Legyen n\ge2 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 v0 csúcsot, amiből k-1 él indul ki (mondjuk v0-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 v0 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