KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

A. 606. Prove that for every simple graph G with n vertices there exist some simple graphs S1, ..., Sk with the following properties:

(a) every Si is a complete bipartite graph;

(b) every edge of G is contained by an odd number of graphs Si;

(c) every edge of the complement of G is contained by an even number of graphs Si;

(d) k\le\frac34n.

(5 points)

Deadline expired on 10 February 2014.


Google Translation (Sorry, the solution is published in Hungarian only.)

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,B\subsetV 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, G1 és G2 szimmetrikus differenciájának azt a gráfot, amit úgy kapunk, hogy vesszük azokat az éleket, amik G1 és G2 közül pontosan az egyikben szerepelnek. A szimmetrikus differenciát jelöljük G_1\triangle G_2-vel. A \triangle 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 f(n)\le\frac34n. 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 n\le3 esetén. Tegyük fel, hogy n\ge4, é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}\cupB)×({b}\cupA) gráfban szerepel az összes a-ból vagy b-ből induló él.

Vizsgáljuk most a G'=G\triangle S 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 G=G'\triangle S, 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 A\capB\capC=Ø.

Legyen


\matrix{
S_1 &=& \big(\{a\}\cup (B\cap C)\big) &\times& \big(\{b,c\}\cup A\big), \cr
S_2 &=& \big(\{b\}\cup (C\setminus B)\big) &\times& \big(\{c\}\cup (B\setminus C)\big).
}

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

A G'=G\triangle S_1\triangle S_2 gráfban a, b és c is izolált csúcs, ezért G=G'\triangle S_1\triangle S_2 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: \big(\{a,b\}\times\{c\}\big)\triangle
\big(\{a,c\}\times\{d\}\big)\triangle
\big(\{a,d\}\times\{b\}\big), 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, Va-val, Vabc-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 Vabc 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


\matrix{
S_1 & = & \big( \{a,b\}
\cup V_{c} \cup V_{bc} \cup V_{cd} \cup V_{acd} \cup V_{bcd} 
\big) &\times& \big( \{c\}
\cup V_{a} \cup V_{ab} \cup V_{abd} \cup V_{abcd} 
\big),\cr
S_2 & = & \big( \{a,c\}
\cup V_{d} \cup V_{bd} \cup V_{cd} \cup V_{abd} \cup V_{bcd} 
\big) &\times& \big( \{d\}
\cup V_{ac} \cup V_{abc} \cup V_{abcd} 
\big),\cr
S_3 & = & \big( \{a,d\}
\cup V_{a} \cup V_{b} \cup V_{bc} \cup V_{bd} \cup V_{abc} \cup V_{bcd} 
\big) &\times& \big( \{b\}
\cup V_{ad} \cup V_{acd} \cup V_{abcd} 
\big).\cr
}

Ezzel a választással a G'=G\triangle S_1\triangle S_2\triangle S_3 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 S1,S2,S3 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


f(n) \le \max\big( f(n-1), f(n-2)+1, f(n-3)+2, f(n-4)+3 \big) \le \frac34 n.


Statistics on problem A. 606.
4 students sent a solution.
5 points:Ágoston Péter, Maga Balázs.
4 points:Simon 047 Péter.
0 point:1 student.


  • Problems in Mathematics of KöMaL, January 2014

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley