En teoría de grafos , una rama de las matemáticas, el rango de un grafo no dirigido tiene dos definiciones no relacionadas. Sea n igual al número de vértices del gráfico.
De manera análoga, la nulidad del gráfico es la nulidad de su matriz de adyacencia, que es igual a n − r .
En la teoría matroide de gráficos, el rango de un gráfico no dirigido se define como el número n - c , donde c es el número de componentes conectados del gráfico. [1] De manera equivalente, el rango de un gráfico es el rango de la matriz de incidencia orientada asociada con el gráfico. [2]
De manera análoga, la nulidad del gráfico es la nulidad de su matriz de incidencia orientada, dada por la fórmula m − n + c , donde n y c son como arriba y m es el número de aristas del gráfico. La nulidad es igual al primer número Betti del gráfico. La suma del rango y la nulidad es el número de aristas.
Ejemplos
Un gráfico y una matriz de muestra:
Un gráfico no dirigido.
(correspondiente a los cuatro bordes, e1 – e4):
En este ejemplo, el rango de la matriz en la teoría de matrices es 4, porque sus vectores columna son linealmente independientes.
^ Weisstein, Eric W. "Rango del gráfico". De MathWorld: un recurso web de Wolfram. http://mathworld.wolfram.com/GraphRank.html
^ Grossman, Jerrold W.; Kulkarni, Devadatta M.; Schochetman, Irwin E. (1995), "Sobre los menores de una matriz de incidencia y su forma normal de Smith", Álgebra lineal y sus aplicaciones , 218 : 213–224, doi : 10.1016/0024-3795(93)00173-W , Señor 1324059. Véase en particular la discusión en la p. 218.
Referencias
Chen, Wai-Kai (1976), Teoría de grafos aplicada , North Holland Publishing Company, ISBN 0-7204-2371-6.
Hedetniemi, ST, Jacobs, DP, Laskar, R. (1989), Desigualdades que involucran el rango de un gráfico. Revista de Matemáticas Combinatorias y Computación Combinatoria , vol. 6, págs. 173-176.
Bevis, Jean H., Blount, Kevin K., Davis, George J., Domke, Gayla S., Miller, Valerie A. (1997), El rango de un gráfico después de la suma de vértices. Álgebra lineal y sus aplicaciones , vol. 265, págs. 55–69.
