Espectro gráfico

Un espectro de gráfico es un conjunto de valores propios de la matriz de adyacencia de un gráfico.

El espectro se puede definir tanto para un grafo simple como para un dígrafo , multigrafo , seudografo o pseudomultigrafo .

Definiciones

Sea un grafo donde hay un conjunto de sus vértices y hay un conjunto de sus aristas . El número cardinal es el número de vértices en el gráfico. ${\ estilo de visualización \ Gamma (V, E)}$ ${\ estilo de visualización V (\ gamma)}$ ${\ estilo de visualización v \ en V (\ Gamma)}$ ${\ estilo de visualización E (\ gamma)}$ ${\ estilo de visualización e \ en E (\ Gamma)}$ $n=|V(\Gamma )|$

Los vértices adyacentes del gráfico son vértices y tales que , en otras palabras, ambos vértices son terminales para una arista. $\Gama$ $v_{1}$ $v_{2}$ ${\ estilo de visualización \ izquierda \ {v_ {1}, v_ {2} \ derecha \} \ en E (G)}$

La matriz de adyacencia para un gráfico simple es [1] una matriz de tamaño donde: $\Gama$ ${\matemáticas A}$ $n\veces n$

a_{i,j}={\begin{cases}1&:\,\left\{v_{i},v_{j}\right\}\in E(G),\\0&:\, \left\{v_{i},v_{j}\right\}\notin E(G)\end{casos}}

es decir, el elemento de la matriz es igual a uno si los vértices y son adyacentes, e igual a cero si no, y . $a_{i,j}$ $v_{i}$ $v_{j}$ $a_{i,i}=0$

Para un seudógrafo , un elemento es igual al doble del número de bucles adjuntos a un vértice [2] . También es posible contar bucles una vez. El bucle orientado se tiene en cuenta una vez [2] . ${\ Displaystyle a_ {yo, yo}}$ $v_{i}$

Para un multigrafo , un elemento es igual al número de aristas múltiples . $a_{i,j}$ $e=\izquierda\{v_{i},v_{j}\derecha\}$

El polinomio característico de un grafo es el polinomio característico de su matriz de adyacencia : $P_{G}(\lambda)$ $det(\lambda \mathbf {I} -\mathbf {A} )=0$

P_{G}(\lambda )=\lambda ^{n}+c_{1}\lambda ^{n-1}+c_{2}\lambda ^{n-2}+c_{3}\ lambda ^{n-3}+\puntos +c_{n}

El vector propio del gráfico es el vector propio de la matriz de adyacencia: ${\matemáticas x}$

\mathbf {A} \mathbf {x} =\lambda \mathbf {x}

Definiciones del espectro de un gráfico

En [3] , el espectro de un gráfico se define como el conjunto de valores propios del polinomio característico del gráfico (o valores propios del gráfico ), donde y las multiplicidades de estos números $\lambda _{i}$ ${\displaystyle \lambda _{0}\leqslant \lambda _{1}\leqslant \dots \leqslant \lambda _{s))$ ${\ estilo de visualización m (\ lambda _ {i})}$

Spec(\Gamma)={\begin{pmatrix}\lambda_{0}&\lambda_{1}&\dots &\lambda_{s-1}\\m(\lambda_{0} )&m(\lambda _{1})&\puntos &m(\lambda _{s-1})\end{pmatriz}}

En [4] , el espectro de un gráfico se define simplemente como el conjunto de valores propios:

Sp(\Gamma )=\left[\lambda _{1},\,\lambda _{2},\,\dots,\,\lambda _{n}\right]

Propiedades

Los coeficientes del polinomio característico del gráfico satisfacen las condiciones [3] : $c_{yo}$ $\Gama$

${\ estilo de visualización c_ {1} = 0}$
${\ estilo de visualización -c_ {2))$ es el número de aristas del gráfico $\Gama$
${\ estilo de visualización -c_ {3))$ - hay el doble de triángulos en el gráfico $\Gama$

Notas

↑ Biggs, 1993 , pág. 7.
↑ 1 2 Cvetkovich, 1984 , p. diez.
↑ 1 2 Biggs, 1993 , pág. ocho.
↑ Cvetkovich, 1984 , pág. once.

Literatura

Biggs NL Teoría de grafos algebraicos . — 2do. - Prensa de la Universidad de Cambridge, 1993. - 205 p.

Cvetkovich D., Dub M., Sahs H. Espectros de gráficos. Teoría y aplicación. - Kyiv: Naukova Dumka, 1984. - 384 p.