Diferenças

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

--- grafos:subgrafos [2023/08/08 14:26] – edição externa 127.0.0.1
+++ grafos:subgrafos [2023/08/10 13:11] (atual) – edição externa 127.0.0.1
@@ Linha 31: / Linha 31: @@
 <WRAP round box 100%>
 === Definição: Grafo Induzido ===
-No caso em que $A' = \{uv \in A : u,v \in V'\}$ é o conjunto de todas essas arestas, dizemos que $H$ é o subgrafo de $G$ **induzido** por $V'$ e em geral denotamos $H = G[V']$.
+//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']$.//
 </WRAP>
-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 $01$ (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\}$.
+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:
@@ Linha 47: / Linha 48: @@
   * Uma aresta, e os vértices aos quais ela é incidente, de um grafo $G$ é um subgrafo de $G$;
-<WRAP round box 70%>
+<WRAP round box 100%>
+=== 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$.//
+</WRAP>
+<WRAP round box 100%>
 === 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.
+//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**. //
+//Se $G_1$ e $G_2$ não possuírem vértices em comum, os dois subgrafos são chamados de **vértices-disjuntos**. //
 </WRAP>
 ----
-<WRAP round tip 30%>
-=== Veja também: ===
-[[.defgerador | Subgrafo gerador]].
-</WRAP>
 <WRAP round info box 100%>