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 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 {K1,4, C4 U K1}, 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 SinogowitzCollatz, L. and Sinogowitz, U. "Spektren endlicher Grafen." Abh. Math. Sem. Univ. Hamburg 21, 63–77, 1957. 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.Schwenk, A. J. "Almost All Trees are Cospectral" In: New Directions in the Theory of Graphs (F. Harary, Ed.), Academic Press, New York, 1973, pp. 275–307.
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:
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.Definition 2.1 in
Cheeger-egyenlőtlenség Ha a G gráf d-reguláris, kapcsolat van a h(G) Cheeger-szám és a d − λ2, 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 szerintTheorem 2.4 in
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.Eigenspaces of Graphs, by Dragoš Cvetković, Peter Rowlinson, Slobodan Simić (1997) A Cvetković, Doob és Sachs hármasa által írt, 1980-ban kiadott monográfia, a Spectra of GraphsDragoš M. Cvetković, Michael Doob, Horst Sachs, Spectra of Graphs (1980) 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
Jegyzetek
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
[chapter from Combinatorial Scientific Computing] [presented at FOCS 2007 Conference] [course page and lecture notes] [first 4 chapters are available]