EXERCÍCIOS DE TEORIA DOS GRAFOS
1.) Considere a tabela de tarefas a seguir para a construção de uma casa de madeira:
TAREFAS PRÉ-REQUISITOS DIAS
1. Limpeza do terreno Nenhum 4
2. Produção e colocação da fundação 1 3
3. Produção da estrutura 2 7
4. Colocação do telhado 3 6
5. Colocação das tábuas externas 3 4
6. Instalação do encanamento e fiação 4e5 6
7. Colocação das janelas e portas 3 5
8. Instalação das janelas e portas 6 5
9. Pintura do interior 7e8 5
a) Construa o diagrama PERT;
b) Determine o tempo mínimo para construir a casa;
c) Forneça o caminho crítico. (maior)
SOLUÇÃO
a)
5(4) 6(6)
3(7)
8(5)
1(4) 2(3) 4(6)
9(5)
7(5)
1
2.) Considere o grafo:
4
a4
a3
a5
3 5
a2 a6
7
2
a1 a7
6
1
e responda as seguintes perguntas:
a) O grafo é simples?
b) O grafo é completo?
c) O grafo é conexo?
d) É possível encontrar dois caminhos do nó 3 para o nó 6?
e) É possível encontrar um ciclo?
f) É possível encontrar um arco cuja remoção transforma o grafo em um grafo acíclico?
g) É possível encontrar um arco cuja remoção transforma o grafo em um grafo não-conexo?
3.) Esboce um grafo com as seguintes características:
a) simples com 3 nós, cada um com grau 2;
b) 4 nós e ciclos de comprimento 1, 2, 3 e 4;
c) não completo com 4 nós, cada um com grau 4.
2
4.) Observe o seguinte grafo direcionado:
6
a6 5
a7
a5
a10
1
4
a1 a9 a8
a2
a4
2
a11 a3 3
e responda as seguintes perguntas:
a) Quais são os nós acessíveis a partir do nó 3?
b) Qual o caminho mais curto do nó 3 para o nó 6?
c) Qual o caminho de comprimento 8 do nó 1 para o nó 6?
5.) Observe o grafo direcionado abaixo:
a2
2
a1 a3
a4
1 3
a5
a7
a6
4
e responda as seguintes perguntas:
a) Existe um caminho de comprimento 5 do nó 1 para o nó 4?
b) É possível acessar o nó 1 de algum outro nó?
c) Quais são os ciclos deste grafo?
3
6.) Qual dos grafos não é isomorfo aos outros e por quê?
(a) (b) (c)
7.) Qual dos grafos não é isomorfo aos outros e por quê?
(a) ( b) (c) (d)
Nos exercícios a seguir ( 8 , 9 e 10 ) verifique se os grafos são isomorfos. Se forem, forneça a bijeção
(no caso de grafos simples) ou bijeções que estabelecem o isomorfismo. Se não forem, expli- plique
por quê.
(Bijeção = mapear os nós/arestas de um grafo de origem em um grafo de destino)
8.) (a)
1 (b)
a
5 e
2 b
4 3 d c
4
9.)
1 b
a c
6 2
3
5
4 f e d
(a) ( b)
10.)
2 3
4 e b
f
5
6
(a) d c
(b)
5
11.) Sabendo que os grafos abaixo são isomorfos determine um par de bijeções que garante o isomor-
fismo.
a
1
e1 e2
a4 a5 a1 e3
b
e4
a6 e6
2 3 c
e5
a3 a7 a2 e7
d
4
(a) (b)
12.) Construa todos os grafos não-isomorfos com 3 nós.
6
13.) Apresentamos abaixo um conjuntos de grafos não-isomorfos com 4 nós que chamaremos de G4:
(a) (b) (c) (d) (e)
1 4 1 4 1 4 1 4 1 4
2 3 2 3 2 3 2 3
2 3
(f) (g) (h)
1 4 1 4 1 4
2 3 2 3 2 3
Verifique se os grafos abaixo pertencem a esta coleção ou se são isomorfos a algum dos grafos
desenhados acima:
13.1)
1 4
RESPOSTA
2 3
13.2)
1 2 3 4 RESPOSTA
13.3)
4
RESPOSTA
1 3
2
7
13.4)
1 4 RESPOSTA
3 2
13.5)
1 4
RESPOSTA
3
2
13.6)
1 4 RESPOSTA
3
2
13.7)
RESPOSTA
1 2 3 4
13.8)
2
RESPOSTA
1 4 3
