A B. 5509. feladat (2026. január)

B. 5509. Egy $\displaystyle n$ csúcsú gráf csúcshalmaza legyen: $\displaystyle V=\{ v_1,v_2,\ldots,v_n \}$, a $\displaystyle v_i$ csúcs fokszáma $\displaystyle d_i$. Egy a gráf csúcsaihoz nemnegatív valós számokat rendelő $\displaystyle f$ függvényt verőceinek nevezünk, ha a gráf minden $\displaystyle v_iv_j$ élére teljesül, hogy

$\displaystyle f(v_i)+f(v_j) \geq {d_i+d_j}. $

Határozzuk meg azt a legnagyobb $\displaystyle \lambda$ valós számot, amelyre minden $\displaystyle n$-re, minden $\displaystyle n$ csúcsú egyszerű gráfra és minden $\displaystyle f$ verőcei függvényre teljesül, hogy

$\displaystyle f(v_1)+f(v_2)+\ldots+f(v_n) \geq \lambda (d_1+d_2+\ldots+d_n). $

Javasolta: Varga Boldizsár (Verőce)

(6 pont)

A beküldési határidő 2026. február 10-én LEJÁRT.

1. megoldás. Ha $\displaystyle n\ge2$, és a gráf egy csillaggráf, azaz például a $\displaystyle v_1$ csúcs – ez lesz csillag közepe – össze van kötve az összes többi csúccsal, azok között pedig nincs további él, akkor a fokszámok $\displaystyle d_1=n-1$ és $\displaystyle d_2=d_3=\ldots=d_n=1$, ezek összege $\displaystyle d_1+\ldots+d_n=2(n-1)$. Az $\displaystyle f(v_1)=n$, $\displaystyle f(v_2)=f(v_3)=\ldots=f(v_n)=0$ függvény eleget tesz a feltételnek, és $\displaystyle f(v_1)+\dots+f(v_n)=n$, tehát ebben az esetben

$\displaystyle f(v_1) + f(v_2) + \ldots + f(v_n) = \dfrac{n}{2n-2} (d_1 + d_2 + \ldots + d_n). $

$\displaystyle (1) $

Ez a példa mutatja, hogy

$\displaystyle \lambda\le\dfrac{n}{2n-2}=\dfrac12+\frac{1}{2(n-1)}. $

Az $\displaystyle n\to\infty$ határátmenetből azt kapjuk, hogy $\displaystyle \lambda\le\dfrac12$.

Megmutatjuk, hogy a $\displaystyle \lambda=\dfrac12$ számra igaz a feltétel: tetszőleges $\displaystyle n$ csúcsú egyszerű gráf és verőcei függvény esetén

$\displaystyle f(v_1) + f(v_2) + \ldots + f(v_n) \ge \dfrac12(d_1 + d_2 + \ldots + d_n). $

$\displaystyle (2) $

Legyen a gráf éleinek (a megfelelő $\displaystyle \{i,j\}$ indexpárok) halmaza $\displaystyle E$; vegyük észre, hogy a jobb oldalon éppen gráf éleinek száma áll: $\displaystyle \dfrac12(d_1 + d_2 + \ldots + d_n)=|E|$.

Színezzük pirosra azokat a $\displaystyle v_i$ csúcsokat, amelyekre $\displaystyle f(v_i)\ge d_i$. Vegyük észre, hogy bármely két szomszédos $\displaystyle v_i$ és $\displaystyle v_j$ csúcs közül legalább az egyik piros, mert a feltétel szerint $\displaystyle f(v_i)+f(v_j)\ge d_i+d_j$, és emiatt $\displaystyle f(v_i)\ge d_i$ és $\displaystyle f(v_j)\ge d_j$ közül legalább az egyik teljesül.

Minden piros csúcsra jelöljük meg a belőle kiinduló éleket (egy élt akár mindkét végénél is megjelölhetünk), ezzel minden élt legalább egyszer megjelölünk. Másrészt minden piros $\displaystyle v_i$ csúcsnál legfeljebb $\displaystyle d_i$ élt jelölünk meg, ezért

$\displaystyle \sum_{i=1}^n f(v_i) \ge \sum_{\text{\(\displaystyle v_i$ piros}} f(v_i) \ge \sum_{\text{$\displaystyle v_i$ piros}} d_i \ge |E| = \dfrac12\sum_{i=1}^n d_i. \)

Ezzel megmutattuk, hogy $\displaystyle \lambda=\dfrac12$ a legnagyobb szám amely minden egyszerű gráf és verőcei függvény esetén teljesíti a feltételt.

2. megoldás. Az 1. megoldáshoz hasonlóan látjuk, hogy $\displaystyle n\ge$ esetén $\displaystyle \lambda\le\dfrac{n}{2(n-1)}$.

Megmutatjuk, hogy tetszőleges $\displaystyle n\ge2$ csúcsú egyszerű gráf és verőcei $\displaystyle f$ függvény esetén

$\displaystyle \sum_{i=1}^n f(v_i) \ge \dfrac{n}{2(n-1)}\sum_{i=1}^n d_i. $

A becslést úgy kapjuk, hogy a gráf összes élére összeadjuk az $\displaystyle \dfrac{f(v_i)+f(v_j)}{d_i+d_j}\ge1$ egyenlőtlenséget. Az éleket mindkét irányban számolva,

$$\begin{gather*} \sum_{i=1}^n d_i =2|E| =\sum_{\substack{1\le i,j\le n\\\{i,j\}\in E}}1 \le\sum_{\substack{1\le i,j\le n\\\{i,j\}\in E}}\dfrac{f(v_i)+f(v_j)}{d_i+d_j} =\sum_{\substack{1\le i,j\le n\\\{i,j\}\in E}}\dfrac{f(v_i)}{d_i+d_j}+\sum_{\substack{1\le i,j\le n\\\{i,j\}\in E}}\dfrac{f(v_j)}{d_i+d_j} =\\ =2\sum_{i=1}^n \left(\sum_{\substack{1\le j\le n\\\{i,j\}\in E}} \dfrac{f(v_i)}{d_i+d_j}\right) =2\sum_{i=1}^n f(v_i)\left(\sum_{\substack{1\le j\le n\\\{i,j\}\in E}} \dfrac1{d_i+d_j}\right) \le2\sum_{i=1}^n f(v_i)\left(\sum_{\substack{1\le j\le n\\\{i,j\}\in E}} \dfrac1{d_i+1}\right) =\\ =2\sum_{i=1}^n f(v_i)\dfrac{d_i}{d_i+1} \le 2\sum_{i=1}^n f(v_i)\dfrac{n-1}{n} =\dfrac{2(n-1)}{n}\sum_{i=1}^n f(v_i), \end{gather*}$$

tehát

$\displaystyle \sum_{i=1}^n f(v_i) \ge \dfrac{n}{2(n-1)}\sum_{i=1}^n d_i. $

Statisztika:

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

A KöMaL 2026. januári matematika feladatai

Már regisztráltál?
Új vendég vagy?