Az A. 829. feladat (2022. május)

A. 829. Legyen $\displaystyle G$ egy $\displaystyle n$ csúcsú egyszerű gráf, melynek van legalább egy éle, és tekintsük a gráf csúcsainak azon $\displaystyle S\colon V(G)\to \mathbb{R}^{\ge 0}$ súlyozásait, melyekre $\displaystyle \sum\limits_{v\in V(G)}S(v)=1$. Legyen továbbá

$\displaystyle f(G)=\max_S \min_{(v,w)\in E(G)} S(v)S(w),$

ahol $\displaystyle S$ végigfut az összes lehetséges súlyozáson.

Bizonyítsuk be, hogy $\displaystyle f(G)=\frac{1}{n^2}$ akkor és csak akkor teljesül, ha $\displaystyle G$ csúcsai lefedhetők élek és páratlan körök diszjunkt uniójával. ($\displaystyle V(G)$ a $\displaystyle G$ gráf csúcsait, $\displaystyle E(G)$ a $\displaystyle G$ gráf éleit jelöli.)

(7 pont)

A beküldési határidő 2022. június 10-én LEJÁRT.

Megoldás. Ha minden csúcsra $\displaystyle \frac{1}{n}$ súlyt írunk, akkor a szorzatok minimuma $\displaystyle \frac{1}{n^2}$, így minden $\displaystyle G$ gráfra teljesül, hogy $\displaystyle f(G)\ge \frac{1}{n^2}$.

Tegyük föl, hogy $\displaystyle G$ csúcsai lefedhetők diszjunkt élekkel és páratlan körökkel. Ekkor tetszőleges $\displaystyle S$ súlyozás mellett létezik olyan él vagy páratlan kör a lefedésben, hogy a benne lévő csúcsokon az átlagos súly legfeljebb $\displaystyle \frac{1}{n}$. Ekkor ebben van olyan él, amin a súlyok összege legfeljebb $\displaystyle \frac{2}{n}$, így a számtani-mértani egyenlőtlenség szerint a súlyok szorzata legfeljebb $\displaystyle \frac{1}{n^2}$ ezen az élen. Tehát ekkor $\displaystyle f(G)\le \frac{1}{n^2}$, így $\displaystyle f(G)=\frac{1}{n^2}$.

Most belátjuk a másik irányt. Tegyük föl, hogy a $\displaystyle G$ gráfban van egy $\displaystyle H$ független csúcshalmaz (azaz olyan halmaz, amiben nincs két éllel összekötött csúcs), melyre azon csúcsok száma, amik valamely $\displaystyle H$-beli csúccsal szomszédosak kevesebb, mint $\displaystyle |H|$. Legyen $\displaystyle |H|=k$ és $\displaystyle H$ szomszédainak elemszáma $\displaystyle t<k$. Ekkor írjunk $\displaystyle H$ elemeire $\displaystyle \frac{1}{n}-\varepsilon$ súlyt, és $\displaystyle H$ szomszédaira $\displaystyle \frac{1}{n}+\frac{k-\frac{1}{2}}{t}\varepsilon$ súlyt. Így a $\displaystyle H$-ból kifutó éleken a szorzat

$\displaystyle \left(\frac{1}{n}-\varepsilon\right)\left(\frac{1}{n}+\frac{k-\frac{1}{2}}{t}\varepsilon\right)=\frac{1}{n^2}+\frac{k-t-\frac{1}{2}}{nt}\varepsilon -\frac{k-\frac{1}{2}}{t}\varepsilon^2.$

Válasszuk az $\displaystyle \varepsilon$ értékét olyan kicsire, hogy $\displaystyle \frac{k-t-\frac{1}{2}}{nt}\varepsilon -\frac{k-\frac{1}{2}}{t}\varepsilon^2>0$, így ezeken az éleken a szorzat nagyobb mint $\displaystyle \frac{1}{n^2}$.

$\displaystyle H$ csúcsaira és a szomszédaira összesen $\displaystyle k(\frac{1}{n}-\varepsilon)+t(\frac{1}{n}+\frac{k-\frac{1}{2}}{t}\varepsilon)=(k+t)\frac{1}{n} -\frac{1}{2}\varepsilon$ súlyt írtunk, így az összes többi $\displaystyle n-k-t$ csúcsra tudunk $\displaystyle \frac{1}{n}$-nél nagyobb súlyt írni. Ekkor minden olyan él, ami nem $\displaystyle H$ egy eleméből indul ki, két olyan csúcsot köt össze, amiken $\displaystyle \frac{1}{n}$-nél nagyobb súly van, így ezeken az éleken is $\displaystyle \frac{1}{n^2}$-nél nagyobb a szorzat, tehát $\displaystyle f(G)>\frac{1}{n^2}$.

Tehát ha egy $\displaystyle G$ gráfra $\displaystyle f(G)= \frac{1}{n^2}$, akkor nincsen benne olyan $\displaystyle H$ független csúcshalmaz, amelynek $\displaystyle |H|$-nál kevesebb szomszédja van, így elég belátni, hogy ha ez teljesül, akkor le tudjuk fedni a $\displaystyle G$ gráf csúcsait diszjunkt élekkel és páratlan körökkel. Ezt az alábbi algoritmus segítségével bizonyítjuk (az itt leírt algoritmus a magyar módszerként ismert algoritmus kiterjesztése páros helyett tetszőleges gráfokra, a bizonyítás pedig a páros gráfokra vonatkozó König-Hall tétel bizonyításának általánosítása):

