Questão 769213

• Banca: CESPE / CEBRASPE
• Órgão: Banco da Amazônia
• Ano: 2012
• Provas: CESPE - 2012 - Banco da Amazônia - Técnico Científico - Administração de Dados
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Grafos

Um grafo completo contém pelo menos um subgrafo ponderado.

• C. Certo
• E. Errado

Gabarito: E

Comentários

• Um grafo completo tem n vértices (Kn). Os arcos para Kn são n(n-1)/2. O n° de relações possíveis são: 1,1,2,4,10,26 etc
  
  1 é possível se houver 1 ou 2 vértices, porque só pode haver uma conexão entre 2 pontos.Nesse caso, NÃO HÁ SUBGRAFOS.
  
  http://www.gpec.ucdb.br/pistori/disciplinas/discreta/aulas/grafos.htm
  
  post scriptum: interessante notar que o mesmo conceito tem a ver com a topologia de full-mesh network, onde o n° de ligações entre os nodes é uma função quadrática (n^2)-n/2
• São dois conceitos diferentes! Completo e ponderado!
  Um grafo é completo quando todo vértice tiver uma aresta para qualquer outro vértice. Um grafo é ponderado quando cada aresta possuir um valor associado a ela (um peso).
  Um grafo completo pode ser ponderado ou não. Ele vai possuir um subgrafo ponderado caso ele seja ponderado!
• Exemplo de um grafo completo:
  

• Grafo completo - É um grafo simples onde cada vertice se conecta a todos os outros vertices - Todo mundo se conecta a todo mundo (Há uma especie de loop no grafo... É um circuito fechado).

  Grafo Regular - Onde todos os vertices possuem o mesmo grau - ou seja... Todos possuem a mesma quantidade de ligações.

  Resumidamente - Todo grafo completo é regular, mas nem todo regular é completo :)

• Força Guerreiro!!!!!!