Questão 1348759

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

Acerca dos conceitos de grafo, assinale a opção correta.

• A. O laço de um vértice v é o número de arestas que incidem em v.
• B. Um grafo é considerado completo quando todos seus vértices têm o mesmo grau k.
• C. Os exemplos de tipos de grafos incluem pseudógrafos, multígrafos, grafos com autolaços e grafos dirigidos.
• D. Dois grafos são chamados bipartidos quando são essencialmente iguais e há correspondência entre seus vértices e suas arestas.
• E. Os grafos esparsos podem ser compactamente representados utilizando-se grafos completos.

Gabarito: C

Comentários

• a) O grau de um vértice v é o número de arestas que incidem em v.

  b) Um grafo é considerado completo quando todos seus vértices têm o mesmo grau k. CONTRA-EXEMPLO: Cn. Completo quando um vértice é conectado a todos os outros vertices.

  c) Ok

  d) Um grafo pode ser bipartido se tem ciclo impar.

  e) Um grafo completo não é esparso, pelo contrário.