2024-181

Sobre o algoritmo MCS (Maximum Cardinality Search) em um grafo $G$ qualquer, considere as afirmações:

1) O MCS visita os vértices de $G$ em uma ordem de eliminação simplicial.

2) O MCS deve ser inicializado em qualquer vértice $v$ tal que $d(v)=\mathrm{\Delta }(G)$.

4) O MCS é um algoritmo que custa $O(|V(G)|)$ e objetiva verificar se $G$ é cordal.

8) Se o MCS fornece uma eliminação simplicial, então $G$ é perfeito.

A soma das alternativas corretas é:

A) 6

B) 7

C) 12

D)14

E) NDA

Ideia Original De: Gabriel Cruz Vitale Torkomian