Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 4218. feladat (2009. november)

B. 4218. Mekkora lehet a legrövidebb kör hossza egy olyan gráfban, amelyben egyetlen csúcs sincs összekötve az összes többivel, bármely két éllel össze nem kötött csúcsnak van közös szomszédja, és ha a csúcsok számát \(\displaystyle n\)-nel jelöljük, akkor a fokszámok négyzetösszege \(\displaystyle n^2-n\)?

Javasolta: Montágh Balázs (Memphis)

(5 pont)

A beküldési határidő 2009. december 10-én LEJÁRT.


Megoldás. A legrövidebb kör hossza legfeljebb 5. Tegyük fel ugyanis, hogy a legrövidebb kör hossza \(\displaystyle k\ge 6\), és legyen \(\displaystyle C=v_1v_2\ldots v_kv_1\) egy ilyen kör. Ekkor a gráf élei között \(\displaystyle v_1v_3, v_1v_4\) és \(\displaystyle v_2v_4\) nem szerepelhet. A feltétel miatt a \(\displaystyle v_1,v_4\) csúcsoknak kell legyen egy \(\displaystyle v\) közös szomszédjuk, de az nem lehet sem \(\displaystyle v_2\), sem pedig \(\displaystyle v_3\), tehát \(\displaystyle v_1v_2v_3v_4vv_1\) egy \(\displaystyle k\)-nál rövidebb kör a gráfban, ami ellentmondás. Az alábbiakban megmutatjuk, hogy a gráf sem háromszöget, sem négyszöget nem tartalmazhat, vagyis a legrövidebb kör hossza csakis 5 lehet.

Tekintsük az összes olyan \(\displaystyle (u,v,w)\) rendezett hármast, ahol \(\displaystyle u,v,w\) a gráf olyan páronként különböző csúcsai, melyekre \(\displaystyle uv\) és \(\displaystyle vw\) egyaránt élei a gráfnak, \(\displaystyle uw\) azonban nem. Ezeknek a száma legyen \(\displaystyle K\). A gráf csúcsait jelölje \(\displaystyle v_1,v_2,\ldots,v_n\), a \(\displaystyle v_i\) csúcs fokszámát pedig \(\displaystyle d_i\). Ekkor a feltétel szerint

\(\displaystyle \sum_{i=1}^nd_i^2=n^2-n.\)

Vizsgáljuk meg először azt, hogy a \(\displaystyle v_i\) csúcs hány ilyen rendezett hármasban szerepelhet, mint a középső \(\displaystyle v\) csúcs. Mivel ekkor \(\displaystyle u\) és \(\displaystyle w\) a \(\displaystyle v_i\) csúcs különböző szomszédai, az ilyen hármasok száma legfeljebb \(\displaystyle d_i(d_i-1)\), a becslés pedig éppen akkor pontos, ha \(\displaystyle v_i\) szomszédai közül semelyik kettő nincs éllel összekötve. Ennek alapján azt kapjuk, hogy

\(\displaystyle K\le \sum_{i=1}^n(d_i^2-d_i)=(n^2-n)-\sum_{i=1}^nd_i,\)

ahol egyenlőség pontosan akkor teljesül, ha a gráf nem tartalmaz háromszöget.

Most nézzük meg azt, hogy a \(\displaystyle v_i\) csúcs hány rendezett hármasban szerepel első \(\displaystyle u\) elemként. Ekkor a \(\displaystyle w\) elem csak azon \(\displaystyle n-1-d_i\) csúcs közül kerülhet ki, melyek \(\displaystyle v_i\)-vel nem szomszédosak, másrészt viszont minden ilyen \(\displaystyle w\) csúcshoz találhatunk alkalmas \(\displaystyle v\) elemet is \(\displaystyle u=v_i\) szomszédai közül, hiszen bármely két éllel össze nem kötött csúcsnak van közös szomszédja. Ezért az ilyen hármasok száma legalább \(\displaystyle n-1-d_i\), és pontosan akkor nem több, ha bármely olyan \(\displaystyle w\) csúcsra, mely \(\displaystyle v_i\)-vel nem szomszédos, az \(\displaystyle w\) és \(\displaystyle v_i\) csúcsoknak pontosan egy közös szomszédja van. Ennek alapján azt kapjuk, hogy

\(\displaystyle K\ge \sum_{i=1}^n(n-1-d_i)=(n^2-n)- \sum_{i=1}^nd_i,\)

ahol egyenlőség pontosan akkor teljesül, ha bármely két éllel össze nem kötött csúcsnak csak egy közös szomszédja van, vagyis ha a gráf nem tartalmaz négy hosszúságú kört.

A két megállapítást összevetve látható, hogy szükségképpen

\(\displaystyle K=(n^2-n)- \sum_{i=1}^nd_i,\)

a gráf pedig sem háromszöget, sem négyszöget nem tartalmazhat. Ezzel korábbi állításunkat beláttuk, a gráfban a legrövidebb kör hossza 5. Ilyen gráfra legegyszerűbb példa az ötszög gráf, de könnyen ellenőrizhetjük, hogy az ún. Petersen-gráf is kielégíti a feladat feltételeit.


Statisztika:

7 dolgozat érkezett.
5 pontot kapott:Ágoston Tamás, Damásdi Gábor, Éles András, Mester Márton, Mészáros András, Strenner Péter.
4 pontot kapott:Perjési Gábor.

A KöMaL 2009. novemberi matematika feladatai