1. O que é um grafo ? Defina um grafo orientado. Defina um grafo não-orientado.
   
   
2. Representação de grafos.
   1. Explique porque a lista de arestas de um grafo não define completamente o grafo.
   2. Defina a Matriz de Ajacência de um grafo. Desenhe um grafo não-orientado de 5 vértices e apresente a matriz de adjacência correspondente. Faça o mesmo para um grafo orientado.
   3. Defina Lista de Adjacência de um vértice. usando os grafos desenhados no item anterior.
   4. O que é o grau de um vértice em um grafo. Exemplifique nos grafos do item b).
   
   
3. Desenhe todos os grafos não-orientados de 5 vértices onde todos os vértices tem grau menor ou igual a 2 (ou seja, têm duas ou menos arestas incidentes).
   
   
4. O que é um caminho em um grafo orientado ? Defina. E em um grafo não-orientado. Defina ciclos (ou circuitos) nos dois tipos de grafos.
   
   
5. Considere o problema de se encontrar todos os vértices que cuja distância do vértice 1 é exatamente K (arestas). Ou seja a distância do caminho mais curto, em número de arestas, do vértice até um tal vértice é K.
   
   
   Teorema 1  (K): Sabe-se encontrar todos os vértices de G=(V,E) que cuja distância do vértice 1 é exatamente K.
   
   
   
   1. Prove este teorema por indução matemática.
   2. Descreva o algoritmo resultante dessa prova. Como este algoritmo é conhecido na literatura ?
   3. Mostre como este algoritmo obtém todos os vértices que estão a distância 2 (K=2) no grafo: V={1,2,3,4,5,6}, E={ (1,2), (1,3), (3,5), (3,6), (3,4), (2,4), (4,5), (4,6) }
   
   
6. Considere o grafo do item c) da questão 5.
   1. Defina um ciclo Euleriano.
   2. Este grafo possui ciclo Euleriano ? Por que ?
   3. No caso afirmativo, apresente um ciclo Euleriano.
   
   
7. O algoritmo conhecido como Busca em Profundidade tem que objetivo quando aplicado a um grafo ? Qual outro algoritmo também cumpre esse objetivo. Aplique o algoritmo de Busca em Profundidade, utilizando a ordem lexicográfica para desempates, no grafo do item c) da questão 5 começando pelo vértice 1.
   
   
8. Defina caminho-mais-curto entre um par de vértices em um grafo orientado.
   
   
9. Seja um grafo orientado G=(V,A) e o problema de encontrar o caminho mais curto entre um vértice
   
   
   1. Escreva o algoritmo de Ford-Bellman para encontrar o caminho-mais-curto de s a todos os demais em V. Explique por este algoritmo pode ser obtido através da prova por indução matemática do teorema abaixo.
      
      
      Teorema 2  (K): Sabe-se obter a distância mínima de s a todos os vértices de V onde os caminhos podem ter no máximo K arcos.
      
      
      
   2. Escreva o algoritmo de Dijkstra para encontrar o caminho-mais-curto de s a todos os demais em V. Explique por este algoritmo pode ser obtido através da prova por indução matemática do teorema abaixo.
      
      
      Teorema 3  (K): Sabe-se determinar o K-ésimo vértice mais próximo a s e sua respectiva distância mínima de s.
      
      
      
   3. Aplique os algoritmos acima no grafo G=(V,A) abaixo fazendo s=1. V={1,2,3,4,5,6}, A={ (1,2), (1,3), (3,5), (3,6), (3,4), (2,4), (4,5), (4,6) }, com distâncias d_1,2= 1, d_1,3=2, d_3,5=4, d_3,6=2, d_3,4=2, d_2,4=2, d_4,5=2, d_4,6=3 .
   
   
10. Considere o problema de encontrar o caminho mais curto entre todos os pares de vértices de um grafo.
    
    
    1. Explique os algoritmos que podem ser obtidos pela prova por indução matemática dos seguintes teoremas.
       
       
       Teorema 4  (K): Sabe-se obter a distância mínima entre todos os pares de vértices em V onde os caminhos podem ter no máximo K arcos.
       
       
       
       Teorema 5  (K): Sabe-se obter a distância mínima entre todos os pares de vértices em V onde os caminhos podem ter como vértices intermediários os vértices que estão no conjunto I={1, 2, ..., K}.
       
       
       O algoritmo resultande da prova deste segundo é frequentemente denominado Flyd-Warshall.
       
       
    2. Aplique os algoritmos acima no grafo G=(V,A) abaixo onde os arcos abaixo ocorrem com as duas orientações possíveis.
       
       V={1,2,3,4,5,6}, A={ (1,2), (1,3), (3,5), (3,6), (3,4), (2,4), (4,5), (4,6) }, com distâncias d_1,2= 1, d_1,3=2, d_3,5=4, d_3,6=2, d_3,4=2, d_2,4=2, d_4,5=2, d_4,6=3 .
    
    
11. Defina o Fecho Transitivo de um grafo G=(V,E). Apresente algoritmos para obter o Fecho Transitivo dos grafos apresentados nesta lista.
    
    
12. Defina uma árvore em um grafo. O que é uma floresta ? O que é uma árvore geradora de um grafo ? Que algoritmo pode ser utilizado para encontrar uma árvore geradora qualquer em um grafo. Aplique este algoritmo no grafo do item c) da questão 5. O que seria uma árvore geradora de peso mínimo ?
    
    
13. Seja um grafo conexo G=(V,E), não-orientado, e w_e, para e Î E os pesos, onde V={1, 2, ..., n } associados às arestas de G. Seja o problema de encontrar a árvore geradora de peso máximo de G.
    
    
    1. Que algoritmo pode ser obtido através da prova dos teoremas abaixo por indução matemática ? Apresente o algoritmo e explique.
       
       
       Teorema 6  (K): Sabe-se encontrar uma sub-árvore da árvore geradora máxima de G=(V,E), que contém o vértice 1 (1 Î V), que possui K vértice e possui peso máximo.
       
       
       
    2. Que algoritmo pode ser obtido através da prova do teorema abaixo por indução matemática ? Apresente o algoritmo e explique.
       
       
       Teorema 7  (K): Sabe-se encontrar a floresta F=(V,E^K) de peso máximo de G=(V,E) que possui K arestas, isto é |E^K|=K.
       
       
       
    3. Aplique os algoritmos acima no grafo G=(V,E). V={1,2,3,4,5,6}, E={ (1,2), (1,3), (3,5), (3,6), (3,4), (2,4), (4,5), (4,6) }, com pesos w_1,2= 1, w_1,3=2, w_3,5=4, w_3,6=2, w_3,4=2, w_2,4=2, w_4,5=2, w_4,6=3 .
    
    
14. Emparelhamentos(matching) e Fluxo em Redes
    
    
    1. Defina um grafo bi-partido.
    2. O que é um emparelhamento. O que seria um emparelhamento máximo em um grafo G=(V,E) não orientado.
    3. Dado um grafo orientado G=(V,E) com capacidade u_e associadas aos arcos e Î E, e vértices de origem s e destino t, defina um fluxo viável de s a t na rede definida por G.
    4. O que seria um fluxo máximo ?
    5. Que algoritmo pode ser usado para obter o emparelhamento máximo de um grafo bi-partido ?
    6. Que algoritmo pode ser usado para obter o fluxo máximo de s a t em um grafo orientado G=(V,E) com capacidade u_e associadas aos arcos ?

This document was translated from L^AT_EX by H^EV^EA.