Az A. 606. feladat (2014. január)

A. 606. Bizonyítsuk be, hogy tetszőleges, n pontú G egyszerű gráfhoz léteznek olyan S₁, ..., S_k egyszerű gráfok, amelyekre a következők teljesülnek:

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

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

(c) G komplementerének minden éle páros sok S_i-ben szerepel;

(d) .

(5 pont)

A beküldési határidő 2014. február 10-én LEJÁRT.

Megoldásvázlat. Legyen G csúcshalmaza V. A megoldáshoz csak olyan gráfokat fogunk használni, amelyek csúcsai a V halmazból kerülnek ki. Az ilyen gráfokat azonosítani fogjuk az éleik halmazával; minden egyes gráfnak megfelel tehát egy V-beli, különböző elemekből álló rendezetlen párokból álló halmaz. Tetszőleges A,BV diszjunkt halmazokra (A×B)-vel fogjuk jelölni azt a teljes gráfot, amelynek két csúcshalmaza A, illetve B. (Ez nem azonos a halmazelméletből ismert Descartes-szorzattal.)

Nevezzük két gráf, G₁ és G₂ szimmetrikus differenciájának azt a gráfot, amit úgy kapunk, hogy vesszük azokat az éleket, amik G₁ és G₂ közül pontosan az egyikben szerepelnek. A szimmetrikus differenciát jelöljük -vel. A művelet kommutatív és asszociatív, így beszélhetünk több gráf szimmetrikus differenciájáról, a sorrend és zárójelezés megadása nélkül is.

Jelöljük f(n)-nel a legkisebb olyan nemnegatív egész számot, amire igaz, hogy tetszőleges n pontú gráf előáll legfeljebb f(n) teljes gráf szimmetrikus differenciájájaként. A feladat megoldásához azt kell igazolnunk, hogy . n szerinti indukcióval bizonyítunk. Könyen ellenőrizhetjük, hogy f(0)=f(1)=0, f(2)=1 és f(3)=2, ezért az állítás teljesül n3 esetén. Tegyük fel, hogy n4, és az állítás igaz minden kisebb értékre.

1. eset: A gráfban van egy a izolált pont. Ekkor a G\{a} gráf előáll legfeljebb f(n-1) teljes páros gráf összegeként.

2. eset: A gráfban van két szomszédos pont, a és b, amiknek nincs közös szomszédja. Legyen az a csúcs b-től különböző szomszédainak halmaza A, a b csúcs a-tól különböző szomszédainak halmaza pedig B. Az S=({a}B)×({b}A) gráfban szerepel az összes a-ból vagy b-ből induló él.

Vizsgáljuk most a gráfot. Ennek a gráfnak a és b is izolált pontja, így G' előállításához biztosan elég f(n-2) teljes gráf. Mivel , az S gráfot hozzávéve ez egy összesen legfeljebb f(n-2)+1 gráfból álló előállítás.

3. eset: A gráfban van három pont, a, b és c, amik egy háromszöget alkotnak, de nincs közös szomszédjuk. Legyen a, b és c további szomszédainak halmaza rendre A, B és C. A feltevésünk szerint ABC=Ø.

Legyen

Az gráf tartalmazza az összes a,b,c-ből induló élt.

A gráfban a, b és c is izolált csúcs, ezért gráfot előállíthatjuk összesen f(n-3)+2 teljes páros gráf szimmetrikus differenciájaként.

4. eset: A gráfban van négy pont, a, b, c és d, amik páronként szomszédosak. Az összes a-ból, b-ből, c-ből vagy d-ből induló élt előállítjuk három teljes páros gráf szimmetrikus differenciájaként. A három gráfot úgy konstruáljuk, hogy először előállítjuk az {a,b,c,d} csúcsú teljes gráfot: , majd ezekhez hozzávesszük a G gráf bizonyos csúcsait.

A további csúcsokat összesen 16 halmazra bonthatjuk aszerint, hogy a,b,c,d közül melyekkel szomszédosak. Ezeket a halmazokat V_Ø-zal, V_a-val, V_abc-vel stb. fogjuk jelölni; az indexekben az a,b,c,d csúcsok közül azokat soroljuk fel, amelyek szomszédok. Tehát például V_abc azoknak az a,b,c,d-től különböző csúcsoknak a halmaza, amelyek szomszédosak a,b,c-vel, de nem somszédosak d-vel.

Most megadjuk a három teljes gráfunkat; legyen

Ezzel a választással a gráfban a, b, c és d is izolált pont, így előállítható legfeljebb f(n-4) teljes gráf szimmetrikus differenciájaként; Ezekhez hozzávéve az S₁,S₂,S₃ gráfokat, a G gráfot f(n-4)+3 teljes gráffal állítjuk elő.

A négy eset közül legalább az egyik bekövetkezik, így

Statisztika:

4 dolgozat érkezett.
5 pontot kapott:	Ágoston Péter, Maga Balázs.
4 pontot kapott:	Simon 047 Péter.
0 pontot kapott:	1 versenyző.

A KöMaL 2014. januári matematika feladatai