Kezdőlap


Feladat:	B.4218	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Ágoston Tamás , Damásdi Gábor , Éles András , Mester Márton , Mészáros András , Strenner Péter
Füzet:	2010/május, 284 - 285. oldal		PDF \| MathML
Témakör(ök):	Feladat, Gráfelmélet
Hivatkozás(ok):	Feladatok: 2009/november: B.4218

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. Legyenek a gráf csúcsai $A_{1}, A_{2}, ..., A_{n}$ , az $A_{i}$ fokszámát jelölje $a_{i}$ . Az $A_{i}$ -vel szomszédos csúcsok halmaza $B_{i}$ , az $A_{i}$ -vel nem szomszédos csúcsoké pedig $C_{i}$ . A feladat feltétele szerint $C_{i}$ minden elemének létezik szomszédja $B_{i}$ -ben. Ezért a $B_{i}$ -beli csúcsok fokszámának összege legalább $| B_{i} | + | C_{i} | = n - 1$ . Ezeket az értékeket $i = 1$ -től $n$ -ig összegezve legalább $n (n - 1)$ -et kapunk. Ebben az összegben minden csúcs annyiszor szerepel, amennyi a foka, így

\begin{matrix} n^{2} - n = a_{1}^{2} + a_{2}^{2} + ... + a_{n}^{2} \geq n (n - 1) . \end{matrix}

Mivel itt egyenlőség van, valamennyi becslésben egyenlőség teljesül, azaz minden

C_{i}

-beli csúcsnak pontosan egy

B_{i}

-beli szomszédja van, és semelyik két

B_{i}

-beli csúcs nincs egymással összekötve. Ez úgy is fogalmazható, hogy a gráf tetszőleges csúcsának semelyik két szomszédja között nem halad él. Ebből következik, hogy a gráf nem tartalmaz 3-hosszúságú kört. Így azonban 4-hosszúságú kör sem lehet benne. Ha ugyanis

A_{1}

A_{2}

A_{3}

A_{4}

egy ilyen kör csúcsai az összekötés sorrendjében, akkor ‐ 3-hosszúságú kör nem lévén ‐

A_{3} \in C_{1}

A_{2}, A_{4} \in B_{1}

, és

A_{3}

-nak két szomszédja is van

B_{1}

-ben:

A_{2}

és

A_{4}

, ami ellentmondás. A legrövidebb kör hossza tehát legalább 5. Ha a gráf egyetlen 5-hosszúságú kör, akkor teljesül a feladat valamennyi feltétele; a legrövidebb kör hossza tehát lehet 5. Megmutatjuk még, hogy a legrövidebb kör sosem lehet 5-nél hosszabb. Egy 5-nél hosszabb legrövidebb

A_{1} A_{2}, ..., A_{k - 1} A_{k}

(

k \geq 6

) körben ugyanis például az egymással össze nem kötött

A_{1}

és

A_{4}

csúcsoknak nincs közös szomszédja; ha ugyanis

P

mindkettőjükkel össze lenne kötve, akkor

A_{1} A_{2} A_{3} A_{4} P

5-hosszúságú kör lenne, ami ellentmondás. Így viszont a gráf nem teljesítené a feladat egyik feltételét.
A legrövidebb kör hossza tehát csakis 5 lehet.