==== Homomorfismo e Isomorfismo ==== === Definição: Homomorfismo === //Sejam $G=(V,E)$ e $G'=(V',E')$ dois grafos. Um mapa $\varphi : V \to V'$ é um **homomorfismo** de $G$ para $G'$ se ele preserva a adjacência de vértices, isto é, se $\{\varphi (x),\varphi (y)\} \in E'$ sempre que $\{x,y\} \in E$. Em particular, para cada $x'$ na imagem de $\varphi$ sua imagem inversa $\varphi ^{-1} (x')$ é um conjunto independente de vértices em $G$.// === Definição: Isomorfismo === //Se $\varphi$ é bijetivo e seu inverso $\varphi ^{-1}$ também é um homomorfismo (de modo que $xy \in E \Leftrightarrow \varphi (x) \varphi (y) \in E'$ para todo $x,y \in V$), chamamos $\varphi$ de **isomorfismo**, dizemos que $G$ e $G'$ são isomórficos e escrevemos $G \simeq G'$. Um isomorfismo de $G$ para si mesmo é um **automorfismo** de $G$.// Normalmente não distinguimos entre grafos isomórficos. Assim, geralmente escrevemos $G=G'$ em vez de $G \simeq G'$. Se quisermos enfatizar que estamos interessados apenas no tipo de isomorfismo de um determinado grafo, nos referimos informalmente a ele como um **//grafo abstrato//**. Uma classe de grafos que é fechada sob isomorfismo é chamada de //propriedade do grafo//. Por exemplo, conter um triângulo é uma propriedade do grafo: se $G$ contém três vértices adjacentes pareados, então todo grafo isomórfico a $G$ também contém. Um mapa que usa grafos como argumentos é chamado de //**invariante de grafo**// se atribuir valores iguais a grafos isomórficos. O número de vértices e o número de arestas de um grafo são duas invariantes de grafos simples; o maior número de vértices adjacentes aos pares é outro. Definimos $G \cup G' := (V \cup V', E \cup E')$ e $G \cap G' := (V \cap V', E \cap E')$. Se $G \cap G' = \emptyset$, então $G$ e $G'$ são disjuntos. ===== Subgrafos ===== Um //subgrafo// de um grafo $G$ é, em linguagem informal, um “pedaço” de $G$. Assim, dado $G = (V, A)$ um grafo qualquer, um **subgrafo** de $G$ é um grafo $H = (V’,A’)$, tal que $V'\subset V$ e $A’\subset A$, ou seja, todo vértice de $H$ é vértice de $G$ e toda aresta de $H$ é aresta de $G$, então $H$ é um subgrafo de $G$. Denotamos, pois, $H\subseteq G$. === Definição: Subgrafo === //Seja tais dois grafos $G=(V,A)$ e $H=(V',A')$. Se $V' \subseteq V$ e $E' \subseteq E$ , então $G'$ é dito um **subgrafo** de $G$, escrito como $G' \subseteq G$.// === Definição: Grafo Induzido === //Seja dois grafos $G=(V,A)$ e $G'=(V',A')$. Se $G' \subseteq G$ e $G'$ contém todas as arestas $xy \in A$ com $x,y \in V'$, então $G'$ é um **subgrafo induzido** de $G$; dizemos que $V'$ induz ou gera $G'$ em $G$ e escrevemos $G' =: G[V']$.// Assim, se $U \subseteq V$ é qualquer conjunto de vértices, então $G[U]$ denota o grafo em $U$ cujas arestas são precisamente as arestas de $G$ com ambas as extremidades em $U$. Se $H$ é um subgrafo de $G$, não necessariamente induzido, abreviamos $G[V(H)]$ para $G[H]$. A figura abaixo exemplifica a diferença entre essas duas subestruturas. Nela, o grafo $H'$ é um subgrafo do grafo $G$ representado e possui como vértices os elementos do conjunto $\{0,1,2,3,4\}$. Suas arestas são algumas arestas de $G$ que possuem dois desses vértices como extremidades. Ainda assim, $H'$ não é um subgrafo induzido de $G$, pois a aresta $\{0,1\}$ (presente no grafo $G$) não é uma aresta de $H'$. O grafo $H$, por outro lado, é o subgrafo de $G$ induzido por $\{0,1,2,3,4\}$. {{ :grafos:exemplossub.png?600 |}} As seguintes observações podem ser feitas: * Todo grafo é um subgrafo de si próprio; * Um subgrafo de um subgrafo $G$ também é um subgrafo de $G$; * Um vértice de um grafo $G$ é um subgrafo de $G$; * Uma aresta, e os vértices aos quais ela é incidente, de um grafo $G$ é um subgrafo de $G$; === Definição: Subgrafo Gerador === //Um **subgrafo gerador** de um grafo $G = (V,A)$ é um [[.subgrafos| subgrafo]] $H' = (V',A')$ de $G$ tal que $V=V'$, ou seja, se se $V'$ gera todo $G$.// === Definição === //Dois subgrafos de um grafo $G$, $G_1$ e $G_2$, são **aresta-disjuntos** se eles não possuem arestas em comum.// //Se $G_1$ e $G_2$ não possuírem vértices em comum, os dois subgrafos são chamados de **vértices-disjuntos**. // ---- === Referências === * M. Cristina, et al. [[http://wiki.icmc.usp.br/images/a/a2/SCC603-2013-01-IntroducaoGrafos.pdf|"Introdução da Grafos"]] .Instituto de Ciências Matemáticas e da Computação(ICMC)2010-2013. Acesso em 16/09/2022. * P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi. [[https://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf| "Uma Introdução Sucinta à Teoria dos Grafos"]] .2011. Acesso em 16/09/2022. * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 03-04. Acesso em 16/09/2022.