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