Nulidad (teoría de grafos)

La nulidad de un grafo en el campo matemático de la teoría de grafos puede significar cualquiera de dos números no relacionados. Si el grafo tiene n vértices y m aristas, entonces:

• En la teoría matricial de grafos, la nulidad del grafo es la nulidad de la matriz de adyacencia A del grafo. La nulidad de A está dada por n − r donde r es el rango de la matriz de adyacencia. Esta nulidad es igual a la multiplicidad del valor propio 0 en el espectro de la matriz de adyacencia. Véase Cvetkovič y Gutman (1972), Cheng y Liu (2007) y Gutman y Borovićanin (2011).
• En la teoría matroide, la nulidad del grafo es la nulidad de la matriz de incidencia orientada M asociada al grafo. La nulidad de M está dada por m − n + c , donde c es el número de componentes del grafo y n − c es el rango de la matriz de incidencia orientada. Este nombre se usa raramente; el número se conoce más comúnmente como rango de ciclo , número ciclomático o rango de circuito del grafo. Es igual al rango del matroide cográfico del grafo. También es igual a la nulidad de la matriz laplaciana del grafo, definida como L = D − A , donde D es la matriz diagonal de grados de vértice; la nulidad laplaciana es igual al rango de ciclo porque L = M M ^T ( M por su propia transpuesta).

• Rango (teoría de grafos)

• Bo Cheng y Bolian Liu (2007), Sobre la nulidad de los grafos. Electronic Journal of Linear Algebra , vol. 16, artículo 5, pp. 60–67.
• Dragoš M. Cvetkovič e Ivan M. Gutman (1972), La multiplicidad algebraica del número cero en el espectro de un grafo bipartito. Matematički Vesnik (Beograd) , vol. 9, págs. 141–150.
• Ivan Gutman y Bojana Borovićanin (2011), Nullity of graphs: an updated survey. Zbornik Radova (Beograd) , vol. 14, no. 22 (Temas seleccionados sobre aplicaciones de espectros de grafos), págs. 137–154.