Questão 802915

• Banca: CESPE / CEBRASPE
• Órgão: INMETRO
• Ano: 2010
• Provas: CESPE - 2010 - INMETRO - Pesquisador Tecnologista - Metrologia em Informática
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Grafos

Assinale a opção correta a respeito de teoria dos grafos.

• A. Um caminho é dito simples se passa exatamente uma vez por cada um dos vértices do grafo, e é unitário se passa exatamente uma vez por cada uma das arestas.
  
• B. O comprimento de um percurso em um grafo não valorado corresponde à soma dos custos de percorrer cada aresta, e em um grafo valorado é igual ao número de arestas que o compõem.
  
• C. Um ciclo que passa por todas as arestas de um grafo é dito hamiltoniano, e um circuito elementar que passa por todos os vértices denomina-se euleriano.
  
• D. O problema do caixeiro viajante consiste em analisar todos os circuitos hamiltonianos existentes para n - 1 pontos.
  
• E. Segundo o conceito de conexidade em grafos orientados, não é necessário que haja um caminho ligando qualquer par de vértices; se isso ocorrer, diz-se que o grafo é fortemente conexo, tal que, dados dois vértices, qualquer um pode ser atingido a partir do outro.
  

Gabarito: E

Comentários

• a) Um caminho é dito simples se passa exatamente uma vez por cada um dos vértices do grafo, e é unitário se passa exatamente por apenas uma aresta.

  b) O comprimento de um percurso em um grafo valorado corresponde à soma dos custos de percorrer cada aresta, e em um grafo não valorado é igual ao número de arestas que o compõem.

  c) Um caminho que passa por todas as arestas de um grafo é dito euleriano, e um circuito elementar que passa por todos os vértices denomina-se hamiltoniano.

  d) O problema do caixeiro viajante consiste em analisar todos os circuitos hamiltonianos existentes para n + 1 pontos.