Spektrális gráfelmélet

Innen: testwiki
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

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

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ó

Sablon:Fő 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)=min0<|S|≤n2|∂(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.[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 MilmanSablon:Sfn által kimondott egyenlőtlenség szerint[9]

12(d−λ2)≤h(G)≤2d(d−λ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.[10] A Cvetković, Doob és Sachs hármasa által írt, 1980-ban kiadott monográfia, a Spectra of Graphs[11] 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.[12] A Spectra of Graphs 1995-ös harmadik kiadása további kutatásokat összegez.[10] 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,[13] számos felhasználási területet nyerve, köztük a spektrális alakfelismerést.

Kapcsolódó szócikkek

Fordítás

Jegyzetek

Sablon: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

  1. ↑ Sablon:Cite web
  2. ↑ Collatz, L. and Sinogowitz, U. "Spektren endlicher Grafen." Abh. Math. Sem. Univ. Hamburg 21, 63–77, 1957.
  3. ↑ Sablon:Mathworld
  4. ↑ Sablon:Citation.
  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. ↑ Sablon:Citation.
  7. ↑ Sablon:Cite web
  8. ↑ Definition 2.1 in Sablon:Harvtxt
  9. ↑ Theorem 2.4 in Sablon:Harvtxt
  10. ↑ 10,0 10,1 Eigenspaces of Graphs, by Dragoš Cvetković, Peter Rowlinson, Slobodan Simić (1997) Sablon:ISBN
  11. ↑ Dragoš M. Cvetković, Michael Doob, Horst Sachs, Spectra of Graphs (1980)
  12. ↑ Sablon:Cite book
  13. ↑ Sablon:Citation.
A lap eredeti címe: „https://hu.wiki.beta.math.wmflabs.org/w/index.php?title=Spektrális_gráfelmélet&oldid=3614”