Teoria espectral de grafs
En matemàtiques, la teoria de grafs espectrals és l'estudi de les propietats d'un graf en relació amb el polinomi característic, els valors propis i els vectors propis de les matrius associades al graf, com ara la seva matriu d'adjacència o la matriu laplaciana.
La matriu d'adjacència d'un gràfic simple no dirigit és una matriu simètrica real i, per tant, és diagonalitzable ortogonalment ; els seus valors propis són nombres enters algebraics reals.
Tot i que la matriu d'adjacència depèn de l'etiquetatge del vèrtex, el seu espectre és un gràfic invariant, encara que no és complet.
La teoria de grafs espectrals també s'ocupa dels paràmetres de gràfics que es defineixen mitjançant multiplicitats de valors propis de matrius associades al gràfic, com ara el nombre de Colin de Verdière.[1]
Esquema històric
[modifica]La teoria dels grafs espectrals va sorgir a les dècades de 1950 i 1960. A més de la investigació teòrica de grafs sobre la relació entre les propietats estructurals i espectrals dels gràfics, una altra font important va ser la investigació en química quàntica, però les connexions entre aquestes dues línies de treball no es van descobrir fins molt més tard. La monografia de 1980 Spectra of Graphs de Cvetković, Doob i Sachs va resumir gairebé totes les investigacions realitzades fins ara a la zona. El 1988 va ser actualitzat per l'enquesta Recent Results in the Theory of Graph Spectra.[2] La 3a edició de Spectra of Graphs (1995) conté un resum de les contribucions més recents al tema. L'anàlisi geomètrica discreta creada i desenvolupada per Toshikazu Sunada a la dècada de 2000 s'ocupa de la teoria de grafs espectrals en termes de laplacians discrets associats a gràfics ponderats, i troba aplicació en diversos camps, inclosa l'anàlisi de formes. En els darrers anys, la teoria de grafs espectrals s'ha expandit a gràfics que varien en vèrtexs que sovint es troben en moltes aplicacions de la vida real.[3][4][5][6]
Gràfics cospectrals
[modifica]
Dos gràfics s'anomenen coespectrals o isoespectrals si les matrius d'adjacència dels gràfics són isoespectrals, és a dir, si les matrius d'adjacència tenen multiconjunts iguals de valors propis.
Els gràfics coespectrals no necessiten ser isomòrfics, però els gràfics isomòrfics sempre són coespectrals.
Gràfics determinats pel seu espectre
[modifica]Un gràfic es diu que està determinat pel seu espectre si qualsevol altre gràfic amb el mateix espectre que és isomorf a .
Alguns primers exemples de famílies de gràfics que es determinen pel seu espectre inclouen:
Desigualtat de Cheeger
[modifica]La famosa desigualtat de Cheeger de la geometria riemanniana té un anàleg discret que implica la matriu laplaciana; aquest és potser el teorema més important de la teoria de grafs espectrals i un dels fets més útils en aplicacions algorítmiques. S'aproxima al tall més escàs d'un gràfic a través del segon valor propi del seu laplacià.
Referències
[modifica]- ↑ «SPECTRAL GRAPH THEORY» (en anglès). [Consulta: 24 agost 2015].
- ↑ Cvetković, Dragoš M. Recent Results in the Theory of Graph Spectra (en anglès), 1988 (Annals of Discrete mathematics). ISBN 0-444-70361-6.
- ↑ Shuman, David I; Ricaud, Benjamin; Vandergheynst, Pierre Applied and Computational Harmonic Analysis, 40, 2, 3-2016, pàg. 260–291. arXiv: 1307.5708. DOI: 10.1016/j.acha.2015.02.005. ISSN: 1063-5203.
- ↑ Stankovic, Ljubisa; Dakovic, Milos; Sejdic, Ervin (en anglès) IEEE Signal Processing Magazine, 34, 4, 7-2017, pàg. 176–182. Bibcode: 2017ISPM...34..176S. DOI: 10.1109/msp.2017.2696572. ISSN: 1053-5888.
- ↑ Sakiyama, Akie; Watanabe, Kana; Tanaka, Yuichi (en anglès) IEEE Transactions on Signal and Information Processing over Networks, 2, 3, 9-2016, pàg. 230–245. DOI: 10.1109/tsipn.2016.2581303. ISSN: 2373-776X.
- ↑ Behjat, Hamid; Richter, Ulrike; Van De Ville, Dimitri; Sornmo, Leif (en anglès) IEEE Transactions on Signal Processing, 64, 22, 15-11-2016, pàg. 6017–6029. Bibcode: 2016ITSP...64.6017B. DOI: 10.1109/tsp.2016.2591513. ISSN: 1053-587X.