Az A. 870. feladat (2024. január)

A. 870. Egy egyszerű gráf minden élére ráírjuk az él két végpontja fokszámainak különbségét. Egy $\displaystyle N$ csúcsú gráfban legfeljebb mennyi lehet az élekre írt számok összege?

Javasolta: Lenger Dániel és Szűcs Gábor (Budapest)

(7 pont)

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

A gráfban egy $\displaystyle v$ csúcsból a nála kisebb fokú csúcsokba menő élek száma legyen $\displaystyle v_1$, a nála kisebb vagy egyenlő fokúakba menő élek száma legyen $\displaystyle v_1'$. Definiáljuk hasonlóan a nagyobb fokúakra a $\displaystyle v_2$, ill. $\displaystyle v_2'$ mennyiségeket is, legyen továbbá $\displaystyle d(v)$ a csúcs foka, ekkor $\displaystyle d(v) = v_1 + v_2' = v_1' + v_2$.

A továbbiakban olyan gráfokat vizsgálunk, ahol az élsúlyok összege maximális. A következő megfigyeléseket tehetjük ezekkel kapcsolatban:

Élbehúzás. Legyen $\displaystyle k$ és $\displaystyle n$ a gráf két össze nem kötött csúcsa, ahol $\displaystyle d(k) \leq d(n)$. Vizsgáljuk meg, hogy a $\displaystyle kn$ él behúzása esetén hogyan változik a rájuk illeszkedő élek súlya. A csúcsokból a nem nagyobb fokúak felé menő éleken eggyel nő, míg a nagyobb fokúak felé menőkön eggyel csökken. A változás tehát $\displaystyle n_1'+ k_1' - n_2 - k_2$. Továbbá a behúzott él súlya $\displaystyle d(n)-d(k)$. Így az élsúlyok változása:

