Spektralna teorija grafov

Iz Wikipedije, proste enciklopedije

Spektralna teorija grafov je veja teorije grafov. Raziskuje značilnosti grafov v povezavi s karakterističnimi polinomi, lastnimi vrednostmi in lastnimi vektorji njihovih matrik sosednosti ali Laplaceovih matrik.

Neusmerjeni graf ima simetrično matriko sosednosti in zato realne lastne vrednosti (večkratno množico, ki se imenuje spekter grafa) in polno množico ortonormalnih lastnih vektorjev.

Matrika sosednosti je odvisna od označitve točk grafa, spekter pa je invarianta grafa.