Az algoritmus úgy fog menni, hogy minden lépésének kezdetén adott néhány diszjunkt él és páratlan kör. Ha ezek fedik az összes csúcsot, akkor készen vagyunk. Különben veszünk egy fedetlen $\displaystyle v$ csúcsot, és találunk olyan éleket és diszjunkt köröket, amik fedik az összes eddig fedett csúcsot, és $\displaystyle v$-t is. Az üres halmazból indulva, ilyen lépéseket csinálva végül kapunk egy megfelelő fedést. A továbbiakban azt írjuk le hogyan működik egy lépés.

Tegyük föl, hogy adott néhány diszjunkt él és páratlan kör, és egy $\displaystyle v$ csúcs amit nem fednek. A fedésben szereplő önálló éleket nevezzük piros éleknek. Definiálni fogunk egy $\displaystyle H$ és egy $\displaystyle R$ csúcshalmazt. Tekintsük a $\displaystyle v$-ből induló alternáló utakat, azaz az olyan utakat, melyeknek az élei felváltva nem pirosak és pirosak. Legyenek $\displaystyle H \cup R$-ben azok a csúcsok, melyekbe vezet $\displaystyle v$-ből alternáló út. Legyen $\displaystyle H$ azon csúcsok halmaza, melyekbe a $\displaystyle v$-ből vezető legrövidebb alternáló út páros hosszú, $\displaystyle R$ pedig azon csúcsok halmaza, melyekbe a $\displaystyle v$-ből vezető legrövidebb alternáló út páratlan hosszú. Tehát a $\displaystyle v$ csúcs $\displaystyle H$-ban van.

Ha $\displaystyle R$-ben találunk fedetlen $\displaystyle w$ csúcsot, akkor megtehetjük, hogy ehelyett az út másik paritású éleit vesszük be a fedésbe, így az út közbülső csúcsai továbbra is fedettek maradnak, és $\displaystyle v$ és $\displaystyle w$ is bekerülnek a lefedett csúcsok közé, ekkor a lépést befejeztük.

Ha $\displaystyle R$-ben van olyan $\displaystyle w$ csúcs, amely az eddigi fedésben egy páratlan körben szerepelt, akkor látható, hogy a $\displaystyle w$-be menő alternáló út és ezen páratlan kör uniója felbontható diszjunkt élekre, így ekkor is kész vagyunk.

Tegyük föl, hogy két $\displaystyle H$-ban lévő csúcs, $\displaystyle w$ és $\displaystyle z$, szomszédos a gráfban. Világos, hogy tekinthető két olyan alternáló út, az egyik $\displaystyle w$-be, a másik $\displaystyle z$-be, melyek egy ideig megegyeznek, utána pedig diszjunktak. Legyen $\displaystyle q$ az utolsó csúcs, ahol megegyeznek. Ekkor $\displaystyle q \in H$, mivel $\displaystyle q$-nál ágazik szét a két út, és $\displaystyle R$-beli csúcs után piros élen kell lépni, így nem lehet szétágazni. Emiatt $\displaystyle q$-ból $\displaystyle w$-be és $\displaystyle q$-ból $\displaystyle z$-be is páros hosszú alternáló út vezet, így ha ezek uniójához még hozzávesszük a $\displaystyle wz$ élt, akkor egy páratlan kört kapunk. A két alternáló út élei helyett vegyük be ezt a páratlan kört, és a $\displaystyle v$-ből $\displaystyle q$-ba menő alternáló úton cseréljük meg az éleket, így ebben az esetben is kapunk egy megfelelő fedést.

Tehát ha $\displaystyle v$-t nem tudjuk hozzávenni a fedéshez, az csak úgy lehetséges, ha $\displaystyle R$ minden elemének van párja egy piros élen keresztül egy $\displaystyle H$-beli csúccsal, és $\displaystyle H$-n belül nem fut él. Ekkor $\displaystyle H$-ban szerepel $\displaystyle v$, és $\displaystyle H$ összes többi csúcsát párba lehet állítani a belőle induló piros él másik végpontján lévő $\displaystyle R$-beli csúccsal, és $\displaystyle H$ összes szomszédja $\displaystyle R$-ben kell, hogy legyen, különben máshova is el lehetne jutni alternáló úttal. Tehát $\displaystyle H$ független halmaz, és eggyel több csúcs van benne, mint a szomszédainak a száma, ami ellentmondás, így ez az eset nem fordulhat elő. Emiatt tényleg mindig be tudjuk venni a $\displaystyle v$-t a fedésbe.

Ezzel az ekvivalenciát beláttuk.

Megjegyzés: Ez a feladat Greco egy 1998-as tételéből származik. Az eredeti tételben $\displaystyle x_vx_w$ szorzat helyett $\displaystyle (x_v+x_w)\log(x_v+x_w)-x_v\log x_v-x_w\log x_w$ szerepel, ennek a minimumának maximuma egy információelméletben hasznos mennyiség. A tétel bizonyítása gyakorlatilag megegyezik az itt leírttal.

Statisztika:

5 dolgozat érkezett.
7 pontot kapott:	Ben Gillott, Varga Boldizsár.
4 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2022. májusi matematika feladatai