Condição de Euler
Em Guimarães, o carteiro Rui quer entregar o correio passando por cada rua do bairro uma única vez e acabar onde começou. Será possível? Há uma forma de responder sem experimentar todos os percursos: basta olhar para os graus dos vértices do grafo.
O problema das pontes de Königsberg
Em 1736, os habitantes de Königsberg perguntavam se era possível passear pela cidade atravessando cada uma das sete pontes uma única vez. Leonhard Euler modelou o problema com um grafo: cada margem ou ilha é um vértice e cada ponte é uma aresta (há arestas múltiplas, porque há duas pontes entre os mesmos locais).
Euler provou que não era possível. A razão está nos graus dos vértices, como vamos ver.
Circuito de Euler e caminho de Euler
Podes passar várias vezes pelo mesmo vértice; o que não podes é repetir arestas.
O Teorema de Euler
O raciocínio anterior explica o resultado. No início do percurso sai-se do vértice sem entrar, e no fim entra-se sem sair. Num circuito, o início e o fim coincidem e as duas arestas desse vértice emparelham-se: todos os graus são pares. Num caminho aberto, o vértice inicial e o final ficam com uma aresta «sobrando», logo têm grau ímpar.
Repara que o número de vértices de grau ímpar é sempre par (a soma dos graus é o dobro do número de arestas), por isso nunca há exatamente 1 ou 3.
Para Königsberg, no esquema acima: A tem grau 5, B tem grau 3, C tem grau 3 e D tem grau 3. Há quatro vértices de grau ímpar, por isso o passeio é impossível. Respondemos assim à pergunta de Euler.
Sem desenhares os grafos, indica, justificando com base na paridade dos graus dos vértices, se cada um dos seguintes grafos conexos admite um circuito de Euler (percurso…
Sem desenhares os grafos, indica, justificando com base na paridade dos graus dos vértices, se cada um dos seguintes grafos conexos admite um circuito de Euler (percurso fechado que percorre cada aresta exatamente uma vez), apenas um caminho de Euler aberto (que começa e acaba em vértices diferentes) ou nenhum dos dois:
- a) Graus dos vértices: A: 2, B: 2, C: 2, D: 2.
- b) Graus dos vértices: A: 3, B: 3, C: 2, D: 4.
- c) Graus dos vértices: A: 3, B: 3, C: 3, D: 3, E: 2, F: 2.
Determinar o grau e encontrar o caminho
Na prática, começa sempre por contar os graus. Depois, se o teorema o permitir, constrói o percurso.
Um grafo conexo tem vértices {A, B, C, D, E} e arestas AB, AC, BC, BD, CD, CE e DE. a) Constrói uma tabela com o grau de cada vértice. b) O grafo admite um circuito de…
Um grafo conexo tem vértices {A, B, C, D, E} e arestas AB, AC, BC, BD, CD, CE e DE.
- a) Constrói uma tabela com o grau de cada vértice.
- b) O grafo admite um circuito de Euler? E um caminho de Euler aberto? Justifica as respostas.
- c) Se for caso disso, indica um caminho de Euler, escrevendo a sequência de vértices percorridos, e identifica o vértice inicial e o vértice final.
Eulerizar um grafo
Se o grafo tem vértices ímpares a mais, não há circuito de Euler. Mas podemos eulerizá-lo: acrescentar (ou repetir) arestas, ligando vértices de grau ímpar, até que todos os graus sejam pares. Repetir uma aresta significa passar duas vezes pela mesma rua.
Em resumo
-
Circuito de Euler: percorre cada aresta uma só vez e volta ao início.
-
Caminho de Euler aberto: percorre cada aresta uma só vez, começando e acabando em vértices diferentes.
-
Teorema de Euler (grafo conexo): circuito ⇔ todos os graus pares; caminho aberto ⇔ exatamente dois vértices de grau ímpar.
-
Com mais de dois vértices ímpares, não há nenhum dos dois.
-
Eulerizar é repetir arestas para emparelhar os vértices ímpares.
-
De volta ao início: o carteiro Rui só consegue o circuito se todos os cruzamentos (vértices) tiverem grau par.