grafos:teoeuler

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:teoeuler [2022/12/05 16:20] – pivagrafos:teoeuler [2023/01/24 17:04] (atual) – edição externa 127.0.0.1
Linha 4: Linha 4:
 === Teorema === === Teorema ===
  
-Um grafo [[grafos:defconexo|conexo]] $G$ admite um [[grafos:defeuler|circuito euleriano]] se, e somente se, todos os seus vértices tem [[grafos:grauv|grau]] par.+//Um grafo [[grafos:defconexo|conexo]] $G$ admite um [[grafos:defeuler|circuito euleriano]] se, e somente se, todos os seus vértices tem [[grafos:grauv|grau]] par.//
 </WRAP> </WRAP>
  
Linha 10: Linha 10:
 **Demonstração:** **Demonstração:**
  
-$(\Rightarrow)$ Seja $C$ um [[.defCiclo|ciclo]] de $G$. Cada vez que um vértice $v$ ocorre no ciclo $C$, há uma contribuição de duas unidades para o [[.grauV| grau]] de $v$, uma aresta para chegar a $v$ e outra para sair. Isto vale não só para os vértices intermediários como também para o vértice final, uma vez que se trata de um ciclo, logo "saímos" e entramos" no mesmo vértice no início e no final do trajeto.+$(\Rightarrow)$ Seja $C$ um circuito euleriano de $G$. Cada vez que um vértice $v$ ocorre no ciclo $C$, há uma contribuição de duas unidades para o [[.grauV| grau]] de $v$, uma aresta para chegar a $v$ e outra para sair. Isto vale não só para os vértices intermediários como também para o vértice final, uma vez que se trata de um ciclo, logo "saímos" e entramos" no mesmo vértice no início e no final do trajeto.
  
-Como $C$ é um circuito euleriano, cada aresta ocorre exatamente uma única vez em $C$, portanto cada vértice possui grau par. Portanto, segue a prova da "ida".+Como $C$ é um circuito euleriano, cada aresta ocorre exatamente uma única vez em $C$, portanto cada vértice possui grau par.
  
 $(\Leftarrow)$ Seja $G$ um grafo conexo com apenas vértices de grau par. $(\Leftarrow)$ Seja $G$ um grafo conexo com apenas vértices de grau par.
Linha 19: Linha 19:
 Como $W$ não pode ser aumentado, contém todas as arestas que incidem em $v_t$. Por hipótese, a quantidade dessas arestas é par. Disso $v_0 = v_t$ e $W$ é um ciclo. Como $W$ não pode ser aumentado, contém todas as arestas que incidem em $v_t$. Por hipótese, a quantidade dessas arestas é par. Disso $v_0 = v_t$ e $W$ é um ciclo.
  
-Suponhamos então que $W$ não seja euleriano. Então existe uma aresta $a = vv_i \not\in W$ com $v_i\in W$. Logo existe uma trilha $(v, a, v_i, \cdots, a_{t−1}, v_t, a_0, \cdots, a_{i−1}, v_i)$ mais longa do que $W$, uma contradição.+Suponhamos então que $W$ não seja euleriano. Então existe uma aresta $a = vv_i \not\in W$ com $v_i\in W$. Logo, existe um caminho  $(v, a, v_i, \cdots, a_{t−1}, v_t, a_0, \cdots, a_{i−1}, v_i)$ mais longo do que $W$, o que configura uma contradição à escolha do caminho $W$. 
 + 
 +<wrap right>$\square$</wrap>
 </WRAP> </WRAP>
  • grafos/teoeuler.1670268001.txt.gz
  • Última modificação: 2022/12/05 16:20
  • por piva