076-2004

MO640 - Questão para a prova oral
Número: 076
Enunciado:
A respeito de breakpoint graphs e grafos de sobreposição de arcos, tais como definidos no artigo de Bergeron, é correto afirmar que:

1. Em um breakpoint graph, dois arcos se sobrepõem se, e somente se, seus suportes são ortogonais.
2. O breakpoint graph um grafo bipartido.
3. O número de componentes conexas do breakpoint graph é igual ao número de componentes conexas do grafo de sobreposição de arcos.
4. O número de componentes conexas do grafo de sobreposição de arcos é igual ao número de intervalos enquadrados da permutação original.
5. NDA

Autor(a): Marília Felippe Chiozo