CCT-UFCA/Ciência da Computação/Teoria dos Grafos/Grafos Eulerianos:
Definições fundamentais
[editar | editar código]Definição: Uma trilha Euleriana é uma trilha que contém todas as arestas de um grafo .
Definição: Um grafo é Euleriano se possui uma trilha fechada Euleriana.
Teoremas relacionados
[editar | editar código]Lema 1: Seja conexo e tal que todos os vértices possuem grau par pelo menos 2. Então todo vértice de está contido em algum ciclo de .
Prova: Se não possui articulação, então é 2-conexo e, como vimos, entre todo par de vértices e existe um ciclo contendo ambos. Logo, para todo vértice de , existirá um ciclo que o contém, e portanto o lema vale.
Caso contrário, seja uma articulação de . Sejam , , ..., as componentes conexas de , com . Se possui um número ímpar de vizinhos em alguma componente , então é um subgrafo que contém um número ímpar de vértices de grau ímpar, o que é absurdo e portanto o lema vale. Caso contrário, provemos por indução no número de articulações de .
- Caso base: Para , temos que o subgrafo é 2-conexo, para todo . Logo, sabemos que todos os vértices de pertencem a um ciclo, e recaímos no primeiro caso desta prova.
- Passo indutivo: Suponha que o lema vale para todo . Seja um grafo com articulações. Assim, cada subgrafo possui no máximo articulações e, por hipótese de indução, em todos os vértices pertencem a algum ciclo, para todo, .
Teorema 1: Um grafo conexo é euleriano se e somente se o grau de todo vértice é par.
Prova (ida): Seja um grafo Euleriano. Seja, também, uma trilha fechada Euleriana de .
Para cada vértice que ocorre internamente em , temos duas arestas distintas incidentes a . Ou seja, o grau desses vértices é igual a duas vezes seu número de ocorrências internas.
Para o vértice , contamos um grau par para as ocorrências internas em e mais duas unidades nas extremidades de , totalizando um número par para seu grau.
Prova (volta): Seja conexo tal que todos os graus são pares. Suponha por absurdo que não é Euleriano.
Seja a trilha fechada de de comprimento máximo. Temos que contém um subgrafo , tal que não é vazio. Além disso, todos os vértices de possuem grau par. Podemos assumir como um subgrafo conexo não vazio de e, portanto, o grau de todos os vértices de são pares e pelos menos 2.
Pelo lema anterior aplicado a , temos que possui ao menos um ciclo . Como é conexo, temos que existe ao menos um vértice .
Podemos escolher como um ciclo contendo , pelo lema anterior. Assim, podemos obter uma trilha que contém as arestas de e de , o que contradiz a hipótese sobre a maximalidade de . Absurdo.
Corolário 1: Seja conexo. O grafo possui uma trilha euleriana se, e somente se, possui no máximo 2 vértices de grau ímpar.
Prova (ida): Seja conexo e tal que possui uma trilha euleriana. Sabemos que cada vértice da trilha euleriana de , com exceção das duas extremidades, possui grau par. Logo, exatamente 2 vértices de (as extremidades da trilha), possuem grau ímpar.
Prova (volta): Suponha que é conexo e possui no máximo 2 vértices de grau ímpar.
Se não possui vértices de grau ímpar, então, pelo Teorema 1, é euleriano, e portanto possui uma trilha euleriana fechada.
Caso contrário, necessariamente possui 2 vértices, e , de grau ímpar. Nesse caso, seja , o grafo obtido pela adição de a . Trivialmente, todos os vértices de possuem grau par e, pelo Teorema 1, sabemos que possui uma trilha euleriana . Por definição, é uma trilha que contém todas as arestas de , portanto, ao remover a aresta antes adicionada, obtemos uma trilha que contém todas as arestas de , e portanto, temos que é trilha euleriana de .
