Spektrális gráfelmélet

A matematika területén a spektrális gráfelmélet a gráfok tulajdonságainak vizsgálata azok mátrixai (szomszédsági vagy Laplace-mátrix) karakterisztikus polinomjainak, sajátértékeinek, sajátvektorainak tükrében. A spektrális gráfelmélet szoros kapcsolatban áll a matematika más területeivel, így a differenciálgeometriával, véletlen bolyongásokkal, Markov-láncokkal is, de fontos gyakorlati alkalmazásai is vannak: VLSI-áramkörök gyártása, fehérjeláncok vagy ismeretségi hálózatok felderítése, képszegmentáció.

Egy irányítatlan gráf szomszédsági mátrixa szimmetrikus, ezért sajátértékei (a gráf spektrumát adó multihalmaz) valós számok és léteznek ortonormális sajátvektorai.

Bár a szomszédsági mátrix függ a csúcsok címkéitől, spektruma gráfinvariáns.

A spektrális gráfelmélet olyan gráfparaméterekkel is foglalkozik, melyeket a gráf valamely kapcsolódó mátrixa sajátértékeinek multiplicitása határoz meg, ilyen például a Colin de Verdière-szám.

Izospektrális gráfok

Két gráf akkor izospektrális vagy kospektrális, ha adjacenciamátrixaikhoz azonos spektrum (sajátérték-multihalmaz) tartozik.

Két izospektrális kilenc lap határolta test, a lehetséges izospektrális poliédergráfok közül a legkisebb.

Két izospektrális gráf nem feltétlenül izomorf, de két izomorf gráf mindig izospektrális. A legkisebb izospektrális irányítatlan gráfpáros a {K_1,4, C₄ U K₁}, ami az 5 csúcsú csillaggráf, valamint a 4 csúcsú körgráf és az egyetlen csúcsból álló gráf diszjunkt uniója, ahogy azt Collatz és Sinogowitz 1957-ben megállapították. A legkisebb izospektrális poliédergráf-páros nyolc csúcsú, kilenc lap határolta testekből áll.

Csaknem minden fa kospektrális, tehát az n csúcsú fák között a kospektrális fák aránya n növekedésével tart 1-hez.

Az izospektrális gráfok konstruálásának egyik lehetősége a Szunada-módszer alkalmazása.

Az izospektrális gráfok másik fontos forrásai a pont-egyenes geometriák pont-kollinearitási gráfjai és egyenes-metszetgráfjai. Ezek a gráfok mindig izospektrálisak, de gyakran nem izomorfak.

Cheeger-egyenlőtlenség

A Riemann-geometria híres Cheeger-egyenlőtlensége rendelkezik Laplace-mátrixszal kapcsolatos diszkrét analógiával; ez talán a spektrális gráfelmélet legfontosabb tétele, és az egyik legfontosabb, algoritmusokban jól használható információ. A gráfok legritkább vágását a Laplace-mátrixuk második sajátértékén keresztül approximálja.

Cheeger-állandó

Egy gráf Cheeger-állandója (más néven a hozzá tartozó bővülési hányados, Cheeger-szám vagy izoperimetrikus szám) annak a mértéke, hogy az adott gráf mennyiben rendelkezik „szűk keresztmetszettel”. Ez a szűk keresztmetszetűséget jellemző Cheeger-állandó számos területen lehet érdekes: például jól összekötött számítógép-hálózatok tervezésekor, kártyapakli keverésekor és az alacsony dimenziós topológiában (különösen a hiperbolikus 3-sokaságoknál).

Formálisabban, egy n csúcsú G gráfhoz tartozó h(G) Cheeger-állandó meghatározása:

$h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}},$

ahol S legalább n/2 csúcsú nem üres részhalmazain számítunk minimumot, és ahol ∂(S) az S csúcshalmaz határa, azaz olyan élhalmaz, mely minden elemének pontosan egy végpontja van S-ben.

Cheeger-egyenlőtlenség

Ha a G gráf d-reguláris, kapcsolat van a h(G) Cheeger-szám és a d − λ₂, G spektrális rése között. A Dodziuk, és tőle függetlenül Nógá Álón és Milman által kimondott egyenlőtlenség szerint

${\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.$

Az egyenlőtlenség közeli kapcsolatban van a Markov-láncokra vonatkozó Cheeger-korláttal, és felfogható a Riemann-geometria Cheeger-egyenlőtlensége diszkrét eseteként is.

Története

A spektrális gráfelmélet az 1950-es, 1960-as években bukkant fel. A gráfok strukturális és spektrális tulajdonságai közötti kapcsolatot kutató, nyilvánvaló gráfelméleti gyökerek mellett az új elmélet sokat merített a kvantumkémiából is, bár a két terület közötti szoros kapcsolatokat csak jóval később tárták föl. A Cvetković, Doob és Sachs hármasa által írt, 1980-ban kiadott monográfia, a Spectra of Graphs a terület szinte összes addigi eredményét összefoglalja. 1988-ban frissítették a Recent Results in the Theory of Graph Spectra átfogó elemzésükben. A Spectra of Graphs 1995-ös harmadik kiadása további kutatásokat összegez. A 2000-es években Szunada Tosikazu által kifejlesztett diszkrét geometriai analízis a spektrális gráfelméletet súlyozott gráfok Laplace-mátrixainak tükrében vizsgálja, számos felhasználási területet nyerve, köztük a spektrális alakfelismerést.

Kapcsolódó szócikkek

• Erősen reguláris gráf
• Algebrai összefüggőség
• Algebrai gráfelmélet
• Spektrális klaszterezés
• Estrada-index
• Lovász-féle theta-függvény (Lovász-szám)
• Expandergráf

Fordítás

• Ez a szócikk részben vagy egészben a Spectral graph theory című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Források

• J.Dodziuk, Difference Equations, Isoperimetric inequality and Transience of Certain Random Walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787-794.

További információk

• Spectra of Graphs, 2011
• Spectral Graph Theory, 2011 [chapter from Combinatorial Scientific Computing]
• Spectral Graph Theory and its Applications, 2007 [presented at FOCS 2007 Conference]
• Spectral Graph Theory and its Applications, 2004 [course page and lecture notes]
• Spectral Graph theory  [first 4 chapters are available]