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:
- Em um breakpoint graph, dois arcos se sobrepõem se, e somente
se, seus suportes são ortogonais.
- O breakpoint graph não é um grafo bipartido.
- O número de componentes conexas do breakpoint graph é igual ao
número de componentes conexas do grafo de sobreposição de arcos.
- O número de componentes conexas do grafo de sobreposição de arcos é
igual ao número de intervalos enquadrados da permutação original.
- NDA
Autor(a): Marília Felippe Chiozo