Ciência de Dados - Noções Básicas de Teoria de Grafos

Qual é a definição de conectividade de vértices em um grafo G?

• Grau mínimo de um vértice

• Cardinalidade do menor corte de vértices

• Quantidade de arestas no grafo

• Número de vértices no grafo

O que é um grafo k-conexo em vértices?

• Um grafo sem corte de vértices de tamanho menor que k

• Um grafo sem ciclos

• Um grafo sem vértices isolados

• Um grafo com k vértices

O que é um digrafo?

• Um grafo sem ciclos

• Um grafo sem vértices

• Um grafo com direção nas arestas

• Um grafo sem arestas

Qual é a definição de grau de entrada de um vértice em um digrafo?

• Número de vértices adjacentes

• Número de arestas convergentes ao vértice

• Número de arestas incidentes ao vértice

• Número de arestas divergentes do vértice

O que é uma árvore direcionada enraizada em um digrafo?

• Um digrafo sem ciclos

• Um digrafo com raiz e grau de entrada nulo

• Um digrafo com apenas um vértice

• Um digrafo sem arestas

Qual é a complexidade de espaço da matriz de adjacências de um grafo?

• O(n)

• O(n^2)

• O(m)

• O(n + m)

O que é a estrutura de adjacências em um grafo?

• Um conjunto de vértices isolados

• Um conjunto de listas de adjacências para cada vértice

• Um conjunto de arestas

• Um conjunto de ciclos

Qual é a representação mais comum nas implementações de algoritmos em grafos?

• Matriz de incidências

• Lista de adjacências

• Matriz de adjacências

• Matriz de cliques

O que é a matriz clique de um grafo?

• Uma matriz de custos

• Uma matriz de adjacências

• Uma matriz de incidências

• Uma matriz binária que representa cliques maximais

Se um grafo G admitir cortes de vértices e arestas, ambos de tamanho n-1, então G é o grafo completo Kn. Certo ou Errado?

• Certo

• Depende do número de vértices

• Errado

• Não é possível determinar