 |
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