Grafos

Nesse post você poderá praticar seus conhecimentos sobre a teoria dos grafos resolvendo exercícios sobre o assunto. Lembre-se, você poderá implementar esses grafos usando qualquer linguagem de programação que tenha suporte para isso.

Recomendamos que qualquer implementação seja feita em C ou então python. Em especial na linguagem python você pode usar o Igraph. Conheça mais sobre essa ferramenta aqui.

1)     Para o grafo da Figura:  

• Determine sua matriz de adjacência.
• Represente-o utilizando Lista de adjacências.
• Dê um exemplo prático do que este grafo poderia representar no mundo real.  

2)     Defina e dê exemplos visuais do que são:  

• Vértices e arestas.
• Grafos dirigidos e não dirigidos.    
• Considere o seguinte grafo:

• Qual o grau do nó C?
• Indique um caminho válido de A até E que possua custo igual a 24.    

4)     Considerando o código a seguir:    

typedef struct grafo{        
     int vertices;        
     int arestas;        
     VERTICE *adj; 
} GRAFO;   

Responda:

• Qual a função das variáveis int vértices e int arestas.
• O VERTICE *adj pode ser substituído por uma estrutura de lista ligada, escreva uma estrutura para substituir o vetor estático.

5) Escreva rotinas em C que, dados uma matriz de adjacência e dois nós de um grafo, calculem: 

• o número de caminhos de determinado comprimento existentes entre eles;
• o número total de caminhos existentes entre eles

6) Crie uma programa em C capaz de:

• instanciar um novo grafo
• adicionar um vértice ao grafo
• conectar dois vértices
• imprimir o grafo em forma de matriz de adjacências  

7) Crie um programa em C capaz de realizar as seguintes operações:

• instanciar um novo grafo
• adicionar N vértices ao grafo
• conectar dois vértices
• imprimir o grafo em forma de Lista de Adjacências (dinâmica)

Obs: estes exercícios ainda estão em construção, se você resolveu algum deles e gostaria de compartilhar com a nossa comunidade, entre em contato conosco.