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/16 13:18] – 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 20: Linha 20:
  
 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$. 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.1671207499.txt.gz
  • Última modificação: 2022/12/16 13:18
  • por piva