Grafos

Lista 3
Teoria dos Grafos (Algoritmos em Grafos)

1. Escreva uma função que verifique se um digrafo é simétrico.

2. 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.

3. Escreva uma função GRAPHdeg que devolva o grau de um vértice v num grafo G.

4. Escreva uma função DIGRAPHindeg que devolva o grau de entrada de um vértice v num digrafo G.

5.Modifique DIGRAPHpath de modo que ela imprima os vértices que participam do caminho de s a t.

[As 5 primeiras devem ser feitas usando Matriz de adjacências e Vetor de lista de adjascências]

6. Modifique DIGRAPHpath de modo que DIGRAPHpath(G,s,t,d) verifique a existência de um caminho simples de s a t que tenha comprimento pelo menos d.

7. Escreva uma função que verifique se uma sequência seq[0..k] de vértices de um digrafo é um caminho simples. A função deve devolver -1 se a sequência não é um caminho, 0 se a sequência é um caminho simples, 1 se a sequência é um caminho não simples. Faça duas versões da função: uma supõe que o digrafo é dado por sua matriz de adjacência e outra supõe que o digrafo é dado por listas de adjacência.

8. Mostre as bibliotecas de matriz de adjacências e Lista de adjacências com suas devidas buscas de caminho implementadas.