Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

9.5. Szép gráfok

9.5. Szép gráfok

Ebben a pontban egy meglepő és szép gráfelméleti tételt igazolunk, az eddigieknél egy kicsit több lineáris algebra felhasználásával. Viccesen azonban akár úgy is fogalmazhatnánk, hogy mindennek az az oka, hogy a 15-nek a természetes számok körében nincs más osztója, mint az 1, a 3, az 5 és a 15.

Tekintsünk egy olyan (hurokél és többszörös él nélküli véges) gráfot, amelyben nincs ötnél rövidebb kör és minden csúcsból d él indul ki. Hány csúcsa lehet egy ilyen gráfnak?

Vegyünk egy tetszőleges csúcsot. Ebből d él indul ki, tehát újabb d csúcsot kapunk. Az új csúcsok mindegyikéből d–1 újabb él indul ki. Sem két ilyen él, sem a végpontjaik nem eshetnek egybe, mert akkor egy 3, illetve 4 hosszúságú körhöz jutnánk. Az élek végpontjai tehát újabb d(d–1) csúcsot adnak. A gráfnak így összesen legalább d2+1 csúcsa van.

Milyen d-kre állhat itt egyenlőség? Nyilván d=1 és d=2 megfelel (a gráf ekkor egyetlen él, illetve egy öt hosszúságú kör). Kicsit nehezebb d=3-ra egy jó gráfot mutatni, de van ilyen, az ún. Petersen-gráf (lásd a 9.5.1 feladatot). Viszont d=4, 5 és 6 egyike sem jó, amint ez növekvő nehézségű számolásokkal igazolható. Bravúros módon A. J. Hoffman és R. R. Singleton 1960-ban d=7-re ismét találtak egy jó gráfot; ezt egy csomó Petersen-gráf összeragasztásával nyerték. És mi a helyzet nagyobb d-kre?

9.5.1 Tétel (Hoffman-Singleton-tétel)

Tegyük fel, hogy egy gráf minden csúcsából d él indul ki, a gráfban nincs ötnél rövidebb kör és a gráfnak d2+1 csúcsa van. Ekkor d értéke csak 1, 2, 3, 7 vagy 57 lehet.❶

Megjegyzés: Nem tudjuk, hogy d=57-re valóban létezik-e ilyen gráf.

Bizonyítás: Egy n csúcsú gráf szomszédsági (adjacencia) mátrixán azt az n×n-es A mátrixot értjük, amelyben

Könnyen látható, hogy egy gráf szomszédsági mátrixát négyzetre emelve a kapott B=A2 mátrixban βij éppen az i-edik és j-edik csúcs közös szomszédainak a száma.

Vegyünk most egy, a tétel feltételeit kielégítő n=d2+1 csúcsú G gráfot. A tétel kimondása előtti meggondolásokból adódik, hogy G-ben bármely két csúcs vagy szomszédos, vagy pedig pontosan egy közös szomszédjuk van. Ezért a G gráf n×n-es A szomszédsági mátrixára az

(1)

mátrixegyenlet teljesül, ahol E az (n×n-es) egységmátrix, J pedig a csupa 1-ből álló mátrix.

Mivel A szimmetrikus mátrix, ezért n=d2+1 független sajátvektora van (az Rn euklideszi térben, sőt ezek páronként ortogonálisak is). Az (1) mátrixegyenletből könnyen adódik, hogy ha v_ sajátvektora A-nak λ sajátértékkel, akkor v_ sajátvektora J-nek is, éspedig

(2)

sajátértékkel. Mivel a J-nek az n egyszeres sajátértéke, és minden további sajátértéke 0, ezért az A-nak (2) alapján a d egyszeres sajátértéke (ami közvetlenül is adódott volna), a további sajátértékei pedig kielégítik a λ2+λ–(d–1)=0 egyenletet. Ezt megoldva kapjuk, hogy A további sajátértékei

multiplicitásuk m1, illetve m2, ahol

(3)

Írjuk fel az A mátrix nyomát. Ez egyrészt a főátlóbeli elemek összege, azaz 0, másrészt a sajátértékek (multiplicitással vett) összege. Tehát

(4)

