Exercícios resolvidos de grafos

Prévia do material em texto

Lista 3
Teoria dos Grafos (Algoritmos em Grafos)
Prof. Alex Martins
29/01/2015
Entregar: 05/02/2015
1. Escreva uma função que verifique se um digrafo é simétrico.
m.a.
int DIGRAPHsimetrico (Digraph G) {
	Vertex v, w;
 for (v = 0; v < G->V; v++)
		for (w = 0; w < G->V; w++)
			if (G->adj[v][w] != G->adj[w][v]){
 return 0;
 }
 return 1;
}
v.l
int Esimetrico(Graph G){
 Vertex v, simetrico = 0;
 link p, q;
 //Confere a simetria da lista de adjacência
 for (v = 0; v < G->V; v++){
 for (p = G->adj[v]; p != NULL; p = p->next)
 simetrico = 0;
 for (q = G->adj[p->w]; q != NULL; q = q->next) 
 {
 if (q->w == v) {
 simetrico = 1;
 }
 }
 if (simetrico == 0)
 return (0);
 }
return simetrico;
}
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.
m.a.
int DIGRAPHconsistente (Digraph G) {
 int cont = 0;
 Vertex v, w;
	for (v = 0; v < G->V; v++)
		for (w = 0; w < G->V; w++){
			if (G->adj[v][w] != G->adj[w][v])
				return 0;
 if (G->adj[v][w] == 1)
 cont++;
 }
 
 for (v = 0; v < G->V; v++)
 if (G->adj[v][v] != 0)
 return 0;
 if (G->A != cont)
 return 0;
 
return 1;
 
}
v.l.
int consistence(Graph G){
 Vertex v, z, simetrico = 0;
 link p, q;
 int cont;
 //Confere a simetria da lista de adjacência
 for (v = 0; v < G->V; v++){
 for (p = G->adj[v]; p != NULL; p = p->next)
 simetrico = 0;
 for (q = G->adj[p->w]; q != NULL; q = q->next) 
 {
 if (q->w == v)
 simetrico = 1;
 }
 if (simetrico == 0)
 return (0);
 }
 //Confere a inexistencia de laços
 for (v = 0; v < G->V; v++){
 for (p = G->adj[v]; p != NULL; p = p->next)
 if (p->w == v)
 return(0);
 }
 
 //Confere a quantidade de arcos com o valor de G->A
 for (v = 0; v < G->V; v++){
 for (p = G->adj[v]; p != NULL; p = p->next)
 cont++;
 if (cont != G->A)
 return 0;
 } 
return(1); //e consistente
}
3. Escreva uma função GRAPHdeg que devolva o grau de um vértice v num grafo G.
m.a.
int GRAPHdeg (Digraph G, Vertex v) {
	int deg = 0;
	Vertex w;
	for (w = 0; w < G->V; w++)
		if (G->adj[v][w] == 1)
			deg++;
	return deg;
}
/*Grau de entrada*/
void GRAPHdeg(Digraph G, Vertex v)
{
 // Vertex v;
 int deg = 0;
 link p;
 for (p = G->adj[v]; p != NULL; p = p->next)
 deg++;
 printf("Grau de entrada do grafo: %d", deg);
}
4. Escreva uma função DIGRAPHindeg que devolva o grau de entrada de um
 vértice v num digrafo G.
m.a.
int DIGRAPHindeg (Digraph G, Vertex v) {
	int indeg = 0;
	Vertex w;
	for (w = 0; w < G->V; w++)
		if (G->adj[w][v] == 1)
			indeg++;
	return indeg;
}
v.l.
void DIGRAPHindeg(Digraph G, Vertex z)
{
 Vertex v;
 int indeg = 0;
 link p;
 for (v = 0; v < G->V; v++){
 for (p = G->adj[v]; p != NULL; p = p->next)
 if (p->w == z)
 indeg++;
 printf("Grau de entrada do digrafo: %d", indeg);
 }
}
5.Modifique DIGRAPHpath de modo que ela imprima os vértices que
 participam do caminho de s a t.
 imprimeCaminhoAoContrário( Digraph G, Vertex s, Vertex t) {
 Vertex w;
 for (w = t; w != s; w = parnt[w])
 printf( "%d-", w);
 printf( "%d\n", s);
 }
 imprimeCaminho( Digraph G, Vertex s, Vertex t) {
 Vertex w, pilha[maxV];
 int topo = 0;
 for (w = t; w != s; w = parent[w]) 
 pilha[topo++] = w;
 printf( "%d", s);
 while (topo > 0) 
 printf( "-%d", pilha[--topo]); 
 printf( "\n");
 }
[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.