Grafos Euleriano

Um grafo G é Euleriano se e somente se for conexo e tiver exatamente ou 0 ou 2 vértices de grau ímpar. No primeiro caso, G permite um passeio circuit Euleriano, enquanto que no segundo caso G permite um caminho euleriano com início numa vértice de grau ímpar e término na outra vértice.

Caminho Euleriano é um caminho no grafo que visita cada aresta exatamente uma vez. Circuito Euleriano é um caminho Euleriano que começa e termina no mesmo vértice

introdução

Há uma importante classe de problemas chamados problemas de roteamento que são muito importantes no mundo de hoje. Na realidade, os problemas de encaminhamento contêm muitos dos problemas não resolvidos mais importantes da matemática. Esses problemas surgem em muitas áreas: transporte, comunicações e serviços de entrega para citar alguns.

O que é um problema de roteamento?
Um problema de roteamento é um problema cuja solução tenta dar a forma mais eficiente (s) de encaminhamento de coisas entre os diferentes destinos. Por exemplo, é muito importante para as companhias aéreas para agendar vôos entre as cidades servidas pela companhia aérea de forma eficiente. Juntando horários de vôos eficientes é um problema de roteamento.

Um Caminho Euleriano é um caminho em um grafo que visita cada aresta apenas uma vez. Com caso especial, um Circuito Euleriano é um caminho Euleriano que começa e termina no mesmo vértice. O conceito foi introduzido por Leonard Euler para a resolução do famoso problema das sete pontes de Königsberg em 1736.
Grafos que possuem um circuito Euleriano são chamados Grafos Eulerianos. Uma das principais condições para um grafo ser Euleriano é que todos os vértices precisam ser de grau par. Esta condição é também suficiente. Euler provou que uma condição necessária para a existência de circuitos eulerianos é de que todos os vértices tenham grau par, e afirmou, sem prova de que grafos conexos com todos os vértices pares tem um circuito Euleriano. A primeira prova