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 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 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:
 
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 − λ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 szerint

 

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

Jegyzetek

14. 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]
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 azcsúcsú csillaggráf , valamint acsúcsú körgráf és az egyetlen csúcsból álló gráf diszjunkt uniója , ahogy azt Collatz és Sinogowitzben 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 tarthez . 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 hiperbolikussokasá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 . 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 szerint 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 azes , 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, ban kiadott monográfia , a Spectra of Graphs a terület szinte összes addigi eredményét összefoglalja.ban frissítették a Recent Results in the Theory of Graph Spectra átfogó elemzésükben . A Spectra of Graphsös harmadik kiadása további kutatásokat összegez . Aes é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 14. J.Dodziuk , Difference Equations , Isoperimetric inequality and Transience of Certain Random Walks , Trans . Amer . Math . Soc.( 1984 ) , no . További információk [ chapter from Combinatorial Scientific Computing ] [ presented at FOCSConference ] [ course page and lecture notes ] [ firstchapters are available ]