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

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

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

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

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

Mutassuk meg, hogy k\gen.

(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 Si csúcsosztályainak megfelelő vektorok ai és bi; ekkor Si 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 (GF2 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\gen.


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