Re: Grafos

[Augusto Morgado <morgado@xxxxxxxxxxxxxxx>]

Eduardo Favarão Botelho wrote:
> 
> Olá pessoal...
> 
> Li o artigo sobre circuitos eulerianos no primeira Eureka, e lá era
> enunciado o seguinte teorema:
> "Existe um circuito euleriano em um grafo se e somente se o grafo é conexo e
> cada vértice tem  grau par".
> 
>     Depois de ler o teorema, pensei num quadrado ABCD com uma bissetriz
> traçada, AC por exemplo.
>     Ora, o circuito não tem grau par, pois nos vértices A e C incidem três
> arcos, número ímpar.
>     O que há de errado?
> 
> Abraços, Eduardo.
Um circuito começa e termina no mesmo ponto, No seu grafo realmente não
existe um circuito euleriano. Não há nada de errado.
O que existe é um caminho aberto (começa e termina em pontos diferentes)
euleriano. A condição de existência de um caminho aberto euleriano é
similar, só que deve haver dois vértices de grau ímpar, os quais serão
precisamente os pontos inicial e final do caminho.