Grafos

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.

Vinicius dos Santos

Apenas um apaixonado por Ciência da Computação e forma com que ela pode transformar vidas!

Deixe uma resposta