Teoria de Grafos Exercícios

Prévia do material em texto

1 
 
Bacharelado em Ciência da Computação e Sistemas de Informação 3o. 
Lista de Exercícios – Teoria dos Grafos 
Nome: 
RA.: Curso: Turma: 
 
 
Questão 1: (0,5 ponto) Para o grafo direcionado ilustrado, apresente: 
a) (0,25 pontos) a função g que é parte definição formal do grafo; 
b) (0.25 pontos) a matriz e a lista de adjacência; 
 
1 2
3
x
y
z
t
 
Questão 1 
Questão 2: ( 0,25 pontos) Considere as seguintes afirmações: 
 
I - A teoria dos grafos é aplicável a diversos problemas de interesse prático. Confira-se o que Roger Pressman 
afirma: “o teste do software começa criando um grafo de objetos importantes e suas relações e então 
imaginando uma série de testes que abrangerá o grafo de forma que cada projeto e relação sejam exercitados 
e os erros sejam descobertos. ...Para executar esses passos, você começa criando um grafo – uma coleção de 
nós que representam objetos, ligações que representam as relações entre objetos, pesos de nó que descrevem 
as propriedades de um nó, (por exemplo o valor específico de um dado ou comportamento de estado) e pesos 
de ligação (link weights ) que descrevem alguma característica de uma ligação. (Pressman, R. 2011, Engenharia 
de Software Uma Abordagem Profissional ). 
 
II - A teoria dos grafos é aplicável a diversos problemas de interesse prático. Um exemplo diz respeito ao 
gerenciamento de recursos em sistemas operacionais. Considere-se o seguinte texto: “...É possível representar 
graficamente a alocação de recursos entre as tarefas de um sistema concorrente. A representação gráfica provê 
uma visão mais clara da distribuição dos recursos e permite detectar visualmente a presença de esperas 
circulares que podem caracterizar impasses. Em um grafo de alocação de recursos é possível representar 
graficamente a alocação de recursos entre as tarefas de um sistema concorrente. A representação gráfica provê 
uma visão mais clara da distribuição dos recursos e permite detectar visualmente a presença de esperas 
circulares que podem caracterizar impasses. 
.” (Mazziero, C. Sistemas Operacionais Conceitos e Mecanismos, 2017). 
 
Considere as seguintes alternativas e assinale, SEM RASURAR a alternativa correta. 
 
a) Apenas a afirmação I diz respeito a um conceito que estende (torna mais geral) o conceito de grafos. 
b) As afirmações I e II dizem respeito a conceitos que estendem (tornam mais geral) o conceito de grafos. 
c) Sem generalizações, as afirmações I e II apresentam exemplos de uso da teoria dos grafos. 
d) Apenas a afirmação II diz respeito a um conceito que estende (torna mais geral) o conceito de grafos. 
e) As afirmações I e II dizem respeito a conceitos que reduzem o conceito de grafos. 
 
 
Questão 3: (2,75 pontos)Responda as perguntas a seguir sobre o grafo na figura a seguir. 
 
i. (0.25 pontos) O grafo e simples? 
ii. (0.25 pontos) O grafo é completo? 
 2 
iii. (0.25 pontos) O grafo é conexo? 
iv. (0.25 pontos) Encontre dois caminhos de A para D. 
v. (0.25 pontos) Encontre um ciclo de comprimento 6. 
vi. (0.25 pontos) Este grafo divide o plano em quantas regiões? Justifique sua resposta. 
vii. (0,25 ponto) Apresente o algoritmo de Dijkstra para encontrar o caminho mínimo 
entre os nós A e E. 
viii. (0,25 ponto) Apresentar a matriz de adjacência modificada do grafo. 
ix. (0,75 ponto) Apresentar as diversas iterações para a obtenção da árvore 
geradora mínima; 
 
 
B C
A D
F E
G H
3
2
1
4
6
1
2
1
1
5
8
5
4
 
Questão 4: (0,5 pontos) Pede-se: 
a) (0,25 ponto) O grafo K3,3 é planar? Justifique sua resposta. 
b) (0,25 ponto) Para o grafo seguinte, apresente: o número cromático e o mapa dual; 
B C
F E
G
H
 
Questão 5: (0,25 pontos) O grafo seguinte é homeomorfo a K5 ou a K3,3?. 
 
 
 
 
 
 
 
Questão 6: (0,5pontos) Considere o grafo K6. 
b 
c 
d 
e f 
g 
h 
i 
j 
 3 
a) (0,25 ponto) Pergunta-se: quantas arestas devem ser removidas deste grafo a fim de se obter 
um grafo planar? 
b) (0,25 ponto) A relação de Euler é válida para o grafo obtido no item a) ? 
 
 
 
 
 
 
Questão 7: (0,25 pontos): Mostre que os dois grafos abaixo são isomorfos