Az A. 731. feladat (2018. október)

A. 731. Adott az \(\displaystyle n\) csúcsú \(\displaystyle G\) fagráf, a csúcsainak halmaza \(\displaystyle V\), és adott a síkon egy \(\displaystyle n\)-elemű \(\displaystyle P\) ponthalmaz, melynek elemei között nincs három egy egyenesen. Igaz-e a \(\displaystyle G\) gráf és a \(\displaystyle P\) halmaz tetszőleges kiválasztása esetén, hogy \(\displaystyle G\) belerajzolható a \(\displaystyle P\) halmazba, vagyis létezik olyan \(\displaystyle f\colon V\to P\) kölcsönösen egyértelmű megfeleltetés, hogy ha \(\displaystyle G\) minden \(\displaystyle (x,y)\) éléhez megrajzoljuk az \(\displaystyle \big[f(x),f(y)\big]\) szakaszt, akkor semelyik két ilyen szakasz nem metszi egymást?

Javasolta: Váli Benedek (Szeged)

(7 pont)

A beküldési határidő 2018. november 12-én LEJÁRT.

Megoldás. A válasz igen. A következő, erősebb állítást fogjuk igazolni:

Ha \(\displaystyle G\) egy \(\displaystyle n\)-csúcsú fagráf, egy kitüntetett csúcsa \(\displaystyle r\) (ezt fogjuk a fa "gyökerének" hívni), valamint \(\displaystyle P\) egy \(\displaystyle n\) pontból álló ponthalmaz, amelynek elemei között nincs három egy egyenesen, és az \(\displaystyle R\) pont \(\displaystyle P\) konvex burkának egyik csúcsa, akkor \(\displaystyle G\) belerajzolható a \(\displaystyle P\) halmazba úgy, hogy az \(\displaystyle r\) csúcsnak az \(\displaystyle R\) pontot feleltetjük meg (1. ábra).

1. ábra

A módosított állítást indukcióval bizonyítjuk. \(\displaystyle n=1\) esetén az állítás triviális. Tegyük fel, hogy \(\displaystyle n\ge2\), és az állítás igaz bármely alacsonyabb csúcsszám esetén.

Ha \(\displaystyle G\)-ból elhagyjuk az \(\displaystyle r\) gyökeret és a belőle induló éleket, a megmaradt gráf legyen \(\displaystyle G'\); ez kisebb összefüggő komponensekre esik szét, amelyek maguk is körmentes, összefüggő gráfok, vagyis fák. Legyenek ezek a komponensek \(\displaystyle G_1,\ldots,G_k\). Először is megmutatjuk, hogy mindegyik \(\displaystyle G_i\) komponens pontosan egy szomszédját tartalamzza \(\displaystyle r\)-nek.

Tekintsünk egy \(\displaystyle G_i\) komponenst, és válasszuk ki egy \(\displaystyle v\in G_i\) csúcsát. Az \(\displaystyle r\) összeköthető \(\displaystyle v\)-vel \(\displaystyle G\)-beli úttal. Az összekötő út első éle \(\displaystyle r\) és \(\displaystyle r\) egyik \(\displaystyle w\) szomszédja között halad, a többi éle mind \(\displaystyle G'\)-n belül, tehát a további csúcsok egy komponensben vannak. A \(\displaystyle v\) csúcs \(\displaystyle G_i\)-beli, tehát \(\displaystyle w\) is \(\displaystyle G_i\)-beli. Ezzel találtunk \(\displaystyle r\)-nek \(\displaystyle G_i\)-beli szomszédját (2. ábra).

2. ábra

Másrészt, ha \(\displaystyle w_1,w_2\) két különböző, \(\displaystyle G_i\)-beli szomszédja lenne \(\displaystyle r\)-nek, akkor ezeket összekötné egy \(\displaystyle G_i\)=beli út. De \(\displaystyle G\)-ben az \(\displaystyle w_1-r-w_2\) út is összeköti \(\displaystyle w_1\)-et és \(\displaystyle w_2\)-t. A kétféle út együtt kiadna egy \(\displaystyle G\)-beli kört, ez viszont ellentmondana a feltételnek, miszerint \(\displaystyle G\) körmentes (3. ábra).

3. ábra

Ezek után mindegyik \(\displaystyle i=1,\ldots,k\)-ra jelölje \(\displaystyle r_i\) az \(\displaystyle r\) csúcs egyetlen \(\displaystyle G_i\)-beli szomszédját.

Mivel \(\displaystyle R\) a konvex buroknak csúcsa, a többi pont egy \(\displaystyle R\) csúcsú, konvex \(\displaystyle D\) szögtartományban van. Ezt a szögtartományt osszuk \(\displaystyle k\) részre: \(\displaystyle D_1,\ldots,D_k\)-ra úgy, hogy mindegyik \(\displaystyle D_i\)-ben a pontok száma megyegyezzen \(\displaystyle G_i\) csúcsszámával. A \(\displaystyle D_i\)-beli pontok halmaza legyen \(\displaystyle P_i\).

4. ábra

A \(\displaystyle P_i\) konvex burkának egy valamelyik csúcsa összeköthető \(\displaystyle R\)-rel a konvex burkon kívül haladó szakasszal; az egyik ilyen pont legyen \(\displaystyle R_i\). Rajzoljuk meg az \(\displaystyle (r,r_i)\) éleknek megfelelő \(\displaystyle RR_i\) szakaszokat, majd alkalmazzuk az indukciós feltevést külön-külön mindegyik \(\displaystyle G_i\) gráfra az \(\displaystyle r_i\) gyökérrel, a \(\displaystyle P_i\) halmazra és az \(\displaystyle R_i\) pontra; így a \(\displaystyle G\) gráfnak egy jó lerajzolását kapjuk. (4. ábra)

Statisztika:

14 dolgozat érkezett.
7 pontot kapott:	Beke Csongor, Csaplár Viktor, Milan Haiman, Nagy Nándor, Schrettner Jakab, Szabó 417 Dávid, Tóth 827 Balázs, Weisz Máté.
6 pontot kapott:	Hegedűs Dániel.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2018. októberi matematika feladatai