Grafos de Euler: aplicações · Matemática 11.º ano MACS

Do mapa ao grafo

Para decidir se um percurso é possível, primeiro simplificamos o mapa e ficamos só com o essencial:

cada cruzamento (ou margem, ou ilha) passa a ser um vértice;
cada rua (ou ponte) passa a ser uma aresta, que liga os dois vértices que une.

Se duas ruas ligarem os mesmos dois cruzamentos, desenhamos duas arestas entre esses vértices (arestas múltiplas). O que interessa é só o que está ligado a quê, não o comprimento nem a forma real das ruas.

O grau de um vértice é o número de arestas que nele terminam. Para o determinar, conta as arestas que saem de cada vértice. No fim, confirma o total: a soma de todos os graus é o dobro do número de arestas, porque cada aresta tem duas pontas.

Neste grafo, o vértice $A$ tem as arestas $AB$, $AC$, $AE$ e $AF$, logo o seu grau é $4$. O vértice $B$ tem apenas $AB$ e $BC$, logo o seu grau é $2$.

Existe um percurso sem repetir ruas?

Recorda o resultado que já conheces (Teorema de Euler), para um grafo conexo:

O porquê está na paridade. Sempre que o percurso passa por um vértice, «entra» por uma aresta e «sai» por outra, usando as arestas aos pares. Por isso, os vértices onde o percurso não começa nem acaba têm de ter grau par.

Circuito de Euler nas ruas de Guimarães

No grafo da figura, as ruas são $AB$, $BC$, $CD$, $DE$, $EF$, $FA$, $AC$, $AE$ e $CE$. É possível percorrer cada rua exatamente uma vez, começando e terminando em $A$?

Graus. $A$: $AB, FA, AC, AE$, logo $4$. $B$: $AB, BC$, logo $2$. $C$: $BC, CD, AC, CE$, logo $4$. $D$: $CD, DE$, logo $2$. $E$: $DE, EF, AE, CE$, logo $4$. $F$: $EF, FA$, logo $2$.

Condição de Euler. O grafo é conexo e todos os graus são pares ($4, 2, 4, 2, 4, 2$). Existe, portanto, um circuito de Euler, e pode começar em qualquer vértice, em particular em $A$.

Construir o percurso. Dá primeiro uma volta ao «hexágono»: $A \to B \to C \to D \to E \to F \to A$. Sobram as ruas $AC$, $CE$ e $EA$, que formam um triângulo. Percorre-o: $A \to C \to E \to A$.

A tua vez. Escreve o percurso completo e confirma que passaste por $9$ arestas, uma só vez cada.

$A \to B \to C \to D \to E \to F \to A \to C \to E \to A$. Contando: $AB, BC, CD, DE, EF, FA, AC, CE, EA$ são $9$ ruas, todas distintas.

Pratica★☆☆

A Câmara Municipal de Guimarães quer inspecionar a iluminação de Natal de todas as ruas do centro histórico. Num mapa simplificado, os cruzamentos são os vértices {A, B,…

A Câmara Municipal de Guimarães quer inspecionar a iluminação de Natal de todas as ruas do centro histórico. Num mapa simplificado, os cruzamentos são os vértices {A, B, C, D, E, F} e as ruas são as arestas AB, BC, CD, DE, EF, FA, AC, AE e CE.

a) Determina o grau de cada vértice.
b) É possível fazer um percurso que comece e termine no mesmo cruzamento e percorra cada rua exatamente uma vez? Justifica com a condição de Euler.
c) Indica um percurso nessas condições com início no cruzamento A.

Resolver

Pontes e passeios

Foi com um problema deste tipo que nasceu a teoria dos grafos: as pontes de Königsberg. Em vez de uma cidade antiga, vejamos um parque.

No Parque da Cidade do Porto, duas ilhas, $X$ e $Y$, estão no meio de um lago, e há pontes entre elas e as margens $N$ e $S$. Modelamos cada margem e cada ilha por um vértice e cada ponte por uma aresta. Onde há duas pontes entre os mesmos sítios, há duas arestas.

Quando o passeio não é possível, uma solução é construir uma ponte nova. Cada aresta acrescentada soma $1$ ao grau das suas duas pontas, por isso troca a paridade desses dois vértices. Se ligarmos dois vértices ímpares, ficamos só com dois vértices ímpares, e passa a existir um caminho euleriano.

Pratica★★☆

No Parque da Cidade do Porto, um lago artificial tem duas ilhas, X e Y. As ilhas e as margens Norte (N) e Sul (S) estão ligadas por pontes de madeira: duas pontes entre…

No Parque da Cidade do Porto, um lago artificial tem duas ilhas, X e Y. As ilhas e as margens Norte (N) e Sul (S) estão ligadas por pontes de madeira: duas pontes entre N e X, uma ponte entre X e Y, duas pontes entre Y e S e uma ponte entre N e S.

