Introduo Teoria dos Grafos

  • Published on
    18-Dec-2014

  • View
    6.075

  • Download
    5

DESCRIPTION

 

Transcript

  • 1. Bianca de Almeida Dantas
  • 2. Introduo Terminologia Exemplos de Grafos Digrafos Percursos em Grafos Representao Computacional Problemas em Grafos Concluses Bibliografia
  • 3. Ramo da matemtica que se utiliza de modelos (os grafos) para estudar as relaes entre os objetos de um conjunto.
  • 4. Figura 1 Grafo com 4 vrtices e 6 arestas.
  • 5. Diversos problemas podem ser representados por grafos: Trajetos entre cidades Roteamento de veculos Mapa de pginas de um site Redes de computadores Representao de mquinas de estados finitos A obteno de estruturas de dados e de algoritmos eficientes para manipulao de grafos uma rea de grande interesse da cincia da computao.
  • 6. Um grafo um par ordenado (V, A), onde V um conjunto qualquer e A um subconjunto de V(2) , o conjunto de todos os pares no- ordenados de V. Chamamos os elementos de V de vrtices e os elementos de A de arestas. Considere dois vrtices u e v e uma aresta que os conecta, denotada por uv ou vu. Dizemos que a aresta uv incide em u e em v ou, ainda, que u e v so pontas da aresta uv.
  • 7. Quando dois vrtices so pontas de uma mesma aresta, eles so ditos vizinhos ou adjacentes. Em algumas situaes, interessante dar nome a um grafo, por exemplo, G. Neste caso, o conjunto de vrtices e de arestas so denotados por V(G) e A(G), respectivamente. O nmero de vrtices, |V(G)|, de G denotado por n e o nmero de arestas, |A(G)|, denotado por m.
  • 8. Vrtices: t, u, v, w, x, y, zArestas: xu, uv, vw, wx, xy, yzn=7m=6
  • 9. O grau de um vrtice definido como o nmero de arestas incidentes em tal vrtice. 2 0 2 3 1 2 2
  • 10. Um grafo regular aquele em que todos os vrtices possuem o mesmo grau. Um grafo regular com vrtices de grau k chamado de k-regular.0-regular 1-regular 2-regular 3-regular
  • 11. Um grafo completo G aquele que possui arestas conectando todos os pares de vrtices, ou seja, G(V, V(2)). Usualmente, so nomeados usando a letra K. Tambm um grafo 5-regular Grafo completo com 6 vrtices (K6)
  • 12. O complemento de um grafo (V, A) definido como (V, V(2) A). u z u z u z y v yv y v w x w x w x Grafo Grafo completo Complemento
  • 13. Um caminho entre dois vrtices v1 e v2 de um grafo a sequncia de arestas do trajeto saindo de v1 em direo a v2. Os vrtices v1 e v2 so ditos extremos do caminho. O comprimento de um caminho o seu nmero de arestas. Um caminho que comea e termina no mesmo vrtice chamado de ciclo ou circuito. Um ciclo de comprimento 1 chamado de lao.
  • 14. u tv x z y w Qual o caminho de v a y?
  • 15. u tv x z y w Alternativa 1 Comprimento: 3
  • 16. u tv x z y w Alternativa 2 Comprimento: 3
  • 17. Ciclo a partir do vrtice u u t v x z y w
  • 18. u tv x z y w Um lao no vrtice t
  • 19. Em um grafo simples no existem laos e h no mximo uma aresta entre quaisquer par de vrtices, ou seja, no existem arestas paralelas. Um grafo G(V, A) conexo se existe um caminho entre todos os pares de vrtices de V.
  • 20. Grafos podem ter pesos associados a suas arestas, representado por um nmero rotulando cada aresta. Neste caso, o comprimento do caminho entre dois vrtices (ou peso do caminho) corresponde soma dos pesos das arestas que compem o caminho.
  • 21. Dizemos que o caminho vermelho um caminhomnimo entre v e y, pois tem o menor peso entre os caminhos possveis. u t 2 4 v x z 3 7 y 6 1 w Caminhos entre v e y? Alternativa 1 (verde):Peso = 13 Alternativa 2 (vermelho):Peso = 11
  • 22. O grafo dos estados do Brasil definido assim: cada vrtice um dos estados da Repblica Federativa do Brasil; dois estados so adjacentes se tm uma fronteira comum.
  • 23. Grafo que representa as adjacncias entre os estados do Brasil
  • 24. Tipos especiais de grafos nos quais todas as arestas so direcionadas. Caminhos em digrafos devem levar em considerao a direo das arestas. Dois tipos de graus de vrtices: Grau de entrada: nmero de arestas que chegam no vrtice; Grau de sada: nmeros de arestas que saem do vrtice.
  • 25. u tv x z y w Caminho de v at y? E de y at v?
  • 26. Quais os graus de entrada (E) e sada (S)? E: 0 E: 2 S: 0 u t S: 0 v x z yE: 0 E: 1 E: 1S: 2 w S: 2 E: 1 S: 0 E: 1 S: 1 S: 1 nica alternativa de v at y! De y at v no existe caminho.
  • 27. Um digrafo D(V, A) dito fortemente conexo se, para todos os pares de vrtices (u, v) existe caminho de u para v e de v para u. Um digrafo fracamente conexo se sua verso no-direcionada for conexa.
  • 28. Digrafo fortemente conexo uv x z y w Digrafo fracamente conexo
  • 29. Existem duas formas de percorrer todos os vrtices de um grafo, geralmente chamadas de buscas: Busca em Largura ou BFS (Breadth-First Search); Busca em Profundidades ou DFS (Depth-First Search).
  • 30. Nesse percurso, partimos de um vrtice inicial e percorremos todos os seus vizinhos, um a um, e ento percorremos os vizinhos de cada um de seus vizinhos, na ordem em que foram visitados no passo anterior.
  • 31. 1
  • 32. 12
  • 33. 12 3
  • 34. 1 2 34
  • 35. 1 2 34 5
  • 36. 1 2 34 5 6
  • 37. 1 2 34 5 6 7
  • 38. 1 2 34 5 6 7
  • 39. 1 2 34 5 6 7
  • 40. 1 2 34 5 6 7
  • 41. 1 2 34 5 6 7 Grafos com essa estrutura so chamados de rvores.
  • 42. Partindo de um vrtice inicial, esse algoritmo visita os vrtices um a um at o filho mais profundo que pode ser alcanado e, aps descer na hierarquia, passa para o prximo filho.
  • 43. 1
  • 44. 12
  • 45. 1 23
  • 46. 1 23
  • 47. 1 23 4
  • 48. 1 23 4
  • 49. 1 23 4
  • 50. 1 2 53 4
  • 51. 1 2 53 4 6
  • 52. 1 2 53 4 6
  • 53. 1 2 53 4 6 7
  • 54. 1 2 53 4 6 7
  • 55. 1 2 53 4 6 7
  • 56. 1 2 53 4 6 7
  • 57. Existem diversas estruturas que podem ser utilizadas para armazenar as informaes de um grafo ou digrafo. Pode-se citar: Matriz de adjacncias; Lista de adjacncias; Lista de arestas; Matriz de incidncias; Listas de vrtices e arestas
  • 58. A matriz de adjacncias para um grafo (digrafo) G (V, A) uma matriz M de dimenso |V|x|V| na qual o elemento Mi,j ser igual a 1 se existe uma aresta de i para j ou 0, caso contrrio.
  • 59. v6v1 v3 v5 v4 v2 v1 v2 v3 v4 v5 v6 v1 0 1 0 0 0 1 v2 0 0 1 0 0 0 v3 0 0 0 1 0 1 v4 0 0 0 0 1 0 v5 0 0 0 0 0 0 v6 0 0 0 0 0 0 Matriz de adjacncias para o digrafo
  • 60. v6 v1 v3 v5 v4 v2 v1 v2 v3 v4 v5 v6 v1 0 1 0 0 0 1 Matriz v2 1 0 1 0 0 0simtrica! v3 0 1 0 1 0 1 v4 0 0 1 0 1 0 v5 0 0 0 1 0 0 v6 1 0 1 0 0 0 Matriz de adjacncia para o grafo
  • 61. Uma lista de adjacncias para um grafo (digrafo) G (V, A) armazena para cada vrtice u de V uma lista de todos os vrtices v para os quais existe uma aresta uv.
  • 62. v6v1 v3 v5 v4 v2 v1 v2 v6 v2 v3 v3 v4 v6 v4 v5 v5 v6 Lista de adjacncias para o digrafo
  • 63. A representao de um grafo (digrafo) G(V,A) por lista de arestas utiliza dois vetores com |A| elementos para armazenar os extremos das arestas pertencentes a A.
  • 64. v6 v1 v3 v5 v4 v2Vetor1 v1 v1 v2 v3 v3 v4Vetor2 v2 v6 v3 v4 v6 v5 Lista de arestas para o digrafo
  • 65. Uma matriz de incidncias para um digrafo G(V,A) uma matriz M de dimenso |V|x|A| em que cada elemento segue a equao: 1, se v i for o vrtice inicial de a j mij 1, se v i for o vrtice final de a j 0, caso contrrio No caso de grafos no-direcionais, temos que mij ser 1 se vi for extremo de aj ou 0 caso contrrio.
  • 66. v6 a5 a6v1 v3 v5 v4 a1 a2 a3 a4 v2 a1 a2 a3 a4 a5 a6 v1 1 0 0 0 1 0 v2 -1 1 0 0 0 0 v3 0 -1 1 0 0 1 v4 0 0 -1 1 0 0 v5 0 0 0 -1 0 0 v6 0 0 0 0 -1 -1 Matriz de incidncias para o digrafo
  • 67. As listas de vrtices e de arestas so a forma mais simples de representao de um grafo (digrafo) G(V,A). So mantidas duas listas uma com todos os vrtices de G e outra com todas as arestas e seus extremos.
  • 68. v6 a5 a6 v1 v3 v5 v4 a1 a2 a3 a4 v2Lista de Vrtices Lista de Arestas vi vj v1 a1 v1 v2 v2 a2 v2 v3 v3 a3 v3 v4 v4 a4 v4 v5 v5 a5 v1 v6 v6 a6 v3 v6 Listas de vrtices e de arestas para o digrafo
  • 69. Fecho transitivo Problema do caminho mnimo Caixeiro viajante Carteiro chins Colorao de vrtices
  • 70. O fecho transitivo Dt de um digrafo D obtido adicionando uma aresta dirigida entre todos os pares de vrtices vi e vj entre os quais exista um caminho que saia de vi em direo a vj. Digrafo Dt de D
  • 71. Ou seja, o fecho transitivo representa a insero de uma nova aresta entre os vrtices conectados indiretamente por um caminho. Diversos algoritmos foram propostos para soluo. Muitas solues se baseiam na matriz de adjacncias.
  • 72. 1 2 3 4 51 2 1 0 0 1 0 0 2 0 0 1 1 0 3 4 3 0 0 0 0 1 4 0 0 0 0 1 5 5 0 0 0 0 0
  • 73. 1 2 3 4 51 2 1 0 0 1 0 1 2 0 0 1 1 1 3 4 3 0 0 0 0 1 4 0 0 0 0 1 5 5 0 0 0 0 0
  • 74. Complexidade (n3) Baseia-se na premissa de que, se existe uma aresta de vi para vk e uma aresta de vk para vj, ento, deve existir uma aresta de vi para vj. Sua estrutura permite fcil paralelizao.
  • 75. AlgoritmoEntrada: M matriz de adjacnciasSada: Mt matriz de adjacncias dofechoinicio n