Exercícios de participação do dia 28/11
1. Considere a representação de grafos usando o tipo abstrato de dados matriz de adjacências. Considere as seguintes declarações:
# define numeroVertices ...
struct Gmat {
int matriz[numVertices,numVertices];
int numeroVertices;
}
struct Gmat matriz Adjacencias
Suponha que não se saiba nada a respeito de G. Faça um algoritmo que determina se G é candidato ou não a ser um grafo direcionado, usando como base Gmat. O algoritmo deve otimizar a varredura de Gmat.
2. Dado o grafo G do quadro branco:
a) Represente G usando lista de adjacências;
b) Armazene o grau de cada vértice de G;
c) Faça um algoritmo que verifique se G é um grafo completo.
d) Determine o tempo de descoberta e o tempo de término de cada vértice, de acordo com a busca em profundidade e começando pelo vértice 1.
e) Faça um algoritmo que determine se G é um grafo cíclico. Se sim, indique quando o ciclo é descoberto pela primeira vez começando pelo vértice 1.