grafos:2conexo

Diferenças

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

Link para esta página de comparações

grafos:2conexo [2023/02/19 14:25] – pivagrafos:2conexo [2023/08/11 13:50] (atual) – edição externa 127.0.0.1
Linha 5: Linha 5:
 <WRAP round box 100%> <WRAP round box 100%>
 === Definição === === Definição ===
-//Um $G$ grafo $2$-conexo é um grafo conexo que continua conexo mesmo se retirarmos um vértice qualquer. Ou seja, precisamos remover pelo menos $2$ vértices para que $G$ deixe de ser conexo.+//Um $G$ grafo $2$-conexo é um grafo conexo que continua conexo mesmo se retirarmos um vértice qualquer. Ou seja, precisamos remover pelo menos $2$ vértices para que $G$ deixe de ser conexo.//
  
-Grafos $2$-conexos também podem ser chamados de **biconexos**.//+//Grafos $2$-conexos também podem ser chamados de **biconexos**.//
 </WRAP> </WRAP>
  
Linha 19: Linha 19:
 ---- ----
 <WRAP round box 90%> <WRAP round box 90%>
-=== Proposição 1 ===+=== Proposição ===
 //Um grafo $G$ é $2$-conexo se, e somente se, pode ser construído a partir de um ciclo adicionando sucessivamente $H$-caminhos com $H$ subgrafos definidos previamente.// //Um grafo $G$ é $2$-conexo se, e somente se, pode ser construído a partir de um ciclo adicionando sucessivamente $H$-caminhos com $H$ subgrafos definidos previamente.//
 </WRAP> </WRAP>
  
 <WRAP round box 100%> <WRAP round box 100%>
-//**Demonstração**:// ($\Rightarrow$) Basta notarmos que um grafo construído a partir de um [[.defCiclo|ciclo]] é uma única [[.defCompCon|componente conexa]], e nenhum de seus vértices possui grau menor que $2$. Desse modo, nenhum de seus vértices é um vértice de corte (//cutvertex//); também chamado de [[grafos:separar|vértice separador]].+//**Demonstração**://  
 + 
 +($\Rightarrow$) Basta notarmos que um grafo construído a partir de um [[.defCiclo|ciclo]] é uma única [[.defCompCon|componente conexa]], e nenhum de seus vértices possui grau menor que $2$. Desse modo, nenhum de seus vértices é um vértice de corte (//cutvertex//); também chamado de [[grafos:separar|vértice separador]].
  
 {{ :grafos:biconexo.png?350|}} {{ :grafos:biconexo.png?350|}}
Linha 37: Linha 39:
 ---- ----
 <WRAP round box 50%> <WRAP round box 50%>
-=== Lema ===+=== Lema 1 ===
 //Seja $G$, um grafo qualquer. Então, vale o seguinte:// //Seja $G$, um grafo qualquer. Então, vale o seguinte://
  
Linha 58: Linha 60:
  
 <WRAP round box 50%> <WRAP round box 50%>
-=== Proposição 2 ===+=== Lema 2 ===
 //Seja $G$ um grafo qualquer e $ab,cd \in a(G)$. São equivalentes:// //Seja $G$ um grafo qualquer e $ab,cd \in a(G)$. São equivalentes://
  
Linha 87: Linha 89:
  
 <WRAP round box 40%> <WRAP round box 40%>
-=== Proposição 3 ===+=== Lema 3 ===
 //O [[grafos:defgbloco|bloco-grafo]] de um grafo conexo é uma [[.defarvore | árvore]].// //O [[grafos:defgbloco|bloco-grafo]] de um grafo conexo é uma [[.defarvore | árvore]].//
 </WRAP> </WRAP>
  • grafos/2conexo.1676827518.txt.gz
  • Última modificação: 2023/02/19 14:25
  • por piva