Az A. 477. feladat (2009. március)

A. 477. Tegyük fel, hogy a 2n pontú G teljes gráf S₁,...,S_k részgráfjaira teljesülnek a következők:

(a) Mindegyik S_i teljes páros gráf;

(b) G minden egyes éle páratlan sok S_i-ben szerepel.

Mutassuk meg, hogy k $\ge$ n.

(5 pont)

A beküldési határidő 2009. április 15-én LEJÁRT.

Megoldásvázlat. A feladatot lineáris algebrai eszközökkel oldjuk meg. A csúcsok különböző részhalmazait, illetve a G külöbnöző részgráfjait a kételemű test feletti 2n-dimenziós (oszlop)vektorokkal, illetve 2n×2n-es mátrixokkal fogjuk reprezentálni.

Az egyszerűség kedvéért legyenek G csúcsai az 1,2,...2n számok.

A csúcsok egy tetszőleges részhalmazának feleltessünk meg egy 2n hosszú vektort, amelynek elemei a 0 és 1 számok lehetnek; az i-edik koordináta akkor legyen 1, ha az i csúcs eleme az adott részhalmaznak.

A G részgráfjait reprezentáljuk 2n×2n-es mátrixokkal a következőképpen: a mátrix (i,j)-edik eleme legyen 1, ha az i és j össze van kötve, egyébként pedig 0. (Ezt a mátrixot a gráf szomszédsági vagy adjacencia-mátrixának is nevezik. Egyszerű gráfok esetén -- mint a feladatban is -- az adjacencia-mátrix mindig szimmetrikus, és a főátlóban csak 0-k állhatnak.)

Minden egyes i-re legyenek az S_i csúcsosztályainak megfelelő vektorok a_i és b_i; ekkor S_i szomszédsági mátrixa

${\bf a}_i^t {\bf b}_i + {\bf b}_i^t {\bf a}_i \,.$

A G teljes gráf szomszédsági mátrixa pedig

$A = \left(\matrix %> { 0 & 1 & 1 & \ldots & 1 \cr 1 & 0 & 1 & \ldots & 1 \cr 1 & 1 & 0 & \ldots & 1 \cr \vdots & \vdots & \vdots & \ddots & \vdots \cr 1 & 1 & 1 & \ldots & 0 \cr }\right).$

Ezekkel a jelölésekkel a (b) feltételt a következő alakban is írhatjuk:

$\sum_{i=1}^k ({\bf a}_i^t {\bf b}_i + {\bf b}_i^t {\bf a}_i) = A.$

Nevezzük tetszőleges M mátrix rangjának, és jelöljük rk(M)-mel, azt, hogy a mátrix oszlopai közül hány (GF₂ fölött) lineárisan függetlent lehet kiválasztani.

Könnyen ellenőrizhető, hogy az A mátrix determinánsa 1, a rangja 2n. Ezért

$2n = rk(A) \le \sum_{i=1}^k \big( rk({\bf a}_i^t {\bf b}_i) + rk({\bf b}_i^t {\bf a}_i) \big) = 2k,$

tehát k $\ge$ n.

Statisztika:

4 dolgozat érkezett.

5 pontot kapott: Nagy 235 János, Nagy 314 Dániel, Tomon István.

1 pontot kapott: 1 versenyző.

A KöMaL 2009. márciusi matematika feladatai

4 dolgozat érkezett.
5 pontot kapott:	Nagy 235 János, Nagy 314 Dániel, Tomon István.
1 pontot kapott:	1 versenyző.

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