Álgebra Linear básica para grafos
Nota
Antes de ler essa página, se você, leitor, não tiver familiaridade com álgebra linear básica, sugerimos que leiam um pouco sobre na apostila de Algebra Linear, do professor Sérgio Luís Zani, aqui.
Seja $G=(V,A)$ um grafo com $n$ vértices e $m$ arestas, digamos $V=\{v_1, \dots, v_{n}\}$ e $E= \{e_1, \dots , e_{m}\}$. O espaço de vértices $\mathcal{V}(G)$ de $G$ é o espaço vetorial sobre o campo de $2$ elementos $\mathbb{F}_2 = \{0,1\}$ de todas as funções $V \to \mathbb{F}_2$. Cada elemento de $\mathcal{V}(G)$ corresponde naturalmente a um subconjunto de $V$ , o conjunto daqueles vértices aos quais atribui um $1$, e cada subconjunto de $V$ é representado exclusivamente em $\mathcal{V}(G)$ por sua função indicadora. Podemos, portanto, pensar em $\mathcal{V}(G)$ como o conjunto de potência de $V$ transformado em um espaço vetorial: a soma $U+U'$ de dois conjuntos de vértices $U,U' \subseteq V$ é sua diferença simétrica, e $U=-U$ para todo $U \subseteq V$. O zero em $\mathcal{V}(G)$, visto dessa maneira, é o conjunto vazio (de vértice) $\emptyset$. Como $\{\{v_1\}, \dots ,\{v_{n}\}\}$ é uma base de $\mathcal{V}(G)$ , sua base padrão, temos $dim \mathcal{V}(G) =n$.
Da mesma forma que acima, as funções $E \to \mathbb{F}_2$ formam o espaço de arestas $\mathcal{E}(G)$ de $G$: seus elementos correspondem aos subconjuntos de $E$, a adição de vetores equivale à diferença simétrica, $\emptyset \subseteq E$ é o zero, e $F=-F$ para todo $F \subseteq E$. Como antes, $\{\{e_1\}, \dots ,\{e_{m}\}\}$ é a base padrão de $\mathcal{E}(G)$, e $dim \mathcal{E} = m$. Dados dois elementos $F,F'$ do espaço de aresta , vistos como funções $E \to \mathbb{F}_2$, escrevemos:
$$\langle F,F' \rangle := \sum_{e \in E} F(e) F'(e) \in \mathbb{F}_2$$
Isso é zero se, e somente se, $F$ e $F'$ tiverem um número par de arestas em comum; em particular, podemos ter $\langle F,F' \rangle = 0$ com $F \neq \emptyset$. Dado um subespaço $\mathcal{F}$ de $\mathcal{E}(G)$, escrevemos
$$\mathcal{F} ^{\bot} := \{D \in \mathcal{E}(G) \mid \langle F,D \rangle =0, \forall F \in \mathcal{F}$$
Este é novamente um subespaço de $\mathcal{E}(G)$ (o espaço de todos os vetores resolvendo um certo conjunto de equações lineares), e pode-se mostrar que
$$dim \mathcal{F} + dim \mathcal{F}^{\bot} = m$$
O espaço de ciclo $\mathcal{C} = \mathcal{C}(G)$ é o subespaço de $\mathcal{E}(G)$ gerado por todos os ciclos em $G$. Mais precisamente, por seus conjuntos de arestas. A dimensão de $\mathcal{C}(G)$ é algumas vezes chamada de número ciclomático de $G$.
os elementos de $\mathcal{C}$ são facilmente reconhecidos pelos graus dos subgrafos que eles formam. Além disso, para gerar o espaço do ciclo a partir dos ciclos, precisamos apenas de uniões disjuntas em vez de diferenças simétricas arbitrárias:
Proposição 1
As seguintes afirmações são equivalentes para conjuntos de arestas $D \subseteq E$:
$(i)$ $D \in \mathcal{C}(G)$;
$(ii)$ $D$ é uma união disjunta (possivelmente vazia) de conjuntos de arestas de ciclos em $G$;
$(iii)$ Todos os graus dos vértices do grafo $(V,D)$ são pares.
Demonstração:
Como os ciclos têm graus pares e tomar diferenças simétricas preserva isso, $(i) \to (iii)$ segue por indução no número de ciclos usados para gerar $D$. A implicação $(iii) \to (ii)$ segue por indução em $|D|$: se $D \neq \emptyset$ então $(V,D)$ contém um ciclo $C$, cujas arestas excluímos para o etapa de indução. A implicação $(ii) \to (i)$ é imediata da definição de $\mathcal{C}(G)$.
Um conjunto $F$ de arestas é um corte em $G$ se existe uma partição $\{V_1,V_2\}$ de $V$ tal que $F=E(V_1,V_2)$. Diz-se que as arestas em $F$ cruzam esta partição. Os conjuntos $V_1,V_2$ são os lados* do corte. Lembre-se que para $V_1 = \{v\}$ este corte é denotado por $E(v)$. Um corte mínimo não vazio em $G$ é uma ligação.
Proposição 2
Juntamente com $\emptyset$, os cortes em $G$ formam um subespaço $\mathcal{B} = \mathcal{B}(G)$ de $\mathcal{E}(G)$. Este espaço é gerado por cortes da forma $E(v)$.
Demonstração:
Deixe $\mathcal{B}$ denotar o subespaço de $\mathcal{E}(G)$ gerado pelos cortes da forma $E(v)$. Todo corte de $G$, com partição de vértice $\{V_1,V_2\}$, digamos, é igual a $\sum_{v \in V_1}E(v)$ e, portanto, está em $\mathcal{B}$. Reciprocamente, todo conjunto $\sum_{u \in U}E(u) \in \mathcal{B}$ é vazio, por exemplo, se $U \in \{\emptyset,V\}$, ou é o corte $E(U, V \setminus U)$.
O espaço $\mathcal{B}$ da Proposição $2$ acima é o espaço cortado, ou espaço de ligação, de $G$. Não é difícil encontrar entre os cortes $E(v)$ uma base explícita para $\mathcal{B}$ e, assim, determinar sua dimensão. Observe que as ligações são para $\mathcal{B}$ o que os ciclos são para $\mathcal{C}$: os elementos mínimos não vazios.
A condição não vazia na definição de uma ligação é válida apenas se $G$ for desconexo. Se $G$ é conexo, suas ligações são apenas seus cortes mínimos, e estes são fáceis de reconhecer: um corte em um grafo conexo é mínimo se, e somente se, ambos os lados da partição de vértice correspondente induzem subgrafos conexos. Se $G$ for desconexo, suas ligações são os cortes mínimos de seus componentes.
Em analogia à Proposição $1$ acima, ligações e uniões disjuntas são suficientes para gerar o espaço de corte:
Lema
Cada corte é uma união disjunta de ligações.
Demonstração:
Aplicamos indução no tamanho do corte $F$ considerado. Para $F = \emptyset$ a afirmação é trivial (com a união vazia). Se $F \neq \emptyset$ não é ele próprio uma ligação, ele contém apropriadamente algum outro corte não vazio $F'$. Pela Proposição $2$ acima, também $F \setminus F' = F + F'$ é um corte não vazio menor. Pela hipótese de indução, tanto $F'$ quanto $F \setminus F'$ são uniões disjuntas de ligações e, portanto, $F$ também é.
Teorema 1
O espaço de ciclo $\mathcal{C}$ e o espaço de corte $\mathcal{B}$ de qualquer grafo satisfazem
$$\mathcal{C}=\mathcal{B}^{\bot}$$
e
$$\mathcal{B} = \mathcal{C}^{\bot}$$
Demonstração:
Considere um grafo $G=(V,E)$. Claramente, qualquer ciclo em $G$ tem um número par de arestas em cada saída. Isso implica $\mathcal{C} \subseteq \mathcal{B}^{\bot}$ e $\mathcal{B} \subseteq \mathcal{C}^{\bot}$.
Para provar $\mathcal{B}^{\bot} \subseteq \mathcal{C}$, lembre-se da Proposição $1$ mais acima, que para cada conjunto de arestas $F \notin \mathcal{C}$ existe um vértice $v$ incidente com um número ímpar de arestas em $F$. Então $\langle E(v),F \rangle =1$, então $E(v) \in \mathcal{B}$ implica $F \notin \mathcal{B}^{\bot}$. Isso completa a prova de $\mathcal{C} = \mathcal{B}^{\bot}$.
Para provar $\mathcal{C}^{\bot} \subseteq \mathcal{B}$, seja dado $F \in \mathcal{C}^{\bot}$. Considere o multigrafo $H$ obtido de $G$ contraindo as arestas em $E \setminus F$. Qualquer ciclo em $H$ tem todas as suas arestas em $F$. Como podemos estendê-lo a um ciclo em $G$ por arestas de $E \setminus F$, o número dessas arestas deve ser par. Portanto, $H$ é bipartido, pela Proposição. Sua bipartição induz uma bipartição $(V_1,V_2)$ de $V$ tal que $E(V_1,V_2) =F$, mostrando $F \in \mathcal{B}$ como desejado.
Considere um grafo conectado $G=(V,E)$ com uma árvore geradora $T \subseteq G$. Para cada corda $e \in E \setminus E(T)$ existe um único ciclo $C_{e}$ em $T+e$, o ciclo fundamental de $e$ em relação a $T$. Da mesma forma, para cada aresta $f \in T$ a floresta $T-f$, pelo Teorema $(iii)$ tem exatamente duas componentes. O conjunto $D_{f} \subseteq E$ de arestas de $G$ entre esses componentes é uma ligação em $G$, o corte fundamental de $f$ em relação a $T$.
Observe que $f \in C_{e}$ se, e somente se, $e \in D_{f}$, para todas as arestas $e \notin T$ e $f \in T$. Esta é uma indicação de alguma dualidade mais profunda, que o seguinte teorema explora mais.
O ciclo fundamental $C_{e}$, e o corte fundamental $D_{f}$:
Teorema 2
Seja $G$ um grafo conexo com $n$ vértices e $m$ arestas, e seja $T \subseteq G$ uma árvore geradora.
$(i)$ Os cortes fundamentais e ciclos de $G$ com respeito a $T$ formam base de $\mathcal{B}(G)$ e $\mathcal{C}(G)$, respectivamente.
$(ii)$ Portanto, $dim \mathcal{B}(G) = n-1$ e $dim \mathcal{C}(G) = m-n+1$.
Demonstração:
$(i)$ Observe que uma aresta $f \in T$ está em $D_{f}$, mas em nenhum outro corte fundamental, enquanto uma aresta $e \notin T$ está em $C_{e}$, mas em nenhum outro ciclo fundamental. Assim, os cortes e ciclos fundamentais formam conjuntos linearmente independentes em $\mathcal{B}=\mathcal{B}(G)$ e $\mathcal{C}=\mathcal{C}(G)$ , respectivamente.
Vamos mostrar que os ciclos fundamentais geram todo ciclo $C$. Pela nossa observação inicial, $D := C = \sum_{e \in C \setminus T}C_{e}$ é um elemento de $\mathcal{C}$ que não contém nenhuma aresta fora de $T$. Mas pela Proposição $1$ acima, o único elemento de $\mathcal{C}$ contido em $T$ é $\emptyset$. Então $D = \emptyset$ , dando $C = \sum_{e \in C \setminus T}C_{e}$.
Da mesma forma, todo corte $D$ é uma soma de cortes fundamentais. De fato, o elemento $D + \sum _{f \in D \cap T}D_{f}$ de $\mathcal{B}$ não contém aresta de $T$. Como $\emptyset$ é o único elemento de $\mathcal{B}$ sem $T$, isso implica em $D = \sum_{f \in D \cap T}D_{f}$.
$(ii)$ Por $(i)$, os cortes e ciclos fundamentais formam bases de $\mathcal{B}$ e $\mathcal{C}$. Como existem $n-1$ cortes fundamentais Corolário, existem $m-n+1$ ciclos fundamentais.
A matriz de incidência $\mathcal{B} = (b_{ij})_{n \times m}$ do gráfico $G=(V,E)$ com $V=\{v_1, \dots ,v_{n}\}$ e $E=\{e_1, \dots, e_{m}$ é definida sobre $\mathbb{F}_2$ por
$$b_{ij} =\begin{cases} 1, & \mbox{se } v_i \in e_j\\ 0, & \mbox{caso contrário.}\end{cases}$$
Como de costume, deixe $B^{t}$ denotar a transposta de $B$. Então $B$ e $B^{t}$ definem mapas lineares $B: \mathcal{E}(G) \to \mathcal{V}(G)$ e $B^{t}: \mathcal{V}(G) \to \mathcal{E}(G)$ em relação às bases padrão. Como é fácil verificar, $B$ mapeia um conjunto de arestas $F \subseteq E$ para o conjunto de vértices incidentes com um número ímpar de arestas em $F$, enquanto $B^{t}$ mapeia um conjunto $U \subseteq V$ para um conjunto de arestas com exatamente uma extremidade em $U$. Em particular:
Proposição 3
$(i)$ O núcleo de $B$ é $\mathcal{C}(G)$.
$(ii)$ A imagem de $B^{t}$ é $\mathcal{B}(G)$.
A matriz de adjacência $A=(a_{ij})_{n \times m} de $G$ é definida por
$$a_{ij} =\begin{cases} 1, & \mbox{se } v_iv_j \in E\\ 0, & \mbox{caso contrário.}\end{cases}$$
Visto como um mapa linear $\mathcal{V} \to \mathcal{V}$, a matriz de adjacência mapeia um determinado conjunto $U \subseteq V$ para o conjunto de vértices com um número ímpar de vizinhos em $U$.
Deixe $D$ denotar a matriz diagonal real $(d_{ij})_{n \times n}$ com $d_{ii}=d(v_i)$ e $d_{ij} = 0$ caso contrário. Nossa última proposição estabelece uma conexão entre $A$ e $B$ (agora vistas como matrizes reais), que pode ser verificada simplesmente a partir da definição de multiplicação de matrizes:
Proposição 4
$$BB_{t} =A+D$$
Também é interesante notar que $A$, com entradas tomadas $mod 2$, define o mesmo mapa $\mathcal{V} \to \mathcal{V}$ como a composição dos mapas de $B$ e $B^{t}$.