Lista de Grafos

Lista 1
Teoria dos Grafos (Algoritmos em Grafos)
Aluno: Francisco Eduardo Rocha Júnior
Prof. Alex Martins
22/02/2013

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?

Fazer os exercícios para grafos e dígrafos.
5. Escreva uma função que verifique se um digrafo (dado por sua matriz de adjacência) é simétrico.

int symmetry(Digraph G){ Vertex v, w; for(v = 0; v < G->V; v++) for(w = 0; w < G->V; w++) if(v != w && G->adj[v][w] != G->adj[w][v]) return 0; return 1;
}

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.

int DIGRAPHcons (Digraph G) { int cons = 1; 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 cons = 0; if (G->adj[v][w] == 1) cont++; } if (G->A != cont) return cons = 0;

for (v = 0; v < G->V; v++) if (G->adj[v][v] != 0) return cons = 0;

return cons;
}

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

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;
}

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.

int DIGRAPHindeg (Digraph G, Vertex v) { int indeg = 0; Vertex w; for (w