a) Modela a situação por um grafo em que as margens e as ilhas são vértices e as pontes são arestas. Indica o grau de cada vértice.
b) Mostra que não é possível fazer um passeio que atravesse cada ponte exatamente uma vez. Justifica com a paridade dos graus.
c) A junta de freguesia quer construir uma nova ponte de modo a tornar o passeio possível, sem obrigar a regressar ao ponto de partida. Entre que dois vértices deve construí-la? Justifica a tua escolha.

Resolver

Eulerizar: repetir o mínimo de ruas

Muitas vezes não podemos construir ruas novas, mas podemos repetir uma rua já existente. É o caso de uma carrinha da recolha de lixo que tem de começar e acabar no armazém: passar duas vezes pela mesma rua não é problema, apenas gasta tempo e combustível.

Eulerizar um grafo é repetir algumas arestas (acrescentar uma «cópia» de cada uma) até todos os vértices ficarem com grau par. Depois, o grafo resultante tem um circuito de Euler. O que se pretende é repetir o mínimo de arestas, porque cada repetição é um custo.

O processo é este:

Identifica os vértices de grau ímpar. Há sempre um número par deles.
Emparelha-os pelas ruas mais curtas (ou pelo menor número de arestas) possível: cada par é ligado por uma aresta repetida, ou por um pequeno caminho de arestas repetidas.
Constrói o circuito de Euler no grafo eulerizado.

O bairro da LimpaÉvora

O grafo tem os vértices $A$, $B$, $C$, $D$ e as arestas $AB$, $BC$, $CD$, $DA$ e $AC$. O armazém fica em $B$. A carrinha tem de começar e acabar em $B$. Qual é o número mínimo de ruas que se têm de repetir?

Graus. $A$: $AB, DA, AC$, logo $3$. $B$: $AB, BC$, logo $2$. $C$: $BC, CD, AC$, logo $3$. $D$: $CD, DA$, logo $2$.

Existe circuito? Há dois vértices ímpares, $A$ e $C$. Não há circuito de Euler, portanto não se pode começar e acabar em $B$ sem repetir nenhuma rua. Há, em contrapartida, um caminho euleriano que começa num dos ímpares e acaba no outro (por exemplo, de $A$ a $C$).

Eulerizar. Os vértices ímpares $A$ e $C$ são adjacentes: repetir a rua $AC$ torna ambos pares ($4$ e $4$). Basta repetir 1 rua. Com menos não é possível, porque repetir zero ruas deixa dois vértices ímpares.

A tua vez. Escreve um percurso que comece e acabe em $B$ e passe por todas as ruas, com $AC$ percorrida duas vezes.

$B \to A \to C \to A \to D \to C \to B$. As arestas são $BA, AC, CA, AD, DC, CB$: as $5$ ruas originais, com $AC$ repetida, num total de $6$ ruas percorridas.

Pratica★★★

A empresa de recolha de resíduos LimpaÉvora percorre diariamente as ruas de um bairro representadas pelo grafo com vértices {A, B, C, D} e arestas AB, BC, CD, DA e AC. O…

A empresa de recolha de resíduos LimpaÉvora percorre diariamente as ruas de um bairro representadas pelo grafo com vértices {A, B, C, D} e arestas AB, BC, CD, DA e AC. O armazém da empresa fica no cruzamento B.

a) Mostra que é possível percorrer todas as ruas exatamente uma vez, indicando onde deve começar e onde deve terminar esse percurso. Escreve um percurso nessas condições.
b) A carrinha tem de começar e terminar o percurso no armazém (cruzamento B). É possível fazê-lo sem repetir nenhuma rua? Justifica.
c) Sendo obrigatório começar e acabar em B, qual é o número mínimo de ruas que terão de ser percorridas duas vezes? Indica um percurso que atinge esse mínimo.

Resolver

Vamos agora fechar o gancho inicial: na iluminação de Natal de Guimarães, todos os graus eram pares, por isso a equipa podia começar e acabar no mesmo cruzamento, passando por cada rua uma só vez.

Em resumo

Para modelar, os cruzamentos (ou margens e ilhas) são vértices e as ruas (ou pontes) são arestas. Duas ruas entre os mesmos sítios são duas arestas.
O grau de um vértice é o número de arestas que lá terminam; a soma dos graus é o dobro do número de arestas.
Num grafo conexo: todos os graus pares ⇒ circuito de Euler (começa-se em qualquer vértice e volta-se a ele); exatamente dois graus ímpares ⇒ caminho euleriano (de um ímpar ao outro); mais de dois ímpares ⇒ não há percurso.
Ligar dois vértices ímpares por uma aresta nova (ou repetida) é o que ajuda a tornar o percurso possível.
Eulerizar é repetir o menor número de arestas até todos os graus ficarem pares; depois constrói-se o circuito.

Vamos praticar! 1 exercícios de nível médio neste tema

★★☆ No Parque da Cidade do Porto, um lago artificial tem duas ilhas, X e Y. As ilhas e as…