En la 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.
- En la teoría matricial de gráficos, el rango r de un gráfico no dirigido se define como el rango de su matriz de adyacencia .
- 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 en el 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 de
Un gráfico y una matriz de muestra:
(correspondiente a las cuatro aristas, e1 – e4):
| = |
|
En este ejemplo, el rango de la teoría de la matriz de la matriz es 4, porque sus vectores columna son linealmente independientes.
Ver también
Notas
- ^ Weisstein, Eric W. "Rango de 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. Ver 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 adición de vértices . Álgebra lineal y sus aplicaciones , vol. 265, págs. 55–69.