A Teoria dos Grafos

[pic 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:

1. (0,25 pontos) a função g que é parte definição formal do grafo;  
2. (0.25 pontos) a matriz e a lista de adjacência;

 

[pic 2]

 

Questão 1

Questão 2: ( 0,25 pontos) Considere as seguintes afirmações:

 

1. - 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 ).  

 

1. - 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. 

 

1. Apenas a afirmação I diz respeito a um conceito que estende (torna mais geral) o conceito de grafos.
2. As afirmações I e II dizem respeito a conceitos que estendem (tornam mais geral) o conceito de grafos.
3. Sem generalizações, as afirmações I e II apresentam exemplos de uso da teoria dos grafos.
4. Apenas a afirmação II diz respeito a um conceito que estende (torna mais geral) o conceito de grafos.
5. 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.  

...