Ciência de Dados - Corte Mínimo de Arestas

Qual é a definição de corte de arestas em um grafo G?

• Um subconjunto de vértices desconexos

• Um subconjunto de arestas que divide o grafo em dois subgrafos

• Um subconjunto de vértices que formam um ciclo

• Um subconjunto de vértices conectados por arestas

O que é um corte de arestas mínimo em um grafo G?

• O corte com o menor número de vértices

• O corte que divide o grafo em mais subgrafos

• O corte que possui a menor cardinalidade entre todos os cortes de arestas

• O corte que não possui laços

O que é uma contração de aresta em um grafo?

• A duplicação de uma aresta existente

• A remoção de uma aresta do grafo

• A identificação de dois vértices como um único vértice

• A adição de uma nova aresta ao grafo

Quantas operações de contração de arestas são realizadas no Algoritmo 3.3?

• 2n

• n-1

• n^2

• n

Qual é a complexidade máxima do Algoritmo 3.3 para encontrar um corte mínimo?

• O(2^n)

• O(n log n)

• O(n^2)

• O(n)

O que o Corolário 3.4 afirma sobre o Algoritmo 3.3?

• O algoritmo sempre retorna um corte mínimo

• O algoritmo retorna um corte mínimo com probabilidade maior que 2/n^2

• O algoritmo retorna um corte mínimo com probabilidade menor que 1/n

• O algoritmo nunca retorna um corte mínimo

Qual é a probabilidade de que o Algoritmo 3.3 encontre o corte mínimo de um grafo G?

• 1/n

• 2/n

• 1/n^2

• 2/n^2

Como o Teorema 3.5 sugere aumentar a probabilidade de obter uma resposta correta com o Algoritmo 3.3?

• Reduzindo o número de iterações de contração

• Alterando a estrutura do grafo de entrada

• Repetindo a execução do algoritmo várias vezes

• Aumentando o número de vértices no grafo

Qual é a complexidade de tempo de cada contração de aresta no Algoritmo 3.3?

• O(n log n)

• O(log n)

• O(1)

• O(n)

O que o Lema 3.3 afirma sobre as operações de contração de arestas em um grafo?

• As operações de contração duplicam o número de vértices

• As operações de contração mantêm o número de vértices constante

• As operações de contração sempre diminuem o número de vértices

• As operações de contração sempre aumentam o número de vértices