grafos:subgrafos

Diferenças

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

Link para esta página de comparações

Ambos lados da revisão anterior Revisão anterior
Próxima revisão		 Revisão anterior
grafos:subgrafos [2023/08/09 10:43] – pivagrafos:subgrafos [2023/08/10 13:11] (atual) – edição externa 127.0.0.1
Linha 37: Linha 37:
 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]$. 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 $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\}$.+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 |}} {{ :grafos:exemplossub.png?600 |}}
- 
- 
  
 As seguintes observações podem ser feitas: As seguintes observações podem ser feitas:
Linha 50: Linha 48:
   * Uma aresta, e os vértices aos quais ela é incidente, 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$;
  
-<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 === === 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>
 ---- ----
-<WRAP round tip 30%> 
-=== Veja também: === 
- 
-[[.defgerador | Subgrafo gerador]]. 
-</WRAP> 
  
 <WRAP round info box 100%> <WRAP round info box 100%>
  • grafos/subgrafos.1691588603.txt.gz
  • Última modificação: 2023/08/09 10:43
  • por piva