MO640 - Questão para a prova oral

Número: 047

Enunciado:
Saad Mneimneh introduz um novo conceito, chamado de separação . Qual das seguintes afirmações é certa?:

1. Se A separa B e C, então B não separa a A e C.
2. A é uma separação entre dois componentes B e C se qualquer aresta imaginária (corda) no grafo de interleaving entre um vértice de B e um vértice de C, cruza um vértice desejável de A.
3. Uma reversão definida por dois vértices em dois componentes A e B, tem como consequência que todos os componentes bons que separam A e B se transformem em ruins, e todos os ruins que separam A e B se transformem em bons.
4. Uma componente qualquer é um obstáculo se ele não separa outros dois componentens ruins.
5. NDA

Autor(a): Matthias Gallé