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ó.[1]
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.
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[2][3] 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.[4]
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.[5]
Az izospektrális gráfok konstruálásának egyik lehetősége a Szunada-módszer alkalmazása.[6]
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.[7]
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.[8]
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[9] által kimondott egyenlőtlenség szerint[10]
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.
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.[11] A Cvetković, Doob és Sachs hármasa által írt, 1980-ban kiadott monográfia, a Spectra of Graphs[12] 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.[13] A Spectra of Graphs 1995-ös harmadik kiadása további kutatásokat összegez.[11] 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,[14] számos felhasználási területet nyerve, köztük a spektrális alakfelismerést.
- 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
- 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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
