==== Á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, [[https://sites.icmc.usp.br/szani/alglin.pdf |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 [[grafos:defbipartite#proposicao |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 [[grafos:defarvores#teoremaequivalencias | 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}$: {{ :grafos:graphs304.png?400 |}} === 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 [[grafos:defarvores#corolario_2|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}$.