A B. 4938. feladat (2018. február)

B. 4938. Ismert, hogy a tórusz felületére rá lehet rajzolni a $\displaystyle 7$ pontú teljes gráfot (lásd pl. a Császár-poliédert). Egy sárga görbe bögre oldalán kijelölünk 7 pontot, és bármelyik kettőt össze akarjuk kötni egy-egy görbével úgy, hogy semelyik két görbének ne legyen közös belső pontja. Legalább hány görbét kell ennek eléréséhez átvezetnünk a görbe bögre fülén?

(6 pont)

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

Megoldás. Először megmutatjuk, hogy a $\displaystyle 7$-pontú teljes gráf felrajzolásához legalább $\displaystyle 6$ élt biztosan át kell vezetnünk a bögre fülén, majd egy példát mutatunk a gráf egy lehetséges felrajzolására, amikor éppen $\displaystyle 6$ élt vezetünk át a fülön.

I. Ha elhagyjuk a bögre fülét és a rajta átvezetett görbéket, a fületlen görbe felülete a gömbbe folytonosan deformálható lesz, ezért a $\displaystyle 7$ pont a megmaradó görbékkel egy síkba rajzolható gráfot alkot. Azt állítjuk, hogy ennek a $\displaystyle 7$-pontú síkgráfnak legfeljebb $\displaystyle 15$ éle lehet. Ha esetleg a gráf nem összefüggő, néhány újabb élgörbe megrajzolásával összefüggővé tehetjük. Ezért állításunkat elég összefüggő gráfokra igazolni.

A gráf élei (a megmaradó, a fülön át nem vezetett görbék) a bögre felületét (legalább háromoldalú) tartományokra osztják; legyen az élek száma $\displaystyle E$, a tartományok (lapok) száma $\displaystyle L$; a csúcsok száma $\displaystyle C=7$. Azt akarjuk megmutatni, hogy $\displaystyle E\le 15$.

Az Euler-féle poliédertétel szerint $\displaystyle C+L=E+2$, vagyis

$\displaystyle L=E-5. \tag{1}$

Számoljuk össze kétféleképpen az egymáshoz illeszkedő lap-él párokat. Mindegyik él pontosan két laphoz illeszkedik, és minden lap legalább 3 élhez, tehát

$\displaystyle 2E \ge 3L.$

Ebbe beírva (1)-et,

$\displaystyle 2E \ge 3(E-5),$

vagyis valóban $\displaystyle E\le15$.

A $\displaystyle 7$-pontú teljes gráfnak $\displaystyle \binom72=21$ éle van, tehát legalább $\displaystyle 6$ élt biztosan át kell vezetnünk a bögre fülén a gráf lerajzolásához.

II. A bal oldali ábrán a $\displaystyle 7$-pontú teljes gráf egy jól ismert felrajzolása látható a tóruszfelületre. A téglalapot hajlítsuk meg, és a két függőleges oldalt ragasszuk egymáshoz; így egy csövet kapunk. A cső két végét is egymáshoz ragasztva megkapjuk a tóruszfelületet, rajta a a $\displaystyle 7$-pontú teljes gráffal. A kék élek és a lila él együtt egy $\displaystyle 7$ hosszú kört alkotnak; ebben a piros élek a másod-, a zöld élek a harmadszomszédos pontokat kötik össze egymással.

A cső két, egymáshoz ragasztott végén (a téglalap alsó és felső oldalán) éppen $\displaystyle 6$ él halad keresztül; ha tehát a csövet a bögre oldalára rajzoljuk, elég ezt a $\displaystyle 6$ élt átvezetnünk a bögre fülén, ahogy a jobb oldali ábra is mutatja.

Válogatás a beküldött dolgozatok konstrukcióiból

Hervay Bence

Soós Máté

Pituk Gábor ötletéből
(A hatszög szemközti oldalait ragasztjuk össze; a fül lehet például a piros és narancsszínű oldalak által alkotott zárt görbe.)

Gáspár Attila

Statisztika:

30 dolgozat érkezett.
6 pontot kapott:	Döbröntei Dávid Bence, Gáspár Attila, Hegedűs Dániel, Hervay Bence, Kerekes Anna, Nagy Nándor, Schifferer András, Schrettner Jakab, Soós 314 Máté, Szabó 417 Dávid.
5 pontot kapott:	Füredi Erik Benjámin.
4 pontot kapott:	6 versenyző.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	3 versenyző.
0 pontot kapott:	7 versenyző.

A KöMaL 2018. februári matematika feladatai