$\displaystyle d(n)-d(k) + n_1'+ k_1' - n_2 - k_2 = n_1' + n_2 - k_1' - k_2 + n_1'+ k_1' - n_2 - k_2 = 2(n_1' - k_2).$

Mivel nem növelhetjük az élsúlyok összegét, ezért: $\displaystyle 2(n_1' - k_2) \leq 0$, azaz $\displaystyle n_1' \leq k_2$.

Éltörlés. Legyen $\displaystyle k$ és $\displaystyle n$ a gráf két összekötött csúcsa, ahol $\displaystyle d(k) \leq d(n)$. Vizsgáljuk meg, hogy a $\displaystyle kn$ él törlése esetén hogyan változik a rájuk illeszkedő élek súlya. A csúcsokból a nem kisebb fokúak felé menő éleken eggyel nő, míg a kisebb fokúak felé menőkön eggyel csökken. A változás tehát $\displaystyle n_2' + k_2' - n_1 - k_1$. Továbbá a törölt él súlya $\displaystyle d(n)-d(k)$ volt. Így az élsúlyok változása:

$\displaystyle d(k) - d(n) + n_2' + k_2' - n_1 - k_1 = k_1 + k_2' - n_1 - n_2' + n_2'+ k_2' - n_1 - k_1 = 2(k_2' - n_1).$

Mivel nem növelhetjük az élsúlyok összegét, ezért: $\displaystyle 2(k_2' - n_1) \leq 0$, azaz $\displaystyle k_2' \leq n_1$.

Cseresznye. Legyen a gráf három csúcsa $\displaystyle u, t, a$, ahol $\displaystyle ua$ nem-él, míg $\displaystyle ta$ él, továbbá $\displaystyle d(u), d(t) \leq d(a)$. Az élbehúzási feltétel $\displaystyle ua$-ra: $\displaystyle a_1' \leq u_2$, míg az éltörlési feltétel $\displaystyle ta$-ra: $\displaystyle t_2' \leq a_1$. A kettőt összeolvasva azt kapjuk, hogy $\displaystyle t_2' \leq a_1 \leq a_1' \leq u_2$, azaz $\displaystyle t_2' \leq u_2$.

Fordított cseresznye. Legyen a gráf három csúcsa $\displaystyle m, u, t$, ahol $\displaystyle mu$ nem-él, míg $\displaystyle mt$ él, továbbá $\displaystyle d(m) \leq d(u), d(t)$. Az élbehúzási feltétel $\displaystyle mu$-ra: $\displaystyle u_1' \leq m_2$, míg az éltörlési feltétel $\displaystyle mt$-ra: $\displaystyle m_2' \leq t_1$. A kettőt összeolvasva azt kapjuk, hogy $\displaystyle u_1' \leq m_2 \leq m_2' \leq t_1$, azaz $\displaystyle u_1' \leq t_1$.

Partíció a minimális fokszámból. Legyen a gráf (egyik) minimális fokszámú csúcsa $\displaystyle m$. Feltehető, hogy $\displaystyle 0<d(m)$: ha behúzunk egy élt egy izolált pontból, a súlyok összege nem csökken. Legyen $\displaystyle A$ az $\displaystyle m$-mel össze nem kötött, míg $\displaystyle B$ az $\displaystyle m$-mel összekötött csúcsok halmaza. Ekkor a fordított cseresznye részbeli érvelés szerint minden $\displaystyle a \in A$, $\displaystyle b \in B$ párra igaz, hogy $\displaystyle a_1' \leq b_1$.

Tegyük fel, hogy létezik olyan $\displaystyle n \in A$, $\displaystyle k \in B$, amelyekre $\displaystyle d(n) > d(k)$. Tudjuk, hogy $\displaystyle n_1' \leq k_1$. Mivel $\displaystyle d(n) > d(k)$, ezért van olyan $\displaystyle x$ csúcs, amely $\displaystyle n$-nel össze van kötve, de $\displaystyle k$-val nem. $\displaystyle d(x)$ nagysága szerint három eset képzelhető el:

• $\displaystyle d(x) \geq d(n)$. Ekkor $\displaystyle k, n, x$-re alkalmazva a cseresznyebeli feltételt: $\displaystyle n_2' \leq k_2$. Ez ellentmond a $\displaystyle d(n) > d(k)$ feltevésnek, hiszen $\displaystyle d(n)=n_1'+n_2\leq n_1'+n_2'\leq k_1+k_2\leq k_1'+k_2=d(k)$.
• $\displaystyle d(k) < d(x) < d(n)$. Ekkor $\displaystyle m - k - x - n$ egy alternáló kört alkot ($\displaystyle mk$ él, $\displaystyle kx$ nem-él, $\displaystyle xn$ él, $\displaystyle nm$ nem-él). Cseréljük ki a kör éleit nem-élekre, míg a nem-éleit élekre. Ekkor a fokszámok nem változnak, sőt a körön belül nő az élsúly, hiszen $\displaystyle (d(n)-d(x)) + (d(k)-d(m)) < (d(n)-d(m)) + (d(x)-d(k))$.
• $\displaystyle d(x) \leq d(k)$. Ekkor $\displaystyle m - k - x - n$ egy alternáló kört alkot ($\displaystyle mk$ él, $\displaystyle kx$ nem-él, $\displaystyle xn$ él, $\displaystyle nm$ nem-él). Cseréljük ki a kör éleit nem-élekre, míg a nem-éleit élekre. Ekkor a fokszámok nem változnak, a körön belül pedig állandó marad az élsúlyok összege, hiszen $\displaystyle (d(n)-d(x)) + (d(k)-d(m)) = (d(n)-d(m)) + (d(k)-d(x))$. Viszont így $\displaystyle n$ és $\displaystyle k$ helyet cserélt a partícióban, azaz ilyen lépésekkel elérhető, hogy az $\displaystyle A$ halmazban lévő csúcsok fokszámai ne haladják meg a $\displaystyle B$ halmazban szereplő csúcsok fokszámait.

Tehát feltehetjük azt, hogy minden $\displaystyle a \in A$, $\displaystyle b \in B$ párra igaz, hogy $\displaystyle d(a) \leq d(b)$.

Vizsgáljuk meg azt, hogy lehet-e él $\displaystyle A$-ban. Tegyük fel, hogy $\displaystyle p,q\in A$, $\displaystyle pq$ él, és $\displaystyle d(p)\leq d(q)$. Ekkor a fordított cseresznye érvelés miatt, $\displaystyle p$ a $\displaystyle B$ halmaz minden csúcsával is össze van kötve (hiszen $\displaystyle q_1 \leq b_1$). Másrészt a cseresznye érvelést alkalmazva az $\displaystyle m, p, q$ hármasra adódik, hogy $\displaystyle |B| + 1 \leq p_2' \leq m_2 = |B|$. Ez ellentmondás, tehát $\displaystyle A$-n belül nincsen él.

Így $\displaystyle m$ csak akkor lehet minimális, ha az $\displaystyle A$ halmaz minden eleme össze van kötve $\displaystyle B$ halmaz minden elemével.

Lehetséges-e, hogy $\displaystyle B$-n belül fut nem-él? Tegyük fel, hogy $\displaystyle r,s \in B$, ahol $\displaystyle rs$ nem-él, és $\displaystyle d(r)\leq d(s)$. Ekkor a fordított cseresznye érvelés miatt $\displaystyle m, r, s$-re teljesülnie kell, hogy $\displaystyle [B| = m_2' \leq r_2 \leq |B|-1$. De ez persze ellentmondás.

Így tehát van olyan maximális gráf, melynek a szerkezete olyan, hogy egy teljes gráf minden csúcsa össze van kötve egy üres gráf minden csúcsával. Innen pedig már könnyen kijön a maximum: ha a teljes gráf mérete $\displaystyle X>0$, az üresé pedig $\displaystyle Y>0$, ahol $\displaystyle X+Y=N$, akkor a súlyok összege

$\displaystyle X(X-1)/2 \cdot 0 + XY \cdot (Y-1)=XY(Y-1).$

Hasonlítsuk össze $\displaystyle XY(Y-1)$-et és $\displaystyle (X-1)(Y+1)Y$-t: a különbségük $\displaystyle (2X-Y-1)Y$, azaz $\displaystyle Y$ növelésével addig nő a szorzat, amíg $\displaystyle Y+1<2X$, azaz $\displaystyle N+1<3X$ és $\displaystyle 3Y<2N-1$. Innen könnyen adódik, hogy a maximumot $\displaystyle X=\lfloor \frac{N+1}{3} \rfloor$, $\displaystyle Y=\lceil \frac{2N-1}{3} \rceil$ esetén érjük el (ha $\displaystyle N$ hármas maradéka 2, akkor két jó pár is van).

Statisztika:

12 dolgozat érkezett.
7 pontot kapott:	Duchon Márton, Varga Boldizsár, Wiener Anna.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2024. januári matematika feladatai