grafos:algebralinbas

Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

Link para esta página de comparações

Próxima revisão		 Revisão anterior
grafos:algebralinbas [2023/05/10 12:54] – criada pivagrafos:algebralinbas [2023/05/10 13:04] (atual) – edição externa 127.0.0.1
Linha 1: Linha 1:
 ==== Álgebra Linear básica para grafos ==== ==== Álgebra Linear básica para grafos ====
 +
 +<WRAP round tip box 100%>
 +=== 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]].
 +</WRAP>
 +
 +
 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$. 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$.
  
Linha 171: Linha 178:
 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}$. 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}$.
  
----- 
-(Colocar link para apostilas sobre algebra linear(zani) 
  • grafos/algebralinbas.1683734063.txt.gz
  • Última modificação: 2023/05/10 12:54
  • por piva