Espacios de aristas y vértices

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 los conjuntos de aristas y vértices , respectivamente. Estos espacios vectoriales permiten utilizar técnicas de álgebra lineal para estudiar el grafo.

Dejar${\displaystyle G:=(V,E)}$Sea un grafo finito no dirigido. El espacio de vértices${\displaystyle {\mathcal {V}}(G)}$de G es el espacio vectorial sobre el campo finito de dos elementos ${\displaystyle \mathbb {Z} /2\mathbb {Z}$ :=\lbrace 0,1\rbrace } de todas las funciones${\displaystyle V\rightarrow \mathbb {Z} /2\mathbb {Z} }$Cada elemento de${\displaystyle {\mathcal {V}}(G)}$corresponde naturalmente al subconjunto de V que asigna un 1 a sus vértices. Además, cada subconjunto de V está representado de forma única en${\displaystyle {\mathcal {V}}(G)}$por su función característica. El espacio de borde${\displaystyle {\mathcal {E}}(G)}$es el${\displaystyle \mathbb {Z} /2\mathbb {Z} }$-espacio vectorial 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 grafo, mientras que la dimensión del espacio de aristas es el número de aristas.

Estas definiciones pueden hacerse más explícitas. Por ejemplo, podemos describir el espacio de aristas de la siguiente manera:

• los elementos son subconjuntos de${\displaystyle E}$, es decir, como un conjunto${\displaystyle {\mathcal {E}}(G)}$es el conjunto potencia de E
• La suma de vectores se define como la diferencia simétrica :${\displaystyle P+Q:=P\triangle Q\qquad P,Q\in {\mathcal {E}}(G)}$
• La multiplicación escalar se define por:
  • ${\displaystyle 0\cdot P:=\emptyset \qquad P\in {\mathcal {E}}(G)}$
  • ${\displaystyle 1\cdot P:=P\qquad P\in {\mathcal {E}}(G)}$

Los subconjuntos unitarios de E forman una base para${\displaystyle {\mathcal {E}}(G)}$.

También se puede pensar en${\displaystyle {\mathcal {V}}(G)}$como el conjunto potencia de V convertido en un espacio vectorial con suma vectorial y multiplicación escalar similares según se define para${\displaystyle {\mathcal {E}}(G)}$.

La matriz de incidencia${\displaystyle H}$para un gráfico${\displaystyle G}$define una posible transformación lineal

${\displaystyle H:{\mathcal {E}}(G)\to {\mathcal {V}}(G)}$

entre el espacio de aristas y el espacio de vértices de${\displaystyle G}$. La matriz de incidencia de${\displaystyle G}$, como transformación lineal, asigna a cada arista sus dos vértices incidentes . Sea${\displaystyle vu}$ser el borde entre${\displaystyle v}$y${\displaystyle u}$entonces

${\displaystyle H(vu)=v+u}$

El espacio de ciclos y el espacio de cortes son subespacios del espacio de aristas.

• Diestel, Reinhard (2005), Teoría de grafos (3.ª  ed.), Springer , ISBN 3-540-26182-6(La tercera edición electrónica está disponible gratuitamente en el sitio web del autor).

• Espacio para bicicletas
• Recortar espacio