Baixe o app para aproveitar ainda mais
Prévia do material em texto
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 1 1- Introdução a Grafos O objetivo deste estudo é mostrar o que representam os grafos observando o aspecto matemático, bem como sua importância para as diversas áreas, mas em destaque a de computação. Com este estudo o aluno poderá saber a história e origem dos grafos, bem como a aplicabilidade na computação nos dias atuais. 1.1- A História dos Grafos De forma bem simples pode-se dizer que os grafos possuem uma história muito rica que vem desde um trabalho de longa data conforme cita Wikipédia (2014, p. 01) como segue: O artigo de Leonhard Euler, publicado em 1736, sobre o problema das sete pontes de Königsberg, é considerado o primeiro resultado da teoria dos grafos.1 É também considerado um dos primeiros resultados topológicos na geometria; isto é, não dependente de quaisquer medidas. Isso ilustra a profunda conexão entre a teoria dos grafos e topologia. Mas quem foi Leonhard Euler? Conforme Wikipédia (2014, p. 01) ele foi um grande matemático que deu os primeiros passos nessa teoria dos grafos, como segue: Euler fez importantes descobertas em campos variados em cálculo e grafos. Também fez muitas contribuições para a matemática moderna no campo da terminologia e notação, em especial para a análise matemática, como a noção de uma função matemática. Além disso tornou-se célebre por seus trabalhos em mecânica, óptica, e astronomia. Euler é considerado um dos mais proeminentes matemáticos do século XVIII. Uma declaração atribuída a Pierre-Simon Laplace manifestada sobre Euler na sua influência sobre a matemática: "Leiam Euler, leiam Euler, ele é o mestre de todos nós. Euler foi um dos mais prolíficos matemáticos, calcula-se que toda a sua obra reunida teria entre 60 e 80 volumes. Dentre muitos trabalhos desenvolvidos por Euler, obviamente destaca-se a teoria dos grafos, foco deste estudo, através do famoso problema conhecido como sete pontes de Königsberg , como segue, conforme Wikipédia (2014, p 01): Em 1736, Euler resolveu o problema conhecido como sete pontes de Königsberg. A cidade de Königsberg, Prússia, foi construída no rio Pregel, e incluiu duas grandes ilhas que estavam conectadas entre si e ao continente por sete pontes. O problema era o de decidir se é possível seguir um caminho que atravessa cada uma das pontes exatamente uma vez e retornar ao ponto de partida. Esta solução é considerada como sendo Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 2 o primeiro teorema da teoria dos grafos, especificamente da teoria gráfica planar. Euler também descobriu a fórmula V - E + F = 2 relacionando o número de vértices, arestas e faces de um poliedro convexo e, portanto, de um grafo planar. A constante nesta fórmula é agora conhecida como a característica de Euler para o gráfico (ou objeto de cálculo), e está relacionada ao gênero do objeto. O estudo e generalização desta fórmula foram, especificamente através de Augustin-Louis Cauchy, Simon Antoine Jean L'Huillier, estando na origem da topologia. Na sequência uma figura do famoso problema que trata do mapa de Könogsber na época de Euler mostrando o layout das sete pontes, destacando o rio Pregel e suas pontas, que será abordado posteriormente. Figura 01 – Problema das Sete Pontes de Euler Fonte: Wikipédia (2014, p. 02) Como visto a fundamentação dos grafos esta na sua constituição matemática, possuindo diversas aplicabilidades que serão vistas futuramente neste estudo. Portanto neste estudo será usada a visão Euleriana quanto aos grafos, sabendo-se que possui varias outras como Hamiltonianos e outras escolas em relação ao assunto. 1.1.1 Porque das Sete Pontes de Euler? Conforme Sá e Silva (2012, p. 09), Para iniciar esse resgate histórico, lembremos que numa cidade chamada Konisberg (atual Kaliningrado, na Rússia) havia sete pontes cruzando o Rio Pregel, conforme o mapa apresentado na Figura 1. Muitos moradores dessa cidade se questionavam sobre a existência de um caminho no qual Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 3 alguém pudesse sair de algum ponto da cidade, percorrer as sete pontes uma única vez e voltar ao ponto inicial. Essa dúvida ficou no ar até que Leonard Euler, em 1736, resolveu esse problema inaugurando um novo ramo da matemática: a Teoria dos Grafos. Para solucionar o problema, Euler criou um desenho que esboçasse a cidade. Para tanto, ele representou as pontes por linhas e as porções de terra (ilhas e margens) por pontos, conforme apresentado na Figura 2. Esse foi o primeiro Grafo da história. Figura 1. Mapa com as Pontes de Konisberg. Figura 2. Grafo que representa a cidade de Konisberg. Sá e Silva (2012, p. 09) citam que, Após chamar cada linha de aresta e cada ponto de vértice, Euler passou a analisar o número de arestas que incide em cada vértice. Esse número é chamado de Grau de um vértice e é escrito como G(v), onde v é o vértice analisado. O que se procurava, então, era o que hoje chamamos de caminho euleriano fechado (no qual os pontos inicial e final coincidem). Determinamos um caminho desse tipo por meio do Teorema que diz que um grafo conexo admite caminho euleriano fechado se, e somente se, todos os vértices têm grau par. Vale lembrar que, analogamente, há os caminhos eulerianos abertos, nos quais é possível realizar um trajeto em que os pontos inicial e final são distintos, como no Grafo abaixo. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 4 Figura 3. Grafo com caminho euleriano aberto. Para que um caminho seja euleriano aberto, o grafo deve ter exatamente dois vértices de grau ímpar, que serão a partida e a chegada do caminho. No grafo da figura 3, temos que esses pontos são os vértices A e E. Voltando ao problema das sete pontes de Konisberg, verificamos no grafo da figura 1 que G(A) = 5, G(B) = 3, G(C) = 3 e G(D) = 3. Dessa forma, concluímos que há mais de dois vértices com grau ímpar e, assim, não é possível estabelecer nenhum tipo de caminho por todas as pontes de Konisberg. (Grifo Nosso). A pergunta eraa seguinte: Haveria possibilidade de transitar pela cidade de Konisberg, iniciando e terminando no mesmo lugar, passando cada ponte exatamente uma vez? A representação de Euler foi seguinte conforme figura abaixo: Figura 02 – Representação Gráfica das sete pontes de Euler Fonte: Fontes (2009, p. 04) Conforme Fonte (2009, p. 04), “Euler representou as relações graficamente. A cada margem e ilha associou um nó e a cada ponte um arco.” Como visto nesta explanação foi resolvido um problema onde citam que muitos moradores dessa cidade se questionavam sobre a existência de um caminho no qual alguém Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 5 pudesse sair de algum ponto da cidade, percorrer as sete pontes uma única vez e voltar ao ponto inicial. Conforme citado acima a dúvida ficou no ar até que Leonard Euler, em 1736, resolveu esse problema inaugurando um novo ramo da matemática: a Teoria dos Grafos. Por isto se tem hoje os Grafos Eulerianos, em homenagem a este grande matemático que desvendou este enigma conhecido como as Sete Pontes de Konisberg, mas sabe-se que existem os hamiltonianos, dentre outros. 1.2 O que são grafos? Vários conceitos podem ser dados quanto aos grafos, mas segundo a Wikipédia (2014, p. 05) pode-se dizer que grafos são: A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, G(V,A), onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, chamado arestas. Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo direcionado, grafo orientado ou digrafo. Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial. Outro conceito pode ser da seguinte forma segundo Ribeiro (2012, p.03), como segue: Um grafo é uma representação abstrata de um conjunto de objetos e das relações existentes entre eles. É definido por um conjunto de nós ou vértices, e pelas ligações ou arestas, que ligam pares de nós. Uma grande variedade de estruturas do mundo real podem ser representadas abstratamente através de grafos. A figura seguinte ilustra um grafo com 5 nós. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 6 Um grafo é descrito por um par (V,E), onde V é o conjunto de vértices e E o conjunto das arestas que ligam pares de vértices. Um grafo pode ser dirigido ou direcionado, se as arestas tiverem uma direção, ou não dirigido, se as arestas não tiverem direção. A figura seguinte ilustra um grafo dirigido. Se as arestas tiverem associado um peso ou custo, o grafo passa a chamar- se de grafo pesado. A figura seguinte ilustra um grafo pesado não dirigido. Os nós podem ser de diferente tipos, representados por cores ou etiquetas. Nesse caso, o grafo diz-se colorido. A figura seguinte ilustra um grafo colorido não dirigido. Quando apenas é admitida no máximo uma aresta entre dois nós, diz-se que o grafo é simples. Como visto então os grafos são representações de objetos das mais variadas formas que se relacionam entre si formando uma verdadeira “rede”, possuindo vários tipos neste contexto que serão vistos posteriormente. A seguir algumas aplicabilidades iniciais dos grafos. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 7 1.3 Algumas das aplicabilidades dos grafos Conforme Ribeiro (2012, p.03), os grafos podem ter várias aplicabilidades como segue: Um vasto leque de sistemas naturais ou artificiais pode ser representado através de grafos. Por exemplo, no campo da biologia podemos ter uma cadeia alimentar, com os animais a serem os nós, e as relações de predador-presa entre eles a serem as arestas. Podemos ter também outras estruturas biológicas, tais como uma rede neuronal (ligações entre neurónios) ou uma rede interação entre proteínas. Na sociologia podemos ter uma rede social de amigos com ligações representando amizades. No software podemos ter uma rede representando heranças entre objetos. Num patamar de existência mais física podemos ter grafos representando uma rede de auto-estradas ligando cidades, uma rede elétrica ligando casas, uma rede computadores, ou uma rede de páginas da internet com hiperligações entre si. Muitos mais exemplos poderiam ser dados, mas o essencial é perceber que os grafos são uma representação abstrata muito poderosa e flexível. (Grifo nosso). Outras aplicabilidades observando seus vértices e suas arestas conforme Fontes (2009, p. 7) seriam: Motores de busca de páginas Web: - Vértices são as páginas HTML e as arestas (direcionadas) são links ligando as páginas - Identificar proximidade entre duas páginas quaisquer - Identificar se uma página é acessível a partir de outra - Identificar o número de links para uma página (grau do vértice) Roteamento de Carga: - Vértices são pontos de entrega e as arestas (com pesos) são estradas - Descobrir a rota de entrega com menor custo - Identificar a rota mais rápida. Problema de Fluxo de redes. : Desta forma como foi citado anteriormente ficam bem evidentes e claras as aplicabilidades dos grafos e a sua importância para a vida das pessoas, como visto não param por ai sendo muito vasta, principalmente nos dias atuais com o crescimento da computação e todas as suas possibilidades. Conforme Ribeiro (2012, p. 04) as aplicabilidades se mostram bem constantes na informática ou na ciência da computação, como segue: Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 8 Dada a enorme utilidade dos grafos como representações de conhecimento, existe toda uma área de Ciência de Computadores dedicada ao seu estudo e são inúmeros e muito importantes os algoritmos que manipulam grafos.Um exemplo é o Algoritmo de Dijkstra, que encontra o caminho mais curto entre um nó e todos os outros nós, num grafo pesado. Existem muitos outros algoritmos para outras tarefas tais como maximizar o fluxo entre nós ou encontrar a árvore mínima de suporte. Ribeiro (2012, p. 05) cita que que: Do ponto de vista da Programação, um grafo é uma estrutura de dados e existem duas maneiras base de o implementar na prática: Matriz de Adjacências: uma matriz de V por V células, onde a célula na linha i e coluna j nos dá informação sobre a ligação entre os nós i e j. Por exemplo, se o grafo não for pesado, a célula podia conter o valor verdadeiro (ou um) quando existisse uma ligação entre i e j e o valor falso (ou zero) quando tal não acontecesse. Se o grafo for pesado, cada célula pode conter um número representando o peso da aresta. A figura seguinte ilustra um grafo não dirigido e a sua correspondente matriz de adjacências. Lista de Adjacências: um vetor de listas onde a posição i do vetor contém uma lista dos nós aos quais o nó i se encontra ligado. Se o grafo for pesado, cada elemento da lista contém também o peso da ligação. A figura seguinte ilustra um grafo não dirigido e a sua correspondente lista de adjacências. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 9 A matriz permite verificar em tempo constante se uma dada ligação existe ou não. Por oposição, no caso da lista, tal não acontece e é necessário percorrer a lista para saber se um dado nó está ou não ligado. Em contrapartida, se for necessário percorrer todos os nós ligados a um dado nó, a lista é mais eficiente, pois permite percorrer apenas os nós ligados, e não andar a percorrer toda uma linha da matriz, verificando se a ligação existe ou não. Para gravar, na Matriz de Adjacências a pergunta é “A” tem ligação com ? Na Lista de Adjacências a pergunta é “A” esta para ? Sendo assim as aplicabilidades são muitas conforme foi referenciado no exemplo acima indo desde sistemas naturais até sistemas artificiais, como os da computação, sendo nestes a solução ser resolvida por elementos matemáticos como matrizes e listas (vetores). 1.4 Entendendo os grafos Os grafos após este pequeno entendimento inicial possuem uma visão matemática bem forte e se constituem na seguinte sistemática que será apresentada, contendo elementos como Vértices e Arestas. Os grafos podem ser orientados e não orientados. Na sequência deste estudo irá se tratar melhor deste aspecto. Conforme Fortes (2009, 08) Grafo, na verdade é, (...) é uma noção simples, abstrata e intuitiva, usada para representar a idéia de alguma espécie de relação entre os objetos. Graficamente, aparece representado por uma figura com nós ou vértices, significando os objetos, unidos por um traço denominado aresta configurando a relação imaginada. Na figura a seguir esta representada um grafo baseado nas pontes de Euler, como segue: Figura 03 – Representação de grafos baseada nas sete pontes de Euler Fonte: Fontes (2009, p. 09) Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 10 Veja nesta figura acima que os Vértices as letras de “A” até “D” e as Arestas são as ligações entre as letras citadas. A representação matemática segundo Fonte (2009, p. 09) é a seguinte: Como visto a representação é bem simples resultando G = (V, E). Quadro 01 – Representação matemática de um grafo Fonte: Fonte (2009, p. 09) A seguir será mostrado exemplos de grafo para melhor elucidar o contexto acima descrito: Exemplo 1: Conforme Fontes (2009, p. 10) seria da seguinte forma como no exemplo 1: A figura acima mostra o grafo G(V,E). Observe que laços (self-loops) são permitidos pela definição. Múltiplas linhas não são permitidas. Neste exemplo, V = {1, 2, 3, 4, 5, 6} e E = {{1,3}, {2,3},{3,4},{3,5},{6,6}}. È comum a utilização da variável vi ou xi, i = 1, 2, ..., n para a distinção dos nós (vértices). |V| = 6, |E| =5. Um grafo é representado matematicamente por: G = (V, E) Onde V é o conjunto de vértices e E é o conjunto de arestas ou ligações entre os vértices. (|V| = n, |E| = m). Onde: n = |V| é a ordem do grafo m = |E| é o tamanho do grafo. Se m = 0 o grafo é dito trivial. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 11 Como visto no exemplo 1 acima os Vértices são as bolinhas numeradas que serão chamadas de números de (1 a 6) e Arestas são as ligações por exemplo (1 a 3) (2 a 3) e assim sucessivamente. Exemplo 2: Neste outro exemplo conforme Fontes (2009, p. 10), têm-se: Seja o grafo G(V,A) dado por: V = {p | p é uma pessoa } A = {(u,v) | < u é amigo de v > } Seja o exemplo: V = {Maria, Pedro, Joana, Luiz } A = {(Maria, Pedro), (Joana, Maria), (Maria, Luiz), (Pedro, Luiz) , (Joana, Pedro) } Construa o grafo do exemplo acima. A construção deste grafo dar-se-ia da seguinte forma conforme figura abaixo: Figura 04 – Representação de grafos do problema Fonte: Fontes (2009, p. 11). Como visto então fica fácil encontrar o formato do grafo, pois se analisando o enunciado dado pelo autor acima: V = {Maria, Pedro, Joana, Luiz } A = {(Maria, Pedro) , (Joana, Maria) , (Maria, Luiz), (Pedro, Luiz) , (Joana, Pedro) } Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 12 Observa-se que os vértices são as pessoas e as arestas são as ligações, portanto o grafo esta pronto. Exercício: Dado o seguinte enunciado na mesma linha de raciocínio do grafo acima, obervando que os vértices são pessoas e as arestas são as ligações solicitadas, construa o grafo seguindo os dados abaixo: V = {Maria, Pedro, Tiago, Ana, Luiz } A = {(Maria, Pedro) , (Pedro, Tiago) , (Maria, Ana), (Maria, Luiz) , (Pedro, Ana), (Pedro, Luiz), (Ana, Tiago), (Tiago, Luiz) } Solução deste grafo: Figura 05 – Representação da solução de grafos Fonte: Alcântara(2014, p. 12). Como visto então basta seguir os relacionamentos solicitados e terá o grafo montado conforme o exemplo acima. 1.4.1 Vértices e Arestas, elementos básicos dos grafos Os grafos possuem basicamente dois elementos que se destacam num primeiro momento, que são os Vértices e as Arestas, sendo estes últimos os elementos que irão ligar-se entre si e formar o grafo e os primeiros são os elos do mesmo, podendo ser representado por números, nomes, etc. Maria Ana Luiz Pedro Tiago Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 13 Conforme Fontes (2009, p. 12) têm-se: Em um grafo não orientado G=(V,E), o conjunto de arestas E consiste em pares de vértices não ordenados. V={1,2,3,4,5,6} E={(1,2),(1,5),(2,5),(3,6)} Fonte: Fontes (2009, p. 12), Neste exemplo dado pelo autor acima citado observa-se que “E” representa as arestas, ou seja, as ligações entre os vértices, representados por “V”. Exercício: Observando-se o mesmo grafo, quais as arestas completariam o grafo em ordem, através de ligações com retas, sendo que o mesmo não poderia cruzar por cima de nenhuma aresta novamente? V={1,2,3,4,5,6} E={(1,2),(1,4),(1,5),(2,3),(2,5),(2,6),(3,6),(4,5),(5,6)} Figura 06 – Solução da representação de elementos de grafos Fonte: Adaptado de Fontes (2009, p. 13), Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 14 1.5 Aspectos gerais dos grafos Como visto até então se entendeu claramente o que são os grafos, bem como suas aplicabilidades, neste item em diante serão mostrados os aspectos gerais dos grafos, como tipos, características, dentre outras, como segue, para proporcionar um melhor entendimento. 1.5.1 Grafos Conforme Conceito...(2014, p. 14) um grafo tem a seguinte sistemática, Um grafo G(V,A) é definido pelo par de conjuntos V e A, onde: V - conjunto não vazio: os vértices ou nodos do grafo; A - conjunto de pares ordenados a=(v,w), v e w ∈ V: as arestas do grafo. Seja, por exemplo, o grafo G(V,A) dado por: V = { p | p é uma pessoa } A = { (v,w) | < v é amigo de w > } Esta definição representa toda uma família de grafos. Um exemplo de elemento desta família (ver G1) é dado por: V = { Maria, Pedro, Joana, Luiz } A = { (Maria, Pedro), (Pedro, Maria), (Joana, Maria), (Maria, Joana), (Pedro, Luiz), (Luiz, Pedro), (Joana, Pedro) , (Pedro, Joana)}. Neste exemplo estamos considerando que a relação <v é amigo de w> é uma relação simétrica, ou seja, se <v é amigo de w> então <w é amigo de v>. Como conseqüência, as arestas que ligam os vértices não possuem qualquer orientação. Na figura a seguir mostra um simples grafo denominado G1. Fonte: Conceito... (2014, p. 14) Como visto então nenhuma novidade do que já foi passado até aqui, só que a partir de agora se mostrará alguns elementos a mais além de Vértices e Arestas dos grafos. Na sequência será visto o que representa o Digrafo. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 15 1.5.2 Digrafo Conforme Conceito... (2014, p. 14) um grafo tem a seguinte sistemática, Considere, agora, o grafo definido por: V = { p | p é uma pessoa da família Castro } A = { (v,w) | < v é pai/mãe de w > } Um exemplo de deste grafo (ver G2) é: V = { Emerson, Isadora, Renata, Antonio, Cecília, Alfredo } A = {(Isadora, Emerson), (Antonio, Renata), (Alfredo, Emerson), (Cecília, Antonio), (Alfredo, Antonio)}. A relação definida por A não é simétrica, pois se <v é pai/mãe de w>, não é o caso de <w é pai/mãe de v>. Há, portanto, uma orientação na relação, com um correspondente efeito na representação gráfica de G. O grafo acima é dito ser um grafo orientado (ou digrafo), sendo que as conexões entre os vértices são chamadas de arcos. Na figura a seguir mostra um simples dígrafo denominado G2. Outro conceito vem de Feofiloff (2013, p. 15) que diz: Um digrafo (= digraph = directed graph) é uma coisa que consiste em dois conjuntos: um conjunto de coisas conhecidas como vértices e um conjunto de coisas conhecidas como arcos. Cada arco é um par ordenado de vértices. O primeiro vértice do par é a ponta inicial do arco e o segundo é a ponta final. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 16 A ponta final de todo arco é diferente de sua ponta inicial. [O livro de Sedgewick admite arcos cuja ponta final é igual à inicial. Arcos desse tipo são conhecidos como laços (= loops). Nossos digrafos não terão laços.] Um arco com ponta inicial v e ponta final w será denotado por v-w . (É preciso estar atento ao contexto para não confundir essa expressão com "v menos w".) Dizemos que o arco v-w sai de v e entra em w. A presença de um arco v-w é independente da presença do arco w-v: o digrafo pode ter os arcos v-w e w-v, pode ter apenas um deles, ou pode não ter nenhum deles. Dizemos que um vértice w é vizinho de um vértice v se v-w é um arco do digrafo. Dizemos também, nessa circunstância, que w é adjacente a v. A relação de vizinhança não é simétrica: w pode ser vizinho de v sem que v seja vizinho de w. (Grifo Nosso). Assim desta forma pode-se definir dígrafo conforme figura a seguir: Um exemplo baseado no digrafo acima conforme Feofiloff (2013, p. 16) seria o seguinte: Uma boa maneira de especificar um digrafo é exibir o seu conjunto de arcos. Por exemplo, o conjunto de arcos 0-5 0-6 2-0 2-3 3-6 3-10 4-1 5-2 5-10 6-2 7-8 8-1 8-4 10-3 11-8 define um digrafo sobre o conjunto de vértices 0..11. O vértice 9 é isolado. (Grifo Nosso). Veja que nos digrafos 0-5 são arcos observando a direção, pois te uma seta ( ), que sai de 0 e vai até 5 e assim para todos os demais. Nos grafos chama-se de arestas. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 17 1.5.3 Características dos grafos em geral Algumas características e particularidades os grafos e digrafos possuem conforme Adaptação de Conceito ... (2014, p. 17), como segue: ORDEM A ordem de um grafo G é dada pela cardinalidade do conjunto de vértices, ou seja, pelo número de vértices de G. Nos exemplos acima: - ordem(G1) = 4 - ordem(G2) = 6 ADJACÊNCIA Em um grafo simples (a exemplo de G1) dois vértices v e w são adjacentes (ou vizinhos) se há uma aresta a=(v,w) em G. Está aresta é dita ser incidente a ambos, v e w. É o caso dos vértices Maria e Pedro em G1. No caso do grafo ser dirigido (a exemplo de G2), a adjacência (vizinhança) é especializada em: Sucessor: um vértice w é sucessor de v se há um arco que parte de v e chega em w. Em G2, por exemplo, diz-se que Emerson e Antonio são sucessores de Alfredo. Antecessor: um vértice v é antecessor de w se há um arco que parte de v e chega em w. Em G2, por exemplo, diz-se que Alfredo e Cecília são antecessores de Antonio. GRAU O grau de um vértice é dado pelo número de arestas que lhe são incidentes. Em G1, por exemplo: - grau(Pedro) = 3 - grau(Maria) = 2 No caso do grafo ser dirigido (a exemplo de G2), a noção de grau é especializada em: Grau de emissão: o grau de emissão de um vértice v corresponde ao número de arcos que partem de v. Em G2, por exemplo: - grauDeEmissão(Antonio) = 1 - grauDeEmissao(Alfredo) = 2 - grauDeEmissao(Renata) = 0 Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 18 Grau de recepção: o grau de recepção de um vértice v corresponde ao número de arcos que chegam a v. Em G2, por exemplo: - grauDeRecepção(Antonio) = 2 - grauDeRecepção(Alfredo) = 0 - grauDeRecepção(Renata) = 1 FONTE Um vértice v é uma fonte se grauDeRecepção(v) = 0. É o caso dos vértices Isadora, Alfredo e Cecília em G2. SUMIDOURO Um vértice v é um sumidouro se grauDeEmissão(v) = 0. É o caso dos vértices Renata e Emerson em G2. LAÇO Um laço é uma aresta ou arco do tipo a=(v,v), ou seja, que relaciona um vértice a ele próprio. Em G3 há três ocorrências de laços para um grafo não orientado. G3: Veja que estas características são fáceis de serem identificadas nos grafos e digrafos como segue: - No caso da ORDEM é correspondente ao número de ligações, vértices, veja na figura G1 acima; - No caso da ADJACÊNCIA esta baseada na vizinhança observando que há SUCESSORES no caso da figura G2 acima quando as setas ( ) chegam. Exemplo: Emerson e Antonio são sucessores de Alfredo. Há os ANTECESSORES,que são de onde partem as setas ( ) saem. Ex: Alfredo e Cecília são antecessores de Antonio. - No caso GRAU é número de ligações que cada vértice recebe. Ex: Na figura G1 por exemplo Pedro recebe 03 ligações (arestas). Quando for GRAU em digrafos tem grau de emissão “que partem” e de recepção “que recebem”. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 19 - No caso de FONTE é quando o grau de recepção for ZERO. É o caso dos vértices Renata e Emerson em Figura G2. - No caso de SUMIDOURO é quando o grau de emissão for ZERO. É o caso dos vértices Renata e Emerson em G2. - No caso do LAÇO é quando um vértice (grafo) ou arco (digrafo) se relaciona com ele mesmo. 1.5.4 Alguns tipos de grafos Conforme Conceito ...(2014, p.19) existem alguns tipos de grafos como segue: GRAFO REGULAR Um grafo é dito ser regular quando todos os seus vértices tem o mesmo grau. O grafo G4, por exemplo, é dito ser um grafo regular-3, pois todos os seus vértices tem grau 3. G4: GRAFO COMPLETO Um grafo é dito ser completo quando há uma aresta entre cada par de seus vértices. Estes grafos são designados por Kn, onde n é a ordem do grafo. Um grafo Kn possui o número máximo possível de arestas para um dados n. Ele é, também regular-(n-1) pois todos os seus vértices tem grau n-1. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 20 GRAFO BIPARTIDO Um grafo é dito ser bipartido quando seu conjunto de vértices V puder ser particionado em dois subconjuntos V1 e V2, tais que toda aresta de G une um vértice de V1 a outro de V2. Para exemplificar, sejam os conjuntos H={h | h é um homem} e M={m | m é um mulher} e o grafo G(V,A) (ver o exemplo G5) onde: V = H U M A = {(v,w) | (v ∈ H e w ∈ M) ou (v ∈ M e w ∈ H) e <v foi namorado de w>} G5: O grafo G6 é uma K3,3, ou seja, um grafo bipartido completo que contém duas partições de 3 vértices cada. Ele é completo, pois todos os vértices de uma partição estão ligados a todos os vértices da outra partição. GRAFO ROTULADO Um grafo G(V,A) é dito ser rotulado em vértices (ou arestas) quando a cada vértice (ou aresta) estiver associado um rótulo. G5 é um exemplo de grafo rotulado. GRAFO VALORADO Um grafo G(V,A) é dito ser valorado quando existe uma ou mais funções relacionando V e/ou A com um conjunto de números. Para exemplificar (ver o grafo G7), seja G (V,A) onde: G6: K3,3 Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 21 V = {v | v é uma cidade com aeroporto} A = {(v,w,t) | <há linha aérea ligando v a w, sendo t o tempo esperado de voo>} MULTIGRAFO Um grafo G(V,A) é dito ser um multigrafo quando existem múltiplas arestas entre pares de vértices de G. No grafo G8, por exemplo, há duas arestas entre os vértices A e C e entre os vértices A e B, caracterizando-o como um multigrafo. SUBGRAFO Um grafo Gs(Vs, As) é dito ser subgrafo de um grafo G(V,A) quando Vs ⊆ V e As ⊆ A. O grafo G9, por exemplo, é subgrafo de G8. G9: HIPERGRAFO Um hipergrafo H(V,A) é definido pelo par de conjuntos V e A, onde: V - conjunto não vazio;A - uma família e partes não vazias de V. G7: G8: Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 22 Seja, por exemplo, o grafo H(V,A) dado por: V = { x1, x2, x3, x4} A = { {x1, x2, x4}, {x2, x3, x4}, {x2, x3}} G10: Como visto acima são vários tipos de grafos existentes e todos tem a sua importância neste nosso estudo. 1.5.5 Percurso de grafos Neste item conforme Conceito... (2014, p.22) têm-se os mais variados percursos de grafos que se tem como segue: CADEIA Uma cadeia é uma sequência qualquer de arestas adjacentes que ligam dois vértices. O conceito de cadeia vale também para grafos orientados, bastando que se ignore o sentido da orientação dos arcos. A seqüência de vértices (x6, x5, x4, x1) é um exemplo de cadeia em G11. Uma cadeia é dita ser elementar se não passa duas vezes pelo mesmo vértice. É dita ser simples se não passa duas vezes pela mesma aresta (arco). O comprimento de uma cadeia é o número de arestas (arcos) que a compõe. CAMINHO Um caminho é uma cadeia na qual todos os arcos possuem a mesma orientação. Aplica-se, portanto, somente a grafos orientados. A seqüência de vértices (x1, x2, x5, x6, x3) é um exemplo de caminho em G11. CICLO Um ciclo é uma cadeia simples e fechada (o vértice inicial é o mesmo que o vértice final). A seqüência de vértices (x1, x2, x3, x6, x5, x4, x1) é um exemplo de ciclo elementar em G11. CIRCUITO Um circuito é um caminho simples e fechado. A seqüência de vértices (x1, x2, x5, x4, x1) é um exemplo de circuito elementar em G11. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 23 FECHO TRANSITIVO O fecho transitivo direto (ftd) de um vértice v é o conjunto de todos os vértices que podem ser atingidos por algum caminho iniciando em v. O ftd do vértice x5 do grafo G17, por exemplo, é o conjunto: {x1, x2, x3, x4, x5, x6}. Note que o próprio vértice faz parte do ftd já que ele é alcançável partindo-se dele mesmo. O fecho transitivo inverso (fti) de um vértice v é o conjunto de todos os vértices a partir dos quais se pode atingir v por algum caminho. O fti do vértice x5 do grafo G17, por exemplo, é o conjunto: {x1, x2, x4, x5, x7}. Note que o próprio vértice faz parte do fti já que dele se pode alncançar ele mesmo. G11: Como visto acima se tem vários tipos de percursos do grafos disponíveis. 1.5.6 Conexões de grafos Neste item serão estudadas as formas como os grafos se conectam entre si, conforme Conceito... (2014, p.23), como segue: GRAFO CONEXO Um grafo G(V,A) é dito ser conexo se há pelo menos uma cadeia ligando cada par de vértices deste grafo G. G12: Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 24 G13: GRAFO DESCONEXO Um grafo G(V,A) é dito ser desconexo se há pelo menos um par de vértices que não está ligado por nenhuma cadeia. G14: COMPONENTE CONEXA Um grafo G(V,A) desconexo é formado por pelo menos dois subgrafos conexos, disjuntos em relação aos vértices e maximais em relação à inclusão. Cada um destes subgrafos conexos é disto ser uma componente conexa de G. GRAFO FORTEMENTE CONEXO No caso de grafos orientados, um grafo é dito ser fortemente conexo (f- conexo) se todo par de vértices está ligado por pelo menos um caminho em cada sentido, ou seja, se cada par de vértices participa de um circuito. Isto significa que cada vértice pode ser alcançável partindo-se de qualquer outro vértice do grafo. G15: G16: Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 25 COMPONENTE FORTEMENTE CONEXA Um grafo G(V,A) que náo é fortemente conexo é formado por pelo menos dois subgrafos fortemente conexos, disjuntos em relação aos vértices e maximais em relação à inclusão. Cada um destes subgrafos é disto ser uma componente fortemente conexa de G, a exemplo dos subgrafos identificados por S1, S2 e S3 em G17. VÉRTICE DE CORTE Um vértice é dito ser um vértice de corte se sua remoção (juntamente com as arestas a ele conectadas) provoca um redução na conexidade do grafo. Os vértices x2 em G13 e G14 são exemplos de vértices de corte. PONTE Uma aresta é dita ser uma ponte se sua remoção provoca uma redução na conexidade do grafo. As arestas (x1, x2) em G13 e G14 são exemplos de pontes. Na sequência serão estudadas as bases e raízes dos grafos, como segue: G17: Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 26 1.5.7 Bases e raízes dos grafos Neste item serão estudados as bases e raízes dos grafos, como eles funcionam, conforme Conceito... (2014, p.25), como segue: BASE Uma base de um grafo G(V,A) é um subconjunto B ⊆ V, tal que: - dois vértices quaisquer de B não são ligados por nenhum caminho; - todo vértice não pertencente a B pode ser atingido por um caminho partindo de B. ANTI-BASE Uma anti-base de um grafo G(V,A) é um subconjunto A ⊆ V, tal que: - dois vértices quaisquer de A não são ligados por nenhum caminho; - de todo vértice não pertencente a A pode ser atingir A por um caminho. RAIZ Se a base de um grafo G(V,A) é um conjunto unitário, então esta base é a raiz de G. ANTI-RAIZ Se a anti-base de um grafo G(V,A) é um conjunto unitário, então esta anti- base é a anti-raiz de G. G18: G19: Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da ComputaçãoEstrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 27 1.5.8 Arvores em grafos Neste item serão estudados as arvores, mostrando que arvores são grafos, conforme Conceito... (2014, p.27), como segue: ÁRVORE Uma árvore é um grafo conexo sem ciclos. Seja G(V,A) um grafo com ordem n ≥ 2. As propriedades seguintes são equivalentes e suficientes para caracterizar G como uma árvore: 1. G é conexo e sem ciclos; 2. G é sem ciclos e tem n-1 arestas; 3. G é conexo e tem n-1 arestas; 4. G é sem ciclos e por adição de uma aresta se cria um ciclo e somente um; 5. G é conexo, mas deixa de sê-lo se uma aresta é suprimida (todas as arestas são pontes); 6. todo par de vértices de G é unido por uma e somente uma cadeia simples. ARBORESCÊNCIA Uma arborescência é uma árvore que possui uma raiz. Aplica-se, portanto, somente a grafos orientados. G20: G21: Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 28 FLORESTA Uma floresta é um grafo cujas componentes conexas são árvores. 1.5.9 Grafos planares e não planares Neste item será estudado os grafos planares, aqueles que não cruzam por cima de arestas ou arcos do outros e não planares, conforme Conceito ... (2014, p.28), como segue: GRAFOS PLANARES E NÃO PLANARES Um grafo G(V,A) é dito ser planar quando existe alguma forma de se dispor seus vértices em um plano de tal modo que nenhum par de arestas se cruze. Ao lado (A seguir) aparecem três representações gráficas distintas para uma K4 (grafo completo de ordem 4). Apesar de haver um cruzamento de arestas na primeira das representações gráficas, a K4 é um grafo planar pois admite pelo menos uma representação num plano sem que haja cruzamento de arestas (duas possíveis representações aparecem nas figuras ao lado). (grifo nosso). K4: G22: Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 29 Já uma K5 e uma K3,3 são exemplos de grafos não planares. Estes dois grafos não admitem representações planares. 1.5.10 Grafos com colorações Neste item será estudado os grafos e suas colorações, conforme Conceito ... (2014, p.29), como segue: COLORAÇÃO Seja G(V,A) um grafo e C um conjunto de cores. Uma coloração de G é uma atribuição de alguma cor de C para cada vértice de V, de tal modo que a dois vértices adjacentes sejam atribuídas cores diferentes. Assim sendo, uma coloração de G é uma função f: V → C tal que para cada par de vértices (v,w) ∈ A → f(v) ≠ f(w). Uma k-coloração de G é uma coloração que utiliza um total de k cores. O exemplo ao lado mostra um 4-coloração para o grafo. NÚMERO CROMÁTICO Denomina-se número cromático X(G) de um grafo G ao menor número de cores k, para o qual existe uma k-coloração de G. O exemplo ao lado mostra uma 3-coloração para o grafo, que é o número cromático deste grafo. K3,3: K5: Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 30 1.5.11 Grafos isomorfos Neste item serão estudados os grafos isomorfos, conforme Conceito... (2014, p.29), como segue: ISOMORFISMO Sejam dois grafos G1(V1,A1) e G2(V2,A2). Um isomorfismo de G1 sobre G2 é um mapeamento bijetivo f: V1 ↔ V2 tal que (x,y) ∈ A1 se e somente se (f(x),f(y)) ∈ A2, para todo x,y ∈ V1. Os grafos ao lado (a seguir) são isomorfos, pois há a função { (a,2), (b,1), (c,3), (d,4), (e,6), (f,5) } que satisfaz a condição descrita acima. (grifo nosso). Como visto neste item mostra os grafos isomorfos. Outro exemplo de isomorfismo poderia ser o seguinte conforme Wikipédia (2014, p.30), conforme figura a seguir: Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 31 A identificação dos grafos isomórficos é algo muito complexo, conforme Gagnon (2014, p. 31) tem-se uma ideia, como segue: Um grafo completo com v vértices, escrito Kv, é um grafo simples onde todo par de vértices é ligado por uma aresta. Em outras palavras, um grafo completo é um grafo simples que contém o número máximo de arestas. Dois grafos G1(V1,E1) e G2(V2,E2) são ditos isomorfos entre si se existe uma correspondência entre os seus vértices e arestas de tal maneira que a relação de incidência seja preservada. Em outros termos, temos |V1|= |V2| e existe uma função unívoca f: V1-->V2, tal que (i,j) é elemento de E1 se e somente se (ƒ(i),f(j)) é elemento de E2. Eis alguns exemplos de grafos isomorfos: Figura 1 Para ver o isomorfismo dos grafos da figura 2, podemos utilizar a seguinte função: f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 8, f(e) = 5, f(f) = 6, f(g) = 7, f(h) = 4. Imagine você pegando a imagem da direta (com números) da figura acima e girando ela para direita, tem-se a imagem semelhante a da esquerda (com letras) , seria esta uma forma de se identificar se são isomórficas. Separando as figuras se teria: Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 32 Figura 07 – Divisão das imagens Fonte: Adaptado de Gagnon (2014, p. 32) Girando a imagem da direita (com números) teria-se aproximadamente esta imagem: Figura 08 – Nova imagem após o giro Fonte: O Autor Desta forma tem-se a seguinte sequência f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 8, porque os demais ficaram encobertos, onde o 1 encobre o 6; o 2 encobre o 7; o 3 encobre o 4 e o 8 encobre o 5,provando que eles são isomórficos. Posteriormente poderão ser tratado melhor sobre grafos isomórficos. 1.5.12 Subconjunto de grafos Neste item será estudado os subconjuntos (Internamente Estável) e os (Subconjunto Externamente Estável), conforme Conceito ... (2014, p.29), como segue: 1 2 3 8 6 5 7 4 Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 33 SCIE (Subconjunto Internamente Estável) (por vezes também conhecido como conjunto independente) Seja G(V,A) um grafo não orientado. Diz-se que S ⊂ V é um subconjunto internamente estável se dois vértices quaisquer de S nunca são adjacentes entre si. Para o grafo ao lado, são exemplos de SCIE os conjuntos: {2, 3}, {1, 4} e {2, 3, 4} Agora, se dado um SCIE S não existe um outro SCIE S' tal que S' ⊂ S, então S é dito ser um SCIE maximal. Para o grafo ao lado, são exemplos de SCIE maximais os conjuntos: {2, 3, 4}, {1, 6} e {4, 5} SCEE (Subconjunto Externamente Estável) (por vezes também conhecido como conjunto absorvente) Seja G(V,A) um grafo orientado. Diz-se que T ⊂ V é um subconjunto externamente estável se todo vértice não pertencente a T tiver pelo menos um vértice de T como sucessor. Agora, se dado um SCEE S não existe um outro SCEE S' tal que S' ⊂ S, então S é dito ser um SCEE minimal. Para o grafo ao lado, são exemplos de SCEE minimais os conjuntos: {x2, x4, x6} e {x1, x5, x3} Este conceito também pode ser aplicado a grafos não orientados, bastando que consideremos que todo vértice exterior a T deva ter como adjacente pelo menos um vértice de T. Sendo assim concluem-se as diversas características dos grafos, tendo-se assim uma visão mais clara do que representam os mesmos. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 34 1.6 Algoritmos importantes usando grafos Neste item será visto um algoritmo em detalhes que utiliza grafos que se destacam pela história, importância, mas obviamente existem muitos outros que poderão ser pesquisados. Neste caso aqui escolhido é o algoritmo do caminho mínimo, mas existem diversos outros. Sobre os problemas de caminho mínimo será mostrado o algoritmo a seguir, mas eles têm uma grande importância veja a figura: Figura 09 – Menor caminho Fonte: Wikipédia (2014, p. 34). Sendo neste caso acima o menor caminho o seguinte: O caminho mínimo entre D e E não é D-E, mas sim D-F-E, com uma distância de 14. D e F = 6 e F e E = 8, resultando 14. Conforme Wikipédia (2014, p. 34) “Na teoria de grafos, o problema do caminho mínimo consiste na minimização do custo de travessia de um grafo entre dois nós (ou vértices); custo este dado pela soma dos pesos de cada aresta percorrida”. Conforme Wikipédia (2014, p. 34) tem-se que, Os algoritmos especializados em solucionar o problema do caminho mínimo são eventualmente chamados de algoritmos de busca de caminhos. Entre os algoritmos dessa classe, os mais conhecidos são: Algoritmo de Dijkstra — Resolve o problema com um vértice-fonte em grafos cujas arestas tenham peso maior ou igual a zero. Sem reduzir o Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 35 desempenho, este algoritmo é capaz de determinar o caminho mínimo, partindo de um vértice de início v para todos os outros vértices do grafo. Algoritmo de Bellman-Ford — Resolve o problema para grafos com um vértice-fonte e arestas que podem ter pesos negativos. Algoritmo A* — um algoritmo heurístico que calcula o caminho mínimo com um vértice-fonte. Algoritmo de Floyd-Warshall — Determina a distância entre todos os pares de vértices de um grafo. Algoritmo de Johnson — Determina a distância entre todos os pares de vértices de um grafo, pode ser mais veloz que o algoritmo de Floyd- Warshall em grafos esparsos. O problema de caminho mínimo é um dos problemas genéricos intensamente estudados e utilizados em diversas áreas como Engenharia de Transportes, Pesquisa Operacional, Ciência da Computação e Inteligência Artificial. Isso decorre do seu potencial de aplicação a inúmeros problemas práticos que ocorrem em transportes, logística, redes de computadores e de telecomunicações, etc. Outras possibilidades de aplicação incluem quaisquer problemas envolvendo redes ou grafos em que se tenha grandezas (distâncias, tempo, perdas, ganhos, despesas) que se acumulem linearmente ao longo do percurso da rede. Um problema relacionado é o Problema do Caixeiro-viajante, que consiste em determinar o caminho mais curto que passa exatamente uma vez por cada vértice e retorna ao vértice de partida. Este é um problema NP- Completo, para os quais não há uma solução eficiente. (Grifo nosso) Neste estudo será visto o algoritmo de Algoritmo de Dijkstra, como segue: 1.6.1 Algoritmo de Dijkstra Conforme se sabe Dijkstra foi um grande cientista da computação em meados dos anos 50, como segue: Conforme Wikipédia (2014, p. 34), tem-se: O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 1959, soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional O([m+n]log n) onde m é o número de arestas e n é o número de vértices. O algoritmo que serve para resolver o mesmo problema em um grafo com pesos negativos é o algoritmo de Bellman-Ford, que possui maior tempo de execução que o Dijkstra. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 36 O algoritmo de Dijkstra assemelha-se ao BFS, mas é um algoritmo guloso, ou seja, toma a decisão que parece ótima no momento. Para a teoria dos grafos uma "estratégia gulosa" é conveniente já que sendo P um menor caminho entre 2 vértices U e V, todo sub-caminho de P é um menor caminho entre 2 vértices pertencentes ao caminho P, desta forma construímos os melhores caminhos dos vértices alcançáveis pelo vértice inicial determinando todos os melhores caminhos intermediários. Nota: diz-se 'um menor caminho' pois caso existam 2 'menores caminhos' apenas um será descoberto. O algoritmo considera um conjunto S de menores caminhos, iniciado com um vérticeinicial I. A cada passo do algoritmo busca-se nas adjacências dos vértices pertencentes a S aquele vértice com menor distância relativa a I e adiciona-o a S e, então, repetindo os passos até que todos os vértices alcançáveis por I estejam em S. Arestas que ligam vértices já pertencentes a S são desconsideradas. Conforme Wikipédia (2014, p. 34), a aplicabilidade poderia ser a seguinte: Um exemplo prático do problema que pode ser resolvido pelo algoritmo de Dijkstra é: alguém precisa se deslocar de uma cidade para outra. Para isso, ela dispõe de várias estradas, que passam por diversas cidades. Qual delas oferece uma trajetória de menor caminho? Sendo assim tem-se uma ideia boa para que serve o algoritmo de Dijkstra. O algoritmo seria o seguinte, conforme Wikipédia (2014, p. 35), seguindo os seguintes passos: 1º passo: iniciam-se os valores: para todo v ∈ V[G] d[v]← ∞ π[v] ← -1 d[s] ← 0 V[G] é o conjunto de vértices(v) que formam o Grafo G. d[v] é o vetor de distâncias de s até cada v. Admitindo-se a pior estimativa possível, o caminho infinito. π[v] identifica o vértice de onde se origina uma conexão até v de maneira a formar um caminho mínimo. 2º passo: temos que usar o conjunto Q, cujos vértices ainda não contém o custo do menor caminho d[v] determinado. Q ← V[G] Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 37 3º passo: realizamos uma série de relaxamentos das arestas, de acordo com o código: enquanto Q ≠ ø u ← extrair-mín(Q) //Q ← Q - {u} para cada v adjacente a u se d[v] > d[u] + w(u, v) //relaxe (u, v) então d[v] ← d[u] + w(u, v) π[v] ← u Q ← Q ∪ {v} w(u, v) é o peso(weight) da aresta que vai de u a v. u e v são vértices quaisquer e s é o vértice inicial. ffd extrair-mín(Q), pode usar um heap de mínimo ou uma lista de vértices onde se extrai o elemento u com menor valor d[u]. No final do algoritmo teremos o menor caminho entre s e qualquer outro vértice de G. O algoritmo leva tempo O(m + n log n) caso seja usado um heap de Fibonacci, O(m log n) caso seja usado um heap binário e O(n²) caso seja usado um vetor para armazenar Q. Na sequência será mostrado um esquema do algoritmo e um link para poder ver em tempo real como ele funciona. Veja a figura a seguir: Figura 10 – Dinâmica do algoritmo de Dijkstra Fonte: Adaptado de Wikipédia (2014, p. 36) Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 38 A figura acima tem o resultado final, mas veja a animação no link abaixo. http://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra O funcionamento é o seguinte: Observando o grafo acima se tem um conjunto de vértices variando de 1 a 6 e diversas arestas valoradas como valores nas distâncias. Partindo-se do vértice 1 observa-se que se tem ligação com o 2, 3 e o 6. O menor caminho é o de valor 7 então ele vai até ali, que é o vértice 2. Figura 11 – Dinâmica do algoritmo de Dijkstra Fonte: Adaptado de Wikipédia (2014, p. 36) No vértice 2 observa-se que se tem ligação com o 3 e o 4. O menor caminho é o de valor 10 então ele vai até o vértice 3. Figura 12 – Dinâmica do algoritmo de Dijkstra Fonte: Adaptado de Wikipédia (2014, p. 37) Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 39 Estando-se no vértice 3 observa-se que se tem ligação com o 4 e o 6. O menor caminho é o de valor 2 então ele vai até o vértice 6. Figura 13 – Dinâmica do algoritmo de Dijkstra Fonte: Adaptado de Wikipédia (2014, p. 37) Estando no vértice 6 observa-se que é o final e ai termina o caminho, pois os vértices vão de 1 até 6, não tendo sentido ele retroceder indo ao 4 ou 5. Figura 14 – Dinâmica do algoritmo de Dijkstra Fonte: Adaptado de Wikipédia (2014, p. 38) Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 40 Como visto este algoritmo pode ser resolvido desta forma, observando o menor caminho, analisando se os mesmos são positivos é claro, como já foi explicado no início. 1.7 Usabilidade com Bancos de dados orientados a grafos. Um dos motivos de se estudar grafos é a aplicabilidade em bases de dados tanto relacionais, orientadas a objetos e até mesmo em outras formas como arquivos de dados que não possuem um gerenciador para auxiliar e são pouco usados. Mas existem bancos de dados orientados a grafos e isto é uma realidade. Na internet fazem uma comparação da seguinte forma: Bancos de dados relacionais foram criados em 1970 aproximadamente e Bancos de dados orientados a grafos vêm de 1736 aproximadamente com o matemático Euler. Matemático que já foi citado anteriormente, como sendo o pioneiro na teoria dos grafos. Mas é claro que é só uma brincadeira!!!. Conforme Sato (2014, p. 40) cita que, É normal, quando falamos de banco de dados, lembrarmos primeiramente de bases relacionais, do tipo SQL. Uma base relacional possui a tabelas, colunas, tuplas (linhas), chaves e relacionamentos. Quando temos um relacionamento entre uma tabela e outra, uma das tabelas possui a indicação de foreign key, chave estrangeira. Quando possuímos então o chamado Many to Many (muito para muito) colocamos uma terceira tabela ligando às outras duas e seus relacionamentos. Em um banco de dados de grafos, relacionamentos são mais naturais. Temos as entidades chamadas de vértices (ou node) que são ligadas entre elas pelas arestas (ou relationships) cada um podendo guardar dados entre os relacionamentos e cada relacionamento pode ter uma direção. (Grifo nosso). Como visto com grafos os relacionamentossão mais naturais até pela sua forma de existir, pois veja se eu tenho um amigo chamado João e ele tem um amigo chamado Pedro, que tem uma amiga chamada Ana, que tem .... e assim vai o número de relacionamentos observando que eu também posso ser amigo de todos eles ou de alguns deles, formando uma grande rede, que hoje são as redes sociais. Prestando bem atenção quando se entra numa rede social muitas vezes vêm imagens de pessoas que a princípio não as conhecemos, mas nossos amigos as conhecem e elas direta ou indiretamente estão interligadas a nós e isto são bases de dados orientadas a grafos. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 41 Conforme Sato (2014, p. 40) a sua representação poderia ser a seguinte: Figura 15 – Ideia de relacionamentos de banco de dados em grafos Fonte: Sato (2014, p.41) Como visto os relacionamentos são muitos entre as bolas vermelhas, podendo umas se relacionar com quase todas de forma direta ou indiretamente. Conforme Sato (2014, p. 41) a ideia é a seguinte, A imagem mostra um exemplo da ideia de grafos. As esferas vermelhas são os vértices e as arestas seus relacionamentos. Apesar de todos aqui possuírem a indicação “relaciona”, cada relacionamento pode guardar dados diferentes sobre o relacionamento. Por exemplo: no twitter podemos ligar uma pessoa a outra pelo relacionamento de seguir. Podemos guardar junto a data de início da relação e a pessoa pode seguir de volta. Podemos também ter vértices de outros tipos, como tweets. Uma pessoa se relaciona a um tweet escrevendo ele ou dando RT. Baseado na teoria de grafos, essas bases são um tipo dentro do mundo das bases noSQL. Ao pensar em noSQL já lembramos que esses são bancos mais rápidos (potencialmente menos seguros) e fáceis de escalar. A velocidade de se comparar um banco de dados relacional com um banco de dados de grafos vem na hora de se comparar uma busca cheia de joins index em um banco SQL e a simplicidade de se buscar relacionamentos em grafos. Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 42 Na verdade as possibilidades são muitas em relação a bancos de dados orientados a grafos e por isso é uma vasta área a ser explorada atualmente. Nos bancos de dados orientados a grafos os elementos são basicamente os vértices e as arestas, como cita Sato (2014, p. 42), Itens de um banco de dados de Grafos Vértice: Também pode ser chamado de nó é a nossa unidade de dados, um conjunto de propriedades do tipo chave valor que representam uma entidade. Um exemplo seria um usuário o Twitter: nome: “Priscila Sato” arroba: “MayogaX” Aresta: São os nossos relacionamentos. Eles ligam os vértices por meio de uma rede semântica. Uma aresta pode possuir um sentido, uma orientação e, se necessário, dados sobre esse relacionamento. Exemplo baseado no Twitter: vértice “Priscila” segue o vértice “Lucas” desde 2012. “Priscila” e “Lucas” são vértices ligados pelo relacionamento “segue” que possui um sentido: do primeiro ao segundo, e possui também dados: a data de início do relacionamento. (Grifo Nosso). São elementos simples que os bancos de dados orientados a grafos possuem como: vértices e arestas. A autora Sato (2014, p. 42) cita, Como manipulo acesso a dados em bases de dados de grafos? A maioria das bases de dados de grafos disponibilizam uma API REST para você poder manipular os dados. Algumas feitas em java disponibilizam um meio amigável para acessar suas classes e fazer buscas em suas bibliotecas. No caso de Neo4J, você pode usar uma linguagem de query específica chamada cypher. Existe também o BrightstarDB que possui uma lib que eles chamam de Entity Framework para noSQL. (Grifo Nosso). Como visto é amplo à forma de manipulação de dados com os bancos de dados orientados a grafos. Conforme Sato (2014, p. 43) os principais bancos de dados orientados a grafos são os seguintes: Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 43 Exemplos de banco de dados de grafos existentes: AllegroGraph ArangoDb Bitsy (java) BrightstarDB (feito para .Net) DEX (possui api .Net e roda em windows) Filament InfiniteGraph InfoGrid HyperGraphDb Oracle Spatial Titan Neo4J (provavelmente o mais famoso de todos). (Grifo Nosso). Pois bem, ai fica uma pergunta: Porque os Bancos de dados orientados a grafos não são tão difundidos quanto os relacionais, por exemplo? Não se pode afirmar, mas o lado comercial ainda fala mais alto hoje em dia mesmo sendo na área de computação e mesmo vendo que eles são muito uteis para situações tão atuais como redes sociais, sistemas de recomendação e etc. 1.7.1 Aplicabilidade dos Bancos de dados que usam grafos Muitas são as aplicabilidades dos bancos de dados orientados a grafos destacando-se atualmente as redes sociais, bancos de dados geográficos (Ex: Google Maps), dentre outras, como sistemas de recomendações em e-commerce em geral. Mas conforme Sato (2014, p. 43) vem a pergunta: Como fazer um sistema de recomendações simples sem usar tanta complexidade? A resposta é usar uma base de dados de grafos. Podemos usar o número de relações para classificar um item para ser indicado. Por exemplo, três itens, um A, um B, e um C possuem ligações com usuários do tipo “curtiu”. Se muita gente curtiu produto A e C ao mesmo tempo, ao pegar um único usuário que curtiu item A e formos sugerir um novo item, vamos sugerir o item B ou o item C? O C, né? Porque quem gosta de A tem um gosto parecido com quem gostou de C. Para isso facilita usar banco de dados de grafos. Claro que você pode usar algoritmos mais complexos para misturar uma base de grafos com uma classificação de conteúdo, por exemplo. A aplicabilidade é a seguinte conforme Sato (2014, p. 43), Você conhece sistemas de recomendações, são itens básicos em e-commerces. A Amazon virou referencia em e-commerce e um dos motivos foi a recomendação Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação Estrutura de Dados II - Capitulo 1 - Introdução a Grafos (EDII_C1_Introdução_Grafos) 44 de produtos. O Google também é ótimo nisso, com base nas suas pesquisas anteriores e gostos pessoais ele altera a ordem dos resultados
Compartilhar