098-2005

MO640 - Questão para a prova oral
Número: 098
Enunciado:
Num grafo qualquer, uma clique é um conjunto de vértices mutuamente adjacentes. Sobre grafos de intervalo, podemos afirmar que:

1. Todo grafo de intervalo é um grafo cordal, i.e., para todo ciclo de comprimento maior que 3, existe uma aresta conectando dois vértices não consecutivos desse ciclo.
2. Todo grafo de intervalo corresponde a um modelo de interseção, no qual os vértices representam intervalos e as arestas conectam intervalos disjuntos.
3. Um grafo é grafo de intervalo se sua matriz de cliques por vértices respeitam a propriedade de 1s consecutivos por coluna.
4. Um grafo pode ser verificado como sendo um grafo de intervalo com, no mínimo, complexidade quadrática em relação ao tamanho do grafo.
5. NDA

Autor(a): Fernando Ferrari de Goes