Spektrális gráfelmélet

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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.

Izospektrális gráfok[szerkesztés]

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 {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]

Cheeger-egyenlőtlenség[szerkesztés]

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ó[szerkesztés]

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[szerkesztés]

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.

Története[szerkesztés]

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.

Kapcsolódó szócikkek[szerkesztés]

Fordítás[szerkeszté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.

Jegyzetek[szerkesztés]

  1. Dudás-Marx László: Gráfok spektruma (szakdolgozat). [2017. január 10-i dátummal az eredetiből archiválva]. (Hozzáférés: 2017. január 9.)
  2. Collatz, L. and Sinogowitz, U. "Spektren endlicher Grafen." Abh. Math. Sem. Univ. Hamburg 21, 63–77, 1957.
  3. Weisstein, Eric W.: {{{title}}} (angol nyelven). Wolfram MathWorld
  4. Hosoya, Haruo; Nagashima, Umpei & Hyugaji, Sachiko (1994), "Topological twin graphs. Smallest pair of isospectral polyhedral graphs with eight vertices", Journal of Chemical Information and Modeling 34 (2): 428–431, DOI 10.1021/ci00018a033.
  5. 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.
  6. Sunada, Toshikazu (1985), "Riemannian coverings and isospectral manifolds", Ann. of Math. 21: 169–186.
  7. Spectra of Graphs, 2011
  8. Definition 2.1 in (Hoory, Linial & Widgerson 2006)
  9. Alon & Spencer 2011.
  10. Theorem 2.4 in (Hoory, Linial & Widgerson 2006)
  11. a b Eigenspaces of Graphs, by Dragoš Cvetković, Peter Rowlinson, Slobodan Simić (1997) ISBN 0-521-57352-1
  12. Dragoš M. Cvetković, Michael Doob, Horst Sachs, Spectra of Graphs (1980)
  13. Recent Results in the Theory of Graph Spectra, Annals of Discrete mathematics (1988). ISBN 0-444-70361-6 
  14. Sunada, Toshikazu (2008), "Discrete geometric analysis", Proceedings of Symposia in Pure Mathematics 77: 51–86.

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[szerkesztés]