Quiz sobre Grafos e Problemas Clássicos

No problema das Pontes de Königsberg, qual foi a conclusão de Euler?

• Existe um caminho que cruza cada ponte exatamente uma vez e volta ao início.

• Não existe um caminho que cruze cada ponte exatamente uma vez e retorne ao ponto de partida.

• O grafo correspondente é bipartido.

• O grafo possui um circuito hamiltoniano.

Em redes sociais modeladas como grafos, o que representam os vértices?

• As conexões (amizades)

• Os usuários/pessoas

• As comunidades

• Os pesos dos relacionamentos

Em problemas de navegação (mapas e rotas), os pesos nas arestas normalmente representam:

• A quantidade de vizinhos

• O grau dos vértices

• Tempo ou distância

• O número de componentes conexas

Sobre o Problema do Caixeiro Viajante (TSP), assinale a alternativa correta:

• É resolvido em tempo polinomial por Dijkstra.

• É NP-difícil, sem algoritmo eficiente conhecido que resolva exatamente todos os casos.

• É um problema simples de resolver com força bruta.

• Pode ser resolvido em tempo linear.

A ordem de um grafo G é dada por:

• |E(G)|

• |V(G)|

• A soma dos graus dos vértices

• O número de componentes conexas

O tamanho de um grafo G é:

• |E(G)|, a quantidade de arestas

• |V(G)|, a quantidade de vértices

• O maior grau do grafo

• O menor grau do grafo

Um laço (aresta que liga um vértice a ele mesmo) contribui quanto para o grau do vértice?

• 0

• 1

• 2

• 3

Um grafo é conexo se:

• Possui pelo menos um ciclo

• Existe caminho entre quaisquer dois vértices

• Todos os graus são pares

• Não possui arestas

Classificações: um vértice de grau 0 é __ e um vértice de grau 1 é __.

• isolado; pendente

• pendente; isolado

• corte; regular

• central; periférico

A sequência de graus de um grafo é:

• A sequência crescente dos pesos das arestas

• A sequência decrescente dos graus dos vértices

• A lista de vértices de grau ímpar

• O conjunto dos graus distintos