adódik. Ez csak úgy teljesülhet, ha m1=m2 vagy pedig s=4d-3 egész szám.

Az első esetben (3)-ból és (4)-ből kapjuk, hogy d2=2d, azaz d=2. A második esetben a d=(s2+3)/4 összefüggést (4)-be beírva

adódik. Vagyis s osztója a 15-nek, tehát s=1, 3, 5 vagy 15. Innen d=1, 3, 7 vagy 57.❷

Feladatok

Gráfon a továbbiakban is hurokél és többszörös él nélküli véges gráfot értünk. Egy csúcs foka a csúcsból kiinduló élek száma. Egy gráf reguláris, ha minden csúcs foka ugyanannyi.

Egy gráf spektruma a szomszédsági mátrix sajátértékeinek a halmaza.

Legyen egy G gráfnak n csúcsa és m éle. A G gráf illeszkedési (incidencia) mátrixának azt az n×m-es C mátrixot nevezzük, amelyben γij=1, ha az i-edik csúcs illeszkedik a j-edik élre, és 0 egyébként.

9.5.1 A Petersen-gráf a következőképpen néz ki: Vegyük egy szabályos ötszög csúcsait, és ezt az öt pontból álló alakzatot a középpontból kicsinyítsük le (pl. fele méretűre). A külső pontok közül kössük össze a szomszédosakat (azaz ekkor egy szabályos ötszöget kapunk), a belső pontok mindegyikét kössük össze a másodszomszédaival (így egy csillagötszöget kapunk), végül mindegyik külső pontot kössük össze a neki megfelelő belső ponttal. Az így kapott gráfnak 10 csúcsa és 15 éle van.

a) Ellenőrizzük, hogy ebben a gráfban valóban nincs ötnél rövidebb kör és minden csúcs foka 3.

b) Adjuk meg a Petersen-gráf spektrumát.

9.5.2 Egy gráf csúcsaihoz rendeljük hozzá rendre az x1,…, xn valós (vagy komplex) számokat. Mutassuk meg, hogy az x_=x1xn nemnulla vektor akkor és csak akkor sajátvektora a gráf szomszédsági mátrixának, ha bármely csúcsnál a szomszédaihoz rendelt xi számok összege ugyanannyiszorosa a csúcshoz rendelt számnak.

9.5.3 Határozzuk meg az alábbi n csúcsú gráfok spektrumát:

a) n csúcsú teljes gráf;

b) n=2k, és minden csúcsnak pontosan egy szomszédja van (ekkor a gráf diszjunkt élek egyesítése, ún. egyfaktor);

c) n=2k, az a1,…, ak csúcsok mindegyike össze van kötve a b1,…, bk csúcsok mindegyikével, és más él nincs (teljes páros gráf);

d) n–1 élű csillag (azaz a középpont a többi n–1 pont mindegyikével össze van kötve, és más él nincs);

*e) n hosszúságú kör.

9.5.4 Milyen kapcsolatban áll egy reguláris gráf spektruma a gráf komplementerének a spektrumával?

M*9.5.5 Legyen a G gráf szomszédsági mátrixa A. Mutassuk meg, hogy akkor és csak akkor van olyan f polinom, amelyre f(A)=J, ha G összefüggő és reguláris (J a csupa 1-ből álló mátrix).

9.5.6 Írjuk fel a 9.5.1 és 9.5.3 feladatokban szereplő gráfok illeszkedési mátrixát.

9.5.7 Legyen a G gráf illeszkedési mátrixa C. Mi a CTC, illetve CCT mátrixok elemeinek a kombinatorikai jelentése?

9.5.8 Melyek azok a gráfok, amelyeknél a(z alkalmasan választott) szomszédsági és illeszkedési mátrix egybeesik?

9.5.9 Legyen Λ a G gráf legnagyobb sajátértéke, δ és Δ pedig a G-ben előforduló legkisebb, illetve legnagyobb fokszám. Bizonyítsuk be, hogy δ≤Λ≤Δ.

M*9.5.10 Legyen Λ a G gráf legnagyobb sajátértéke. Mutassuk meg, hogy G csúcsai kiszínezhetők (legfeljebb) Λ+1 színnel úgy, hogy bármely él két végpontja különböző színű.