Diferenças

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

--- grafos:teoeuler [2022/12/05 16:15] – edição externa 127.0.0.1
+++ grafos:teoeuler [2023/01/24 17:04] (atual) – edição externa 127.0.0.1
@@ Linha 4: / Linha 4: @@
 === 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>
@@ Linha 10: / Linha 10: @@
 **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.
+$(\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.
-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.
-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".
 $(\Leftarrow)$ Seja $G$ um grafo conexo com apenas vértices de grau par.
-Seja $W = (v_0, a_0,\cdots , a_{t−1}, v_t)$ a trilha ([[grafos:walk|passeio]] sem repetição de arestas) mais longa em $G$.
+Seja $W = (v_0, a_0,\cdots , a_{t−1}, v_t)$ o [[.defCaminho|caminho]] mais longo em $G$.
+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 aumentada, 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 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$.
-Suponha 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.
+<wrap right>$\square$</wrap>
 </WRAP>