5o TESTE
Teoria de Grafos
1
1. Obtém o caminho mais curto de A para G.1
R: Na página 56 diz que o caminho mais curto descobre-se tomando
em cada vértice a aresta mais curta. Isto não é verdade em geral. Por
exemplo, se EG em vez de 8 medisse 1, partindo de D para G terı́amos
DEG = 36 e DF G = 43. Contudo no segundo percurso tomamos
sempre a aresta menor enquanto no primeiro tomamos sempre a aresta
maior. Portanto a regra fornecida no manual para determinar o menor
percurso (e o maior) não funciona.
Neste caso, tal como a figura está feita, todos os caminhos de A para
G têm o mesmo número de vértices (e todos os caminhos passam por
D). Contudo aparece em cima 40 e em baixo 10 o que sugere haver
uma aresta de B para E e outra de C para F . Neste caso os caminhos
mais curtos são ABDCF G e ABEG que medem 78. Todos os outros
medem mais de 78.2
Se não existirem as arestas BE e CF , então, de facto, o caminho mais
curto é ABDF G ou ABDEG.
2. Determina o diâmetro de cada um dos seguintes grafos.3
R: O grafo A tem diâmetro 3. O grafo B tem diâmetro 5. O grafo C
tem diâmetro 2. O grafo D tem diâmetro 2.
3. Problema do carteiro.4
1
Página 55.
Aparece um 19 perto do A e um 11 perto do G que parecem perdidos.
3
Página 56.
4
Página 58.
2
2
R: O grafo não é euleriano pelo que é preciso acrescentar arestas (i.e.,
repetir ruas) por forma a permitir ao carteiro voltar ao ponto de partida. No manual sugere-se que o carteiro repita as ruas BE e CF .
Contudo, o vértice C fica com grau impar e portanto o grafo não ficaria euleriano.
A solução certa parece ser repetir as ruas BF e F E.
4. Construa um grafo de 4 vértices dois dos quais com grau 3 e os outros
com grau 2.5
R: Um quadrado com uma diagonal.
5. Tente construir um grafo com 5 vértices, três dos quais com grau ı́mpar
e dois com grau par.6
R: É impossı́vel pelo Lema dos apertos de mão.
6. Exercı́cio 6. página 66.
R: Um T com 4 vértices. Não é euleriano porque todos os vértices t em
grau ı́mpar; não é hamiltoniano porque é preciso passar duas vezes no
único vértice que não está num dos extremos do T .7
5
Exercı́cio 2. página 66
Exercı́cio 3. página 66
7
Os exercı́cios 9 e 10 da página 67 não interessam.
6
3
6o TESTE
4
1. Considere a seguinte figura:
C
H
D
G
B
A
E
F
Será possı́vel desenhar esta figura sem levantar o lápis e passando uma
e uma só vez por cada aresta?
R: Este grafo é semi-euleriano porque só dois vértices (A e G) têm grau
ı́mpar. Portanto é possı́vel começar em A e acabar em G percorrendo
todas as arestas uma só vez.
Como se pode descobrir um tal caminho? Vamos ver como se faz isto
no caso mais simples da casa tradicional.
Se descobrirmos um caminho na Fig.2, então temos um caminho na
Fig.1. Facilmente se vê que AD0 B 0 EABCDE é um caminho na Fig.2,
pelo que ADBEABCDE é um caminho na Fig.1. Em geral, na Fig.2 é
5
muito fácil descobrir os caminhos possı́veis e daı́ passa-se aos possı́veis
na Fig.1.
C
C
B
D
A
E
B
D
A
E
B’
D’
Usando a mesma estratégia podemos resolver o problema para
C
H
D
G
B
A
E
F
Da mesma forma alteramos ligeiramente esta figura para tornar mais
fácil descobrir o caminho que já sabemos existir.
A ideia é começar em A e percorrer todas as arestas até acabar em G.
6
C
H
D
B
G
A
F
E
D’
B’
Uma solução possı́vel é AEB 0 D0 ABCDEF GDHG. Portanto, na figura
original, um dos caminhos possı́veis será AEBDABCDEF GDHG.
2. Diga se é possı́vel desenhar esta figura sem levantar o lápis e passando
uma e uma só vez por cada aresta?
C
B
A
E
D
H
F
G
R: Este grafo é semi-euleriano porque só dois vértices (A e G) têm grau
ı́mpar. Portanto é possı́vel começar em A e acabar em G percorrendo
todas as arestas uma e uma só vez.
7
Para descobrir um caminho vamos seguir o mesmo processo usado na
pergunta anterior.
C
E
D
F
B
H
G
A
D’
Agora é fácil ver que um caminho possı́vel será AHGD0 ABHF BCDEF G.
Logo um caminho na figura original será AHGDABHF BCDEF G.
3. Um carteiro pretende entregar correspondência ao longo de um percurso
da seguinte forma:
B
E
D
A
C
H
F
G
8
Supondo que a estação de correios de onde parte é em B e que a mulher
o vai buscar de carro no final do trabalho, diga onde devem marcar o
encontro por forma a que ele não percorra a mesma rua mais de uma
vez.
R: O grafo é semi-eulariano porque só dois vértices (B e F ) têm grau
ı́mpar. Portanto há um caminho que o leva a passar por todas as ruas,
mas só passa uma vez em cada uma delas: BAEF GHBF .
4. Suponha que, com os dados do exercı́cio anterior, o carteiro pretende
acabar o dia de trabalho na estação de correios. Indique qual das ruas
deverá ele percorrer duas vezes?
R: Se percorrer a rua BF duas vezes fica com um grafo eulariano.
9