Exercício

Lista 1
Teoria dos Grafos (Algoritmos em Grafos)
Prof. Alex Martins
25/04/2014
Entregar: 09/05/2014

1. Quantos digrafos diferentes existem com conjunto de vértices 0..V-1 e A arcos?
2. Exiba todos os grafos com conjunto de vértices 0..3. Para cada valor de E, quantos grafos diferentes existem com vértices 0..3 e E arestas?
3. Quantos grafos diferentes existem com conjunto de vértices 0..V-1 e E arestas?
5. Escreva uma função que verifique se um digrafo (dado por sua matriz de adjacência) é simétrico.
6. Escreva uma função que confira a consistência da representação de um grafo. Ao receber um grafo G, a função deve devolver 1 se a matriz G->adj é simétrica e tem diagonal nula, e se valor de G->A é consistente com o conteúdo de G->adj. Caso contrário, a função deve devolver 0.
7. Escreva uma função GRAPHdeg que devolva o grau de um vértice v num grafo G.
8. Escreva uma função DIGRAPHindeg que devolva o grau de entrada de um vértice v num digrafo G representado por sua matriz de adjacência.
9. Escreva uma função GRAPHremoveE que remova uma aresta v-w de um grafo G dado por sua matriz de adjacência. Se v-w não for aresta, a função nada faz.
10. Escreva uma função de DIGRAPHcopy que receba um digrafo representado por sua matriz de adjacência, crie uma cópia do digrafo, e devolva (o endereço d)a cópia.
11. Escreva uma função de DIGRAPHdestoy que destrua um digrafo representado por sua matriz de adjacência (ou seja, libere o espaço que o digrafo ocupa na memória).
12. Escreva uma função que receba um vetor de arestas e devolva a representação por matriz de adjacência do grafo definido por essas arestas.
13. Escreva uma função DIGRAPHarcs que armazene os arcos de um digrafo num vetor fornecido pelo usuário.
14. Escreva uma função GRAPHedges que armazene as arestas de um grafo num vetor fornecido pelo usuário.
Fonte: Algoritmos para Grafos – Paulo Feofiloff