Grafos

Fase 1)
Desenvolver um programa em C que gere uma matriz representativa da matriz de adjacência de um grafo ‘G’ . O grafo deve é orientado, com ‘v’ vértices. Seja como exemplo a matriz quadrada, CUSTO [v][v]
Os valores da matriz representam o custo associado a cada arco ( i , j ) com origem em [ i ] e destino em [ j ].
Observar que:
A) O grafo não possui laço em um mesmo vértice, isto é, CUSTO [i] [j] deverá ser zero se “ i ” igual a “ j “ if( i == j) CUSTO [i][j] = 0
B) O número de arcos ‘a’ deve ser limitado entre 20% e 50% do total de arcos possíveis, seja x% a porcentagem de arcos, então a = x% . (v2 –v)
O programa deve ajustar a matriz para atender às restrições A) e B).
Tarefa:
- Desenvolver o programa gerador da matriz de adjacência
- Apresentar uma imagem do grafo gerado pela matriz CUSTO
Fase 2)
A matriz de adjacência gerada na fase 1 representa as principais vias de acesso de uma cidade (ruas e avenidas) e locais de específicos a serem alcançados. Os vértices representam os locais de destino. Os arcos representam as vias, com sua direção de deslocamento e o peso (custo) para trafegar nessa via, registrado na matriz CUSTO. A origem do arco está na indicação da linha da matriz e o destino na indicação da coluna da matroz (padrão da matriz de Adjacência)
Exemplo:

1
2
3
4
1
0
12
5
0
2
2
0
0
3
3
0
2
0
1
4
0
2
3
0

Tarefa:
1) Tendo a matriz do grafo G, gerada na fase 1, deve-se executar o algoritmo de Djkstra e determinar para cada vértice o menor caminho aos demais vértices do grafo.

2) Com base nos resultados obtidos deve-se determinar os seguintes elementos do grafo:

a) O afastamento de cada vértice
b) O Raio do grafo
c) O centro exterior do grafo
d) O centro interior do grafo
e) O diâmetro do garfo
f) O vértice periférico
g) A mediana
h) O Anti-centro 3) Com base nas determinações acima informar em que vértices seriam instalados serviços do tipo:
- Delegacia de polícia