MO640 - Questão para a prova oral
Número: 054
Enunciado:
Segundo o paper de Bergeron (2002), qual é a
matriz de bits correspondentes ao grafo de sobreposição da
permutação (-2, 4, 3, -1) (ignorando o s)?
Lembre-se que esta matriz nada mais é do que a matriz de
adjacências do grafo de sobreposição de arcos, com a linha
p indicando a coloração (1 para negro, 0 para branco).
| A. |
| |
v0 |
v1 |
v2 |
v3 |
v4 |
| v0 |
0 |
0 |
1 |
0 |
1 |
| v1 |
0 |
0 |
1 |
1 |
0 |
| v2 |
1 |
1 |
0 |
1 |
0 |
| v3 |
0 |
1 |
1 |
0 |
1 |
| v4 |
1 |
0 |
0 |
1 |
0 |
| p |
0 |
0 |
1 |
1 |
0 |
|
B. |
| |
v0 |
v1 |
v2 |
v3 |
v4 |
| v0 |
0 |
0 |
0 |
0 |
1 |
| v1 |
0 |
1 |
1 |
0 |
1 |
| v2 |
1 |
1 |
0 |
1 |
1 |
| v3 |
0 |
0 |
1 |
1 |
1 |
| v4 |
0 |
1 |
0 |
1 |
0 |
| p |
0 |
1 |
0 |
1 |
1 |
|
C. |
| |
v0 |
v1 |
v2 |
v3 |
v4 |
| v0 |
0 |
1 |
0 |
0 |
1 |
| v1 |
0 |
0 |
1 |
1 |
1 |
| v2 |
0 |
1 |
0 |
1 |
1 |
| v3 |
1 |
0 |
1 |
0 |
1 |
| v4 |
1 |
0 |
1 |
0 |
0 |
| p |
1 |
0 |
1 |
0 |
1 |
|
D. |
| |
v0 |
v1 |
v2 |
v3 |
v4 |
| v0 |
0 |
0 |
0 |
0 |
1 |
| v1 |
0 |
0 |
1 |
0 |
1 |
| v2 |
0 |
1 |
0 |
1 |
1 |
| v3 |
0 |
0 |
1 |
0 |
1 |
| v4 |
1 |
1 |
1 |
1 |
0 |
| p |
1 |
0 |
1 |
0 |
0 |
|
E. | NDA
|
Autor(a): Matthias Gallé