Az A. 888. feladat (2024. október)

A. 888. Legyen \(\displaystyle n\) egy rögzített pozitív egész szám. Határozzuk meg a legkisebb \(\displaystyle k\) pozitív egész számot, melyre teljesül a következő állítás: tetszőleges \(\displaystyle G\) egyszerű, összefüggő gráf és \(\displaystyle V_1\), \(\displaystyle V_2\), \(\displaystyle \ldots\), \(\displaystyle V_n\) minimális vágások esetén legfeljebb \(\displaystyle k\) csúcs választható ki úgy, hogy bármely két kiválasztott csúcshoz létezzen egy \(\displaystyle 1 \leq i \leq n\) egész szám, melyre a két kiválaszott csúcsot elválasztja \(\displaystyle V_i\).

A gráf \(\displaystyle V\) csúcshalmazának két diszjunkt nemüres részre való bontását minimális vágásnak nevezzük, ha a két rész között haladó élek száma minimális.

Javasolta: Imolay András (Budapest)

(7 pont)

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

Azt állítjuk, hogy \(\displaystyle k=2n\). Erre egy jó példa egy \(\displaystyle 2n\) csúcsból álló kör. Legyenek a csúcsai sorban \(\displaystyle v_1, v_2, \ldots , v_{2n}\), és legyenek a vágások \(\displaystyle V_i=\{v_i, v_{i+1}, \ldots , v_{i+n-1}\}\) minden \(\displaystyle 1 \leq i \leq n\) esetén. Először is figyeljük meg, hogy ezek tényleg minimális vágások, ugyanis mindegyik \(\displaystyle V_i\)-ből pontosan két él lép ki, és nincs a csúcsoknak olyan részhalmaza, amiből csak egy él lép ki (azaz nincs hídél). Továbbá gondoljuk meg, hogy itt ki lehet választani az összes csúcsot, azaz bármelyik csúcspárhoz van olyan \(\displaystyle V_i\), ami pontosan egyet tartalmaz közülük. Valóban, tetszőleges két csúcsot választva legalább \(\displaystyle n-1\) csúcs van köztük a kör egyik ívén, és ekkor jó vágás lesz az, ahol az egyik rész az egyik csúcsot és a következő \(\displaystyle n-1\) csúcsot tartalmazza a legalább \(\displaystyle n-1\) csúcsból álló ívről.

Most térjünk rá annak a bizonyítására, hogy miért nem lehet \(\displaystyle k>2n\). Legyen \(\displaystyle G=(V,E)\) tetszőleges gráf, és legyenek \(\displaystyle V_1, V_2, \ldots , V_n\) minimális vágások. Minden \(\displaystyle v\) csúcshoz rendeljük hozzá egy kódot, ami egy \(\displaystyle n\)-hosszú \(\displaystyle 0-1\) sorozat, melynek az \(\displaystyle i.\) jegye pontosan akkor \(\displaystyle 1\), ha \(\displaystyle v \in V_i\). Figyeljük meg, hogy két csúcshoz pontosan akkor van olyan \(\displaystyle V_i\), ami pontosan az egyiküket tartalmazza, ha a hozzájuk rendelt kód különböző. Azaz azt kell bizonyítanunk, hogy a csúcsokhoz rendelt kódok között legfeljebb \(\displaystyle 2n\) darab különböző van.

Nevezzünk egy kódot párosnak, ha páros sok 1-es szerepel benne, különben páratlannak. Minden \(\displaystyle x\) kódhoz legyen \(\displaystyle V_x\) azon csúcsok halmaza, akikhez az \(\displaystyle x\) kódot rendeltük. Tetszőleges \(\displaystyle S\) vágásra \(\displaystyle d(S)\) jelölje azt, hogy hány él megy a vágás két része között. A bizonyítás kulcsa a következő lemma.

Lemma.

\(\displaystyle \sum_{i=1}^n d(V_i) \geq \sum_{x \text{ páros}} d(V_x) \quad \text{ és } \quad \sum_{i=1}^n d(V_i) \geq \sum_{x \text{ páratlan}} d(V_x).\)

Bizonyítás: Csak az első egyenlőtlenséget bizonyítjuk, a másik ugyanúgy megy. Az egyenlőtlenség mindkét oldala éleket számol le, egy élet leszámolhat akár többször is. Azt fogjuk megmutatni, hogy a bal oldal minden élet legalább annyiszor megszámol, mint a jobb oldal. Legyen \(\displaystyle e \in E\) tetszőleges él, és legyen \(\displaystyle x\) és \(\displaystyle y\) a két végpontjának a kódja. Ezek szerint a kódok szerint esetekre bontunk.

• Ha \(\displaystyle x\) és \(\displaystyle y\) is páratlan, akkor a jobb oldalon egyszer sem számoljuk meg \(\displaystyle e\)-t, így igaz az állítás.
• Ha \(\displaystyle x \neq y\) és \(\displaystyle x\) és \(\displaystyle y\) közül pontosan egy páros, akkor a jobb oldalon egyszer számoljuk meg \(\displaystyle e\)-t, és a bal oldalon is megszámoljuk legalább egyszer, mert különböző \(\displaystyle e\) végpontjainak a kódja, és így legalább egy vágás elválasztja őket egymástól.
• Végül ha \(\displaystyle x\) és \(\displaystyle y\) is páros, akkor \(\displaystyle x=y\) esetén egyik oldalon sem számoljuk meg őket, ha pedig \(\displaystyle x\neq y\), akkor a jobb oldalon kétszer számoljuk meg \(\displaystyle e\)-t, de a bal oldalon is legalább ennyiszer, mert \(\displaystyle x\) és \(\displaystyle y\) kódja legalább két helyen eltér egymástól, és az ezekhez a helyekhez tartozó vágások elválasztják \(\displaystyle e\) végpontjait egymástól.

A lemmát használva már nem nehéz befejezni a bizonyítást. Mivel a \(\displaystyle V_i\) vágások minimálisak, és pozitív az értékük (mert \(\displaystyle G\) összefüggő), így az mindkét egyenlőtlenség jobb oldalán legfeljebb \(\displaystyle n\) darab nemnulla összeadandó szerepelhet. Azonban ha \(\displaystyle d(V_x)=0\), akkor a csúcsokat az üres halmazra és \(\displaystyle V\)-re választottuk szét, és ekkor vagy egyik csúcsnak sem \(\displaystyle x\) a kódja, vagy mindegyiknek \(\displaystyle x\) a kódja, és az utóbbi lehetetlen, mert \(\displaystyle G\) összefüggő. Ekkor tehát a legfeljebb \(\displaystyle n\) különböző páros kód tartozik a csúcsokhoz, és ugyanígy, páratlan kódból sem lehet több, mint \(\displaystyle n\)-féle rendelve a csúcsokhoz, és ezzel a bizonyítást befejeztük.

Statisztika:

Az A. 888. feladat értékelése még nem fejeződött be.

A KöMaL 2024. októberi matematika feladatai