En la disciplina matemática de la teoría de grafos , el espacio de aristas y el espacio de vértices de un grafo no dirigido son espacios vectoriales definidos en términos de conjuntos de aristas y vértices , respectivamente. Estos espacios vectoriales permiten utilizar técnicas de álgebra lineal en el estudio de la gráfica.
Definición
Dejar ser un gráfico finito no dirigido. El espacio del vértice de G es el espacio vectorial sobre el campo finito de dos elementos de todas las funciones . Cada elemento denaturalmente corresponde al subconjunto de V que asigna un 1 a sus vértices. Además, cada subconjunto de V está representado de forma única enpor su función característica. El espacio del borde es el -vector espacio generado libremente por el conjunto de aristas E . La dimensión del espacio de vértices es, por lo tanto, el número de vértices del gráfico, mientras que la dimensión del espacio del borde es el número de bordes.
Estas definiciones pueden hacerse más explícitas. Por ejemplo, podemos describir el espacio del borde de la siguiente manera:
- Los elementos del espacio vectorial son subconjuntos de , es decir, como un conjunto es el conjunto de potencia de E
- La suma de vectores se define como la diferencia simétrica :
- la multiplicación escalar se define por:
Los subconjuntos singleton de E forman una base para.
También se puede pensar en como el conjunto de potencias de V convertido en un espacio vectorial con una suma vectorial similar y una multiplicación escalar definida para.
Propiedades
La matriz de incidencia para un gráfico define una posible transformación lineal
entre el espacio de borde y el espacio de vértice de. La matriz de incidencia de, como una transformación lineal, asigna cada borde a sus dos vértices incidentes . Dejar ser el borde entre y luego
El espacio de ciclo y el espacio de corte son subespacios lineales del espacio de borde.
Referencias
- Diestel, Reinhard (2005), Graph Theory (3.a ed.), Springer , ISBN 3-540-26182-6 (la tercera edición electrónica está disponible gratuitamente en el sitio del autor).