Questões

A Teoria dos Grafos é uma área da matemática aplicada amplamente utilizada em várias disciplinas de informática e gestão. Considere os conceitos de grafos, caminhos mínimos e algoritmos de otimização. Qual das seguintes afirmações é correta em relação ao uso da matemática em algoritmos de grafos? 

Considere um grafo dirigido G=(N, A) em que o conjunto N é composto por seis nós, numerados de 1 a 6. O conjunto de arcos A é o apresentado a seguir na forma de lista de adjacência:

1 → 2, 4, 5

2 → 3

3 → 2

4 → 2, 3

5 → 4

6 → 1, 5

Tendo em vista a estrutura desse grafo, considere as afirmativas a seguir.

I  →  Trata-se de um grafo conexo, porém não fortemente conexo.

II  →  A sequência de nós 6, 1, 5, 2, 4, 3 representa uma possível ordem de visita aos nós para um percurso em amplitude.

III  →  A sequência de nós 6, 1, 2, 4, 3, 5 representa uma possível ordem de visita aos nós para um percurso em profundidade.

IV  →  Existe um caminho ligando os nós 6 e 2 composto por uma sequência de 5 arcos distintos entre si.

Estão corretas

Considere uma árvore que contém todo e qualquer nó em um grafo, mais formalmente, uma spanning tree de um grafo G = (N, E) e um grafo G' = (N, E') tal que E' é um subconjunto de E, G' é conectado, G' não contém nenhum ciclo e G' contém todos os nós originais em G.

Se cada enlace tiver um custo associado e o custo de uma árvore for a soma dos custos dos enlaces, é correto afirmar que uma árvore cujo custo seja o mínimo entre todas as spanning trees é denominada: 

Considerando uma estrutura de dados do tipo “lista”, se tanto as operações de inserção quanto as operações de remoção são realizadas somente em um de seus extremos, então pode-se afirmar que essa estrutura recebe o nome de: