Grafos, graus e trilhas eulerianas
Definição e escopo FATO
Um multigrafo finito não direcionado G=(V,E) é composto por um conjunto finito de vértices V e uma coleção finita de arestas E. Cada aresta conecta dois vértices sem impor um sentido de percurso. Várias arestas podem conectar o mesmo par de vértices; um laço também pode conectar um vértice a ele mesmo. Um grafo simples é o caso particular sem laços nem arestas paralelas.
Esse modelo foi escolhido porque várias pontes de Königsberg conectavam as mesmas áreas terrestres: representá-las exige arestas paralelas. O artigo não trata de grafos direcionados, nos quais uma aresta tem um sentido, nem de grafos ponderados, nos quais ela carrega, por exemplo, uma distância ou um custo.
Assim, o multigrafo subjacente conserva apenas a relação de incidência: quais vértices cada aresta conecta. As posições desenhadas, os comprimentos e os ângulos não fazem parte de sua definição. Esses dados podem ser adicionados ao modelo quando forem úteis, mas não são necessários para o problema estudado aqui.
O vocabulário mínimo FATO
| Termo | Definição em um multigrafo não direcionado |
|---|---|
| Grau de um vértice | Número de extremidades de arestas incidentes no vértice; um laço conta como 2 |
| Passeio | Sequência de vértices e arestas incidentes; vértices e arestas podem se repetir |
| Trilha | Passeio que não repete nenhuma aresta |
| Caminho | Passeio que não repete nenhum vértice |
| Circuito | Trilha fechada: o início e o fim coincidem |
| Ciclo | Circuito que não repete nenhum vértice, exceto o vértice comum de início e fim |
| Conexo | Um caminho conecta cada par de vértices |
Uma trilha euleriana utiliza cada aresta exatamente uma vez. Ela é aberta se suas extremidades forem diferentes e se torna um circuito euleriano se retornar ao vértice inicial. A palavra “euleriana” se refere aqui às arestas, não aos vértices.
O lema do aperto de mãos FATO
Cada aresta comum tem duas extremidades e acrescenta 1 ao grau de cada um de seus vértices. Um laço também tem duas extremidades, ambas no mesmo vértice, e portanto acrescenta 2 ao seu grau. Contando com multiplicidade, cada aresta contribui com exatamente 2 para a soma total:
v∈V∑deg(v)=2∣E∣
O lado direito é par. Os vértices de grau par contribuem com uma soma par; portanto, a soma dos graus ímpares também deve ser par. Uma soma de inteiros ímpares é par se, e somente se, contiver um número par de termos. Logo, há sempre um número par de vértices de grau ímpar.
Em um grafo simples que representa uma assembleia, uma aresta significa que duas pessoas apertaram as mãos. O lema afirma então que o número de pessoas que deram um número ímpar de apertos de mão é par. Essa imagem explica seu nome, mas a demonstração também vale para multigrafos e laços com a convenção de grau anterior.
As pontes de Königsberg FATO
O problema histórico descreve quatro áreas terrestres conectadas por sete pontes. A questão era encontrar um passeio que atravessasse cada ponte exatamente uma vez, sem exigir o retorno ao ponto de partida.
Euler designou as áreas por letras e representou as travessias sucessivas por sequências de letras. Na reformulação moderna da teoria dos grafos, cada área se torna um vértice e cada ponte, uma aresta. O multigrafo obtido tem quatro vértices de graus 5, 3, 3 e 3. Sua soma é 14, isto é, o dobro do número de arestas (sete), de acordo com o lema.
Em uma trilha euleriana, todas as arestas incidentes são utilizadas. Cada passagem por um vértice intermediário as consome aos pares: uma para entrar e outra para sair. Portanto, apenas o início e o fim de uma trilha euleriana aberta têm grau ímpar, enquanto um circuito euleriano não tem nenhum.
Königsberg tem quatro. Não existe nenhuma trilha que utilize cada uma das sete pontes exatamente uma vez. Euler estabeleceu essa impossibilidade e formulou as regras gerais de paridade; o teorema moderno fornece a caracterização completa.
O teorema euleriano moderno FATO
Considere um multigrafo finito não direcionado no qual todos os vértices de grau não nulo pertencem à mesma componente conexa.
- Ele admite um circuito euleriano se, e somente se, todos os seus vértices têm grau par.
- Ele admite uma trilha euleriana aberta se, e somente se, exatamente dois vértices têm grau ímpar; eles são necessariamente seu início e seu fim.
A necessidade decorre do pareamento entrada–saída. A suficiência é construtiva. Quando todos os graus são pares, parte-se de um vértice incidente em uma aresta e seguem-se arestas ainda não utilizadas. Não é possível ficar bloqueado em outro vértice: por paridade, cada chegada deixa ali uma aresta não utilizada para sair. Portanto, a trilha acaba retornando ao ponto de partida e forma um circuito.
Se ainda restarem arestas, a conexidade garante que um vértice do circuito toca uma parte ainda não utilizada. A partir desse vértice, constrói-se um novo circuito e depois ele é inserido no primeiro. Repetindo a operação, obtém-se um circuito que contém todas as arestas: esse é o princípio do algoritmo de Hierholzer.
Se existirem exatamente dois vértices ímpares, adiciona-se temporariamente uma aresta entre eles. Todos os graus se tornam pares; constrói-se um circuito euleriano e depois se remove a aresta adicionada. O circuito então se abre em uma trilha cujas extremidades são precisamente os dois vértices de grau ímpar.
Modelar exige escolher a estrutura correta FATO
Estradas, dependências de software, moléculas e circuitos elétricos podem ser representados por grafos, mas não pelo mesmo modelo sem qualificação.
- Uma rede viária pode ser não direcionada ou direcionada e costuma carregar distâncias ou tempos de viagem.
- Um grafo de dependências geralmente é direcionado: nele, um ciclo expressa uma dependência circular.
- Um grafo molecular carrega rótulos nos átomos e nas ligações.
- Uma rede elétrica acrescenta grandezas físicas e leis que não estão contidas apenas na incidência.
O benefício da abstração, portanto, não é que um único algoritmo serviria em todos os casos. É separar a estrutura comum — vértices e arestas — das informações próprias do domínio e então escolher um teorema ou algoritmo cujas hipóteses correspondam exatamente ao grafo construído.
Resumo
Em um multigrafo finito não direcionado cujas arestas pertencem à mesma componente, a paridade dos graus determina se cada aresta pode ser percorrida exatamente uma vez: zero vértices de grau ímpar para um circuito e exatamente dois para uma trilha aberta.