2024-182

Considere as afirmações abaixo:

I-) O grafo complementar do grafo casa é perfeito.

II-) O grafo abaixo é cordal pois é triangulado:

III-) Todo grafo perfeito possui representação por intervalos.

IV-) O grafo abaixo possui 2 vértices simpliciais e 36 ordens de eliminação perfeita distintas:

Assinale a alternativa CORRETA:

a-) Somente IV está CORRETA

b-) Somente II está CORRETA

c-) Somente I está CORRETA

d-) Somente III está CORRETA

e-) N.D.A.

Ideia original de: Guilherme Terrell

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) = \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