Wiki Computação

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.
====== Teoria dos Grafos  ======

Grafos são uma área da matemática discreta que estuda a relação entre os objetos de um conjunto. Um grafo G é uma estrutura abstrata formada por dois conjuntos: o primeiro conjunto V(G), finito e não vazio, tem seus elementos chamados de vértices. Vértices costumam ser representados como u, v w, ou vi, vj. O segundo conjunto, E(G), é formado pelos pares não ordenados dos vértices de V(G), que podem ser entendidos como arestas. Arestas, em geral, são representadas pelas letras a, b, c, d ou ei, ej. A representação usual de um grafo é G(V, E), que indica a sua natureza composta por dois conjuntos. 

Uma vez que o conjunto de arestas é formado pelos subconjuntos de pares de vértices, se V(G) tem n elementos, então, por análise combinatória, E(G) tem no máximo n(n-1) / 2 elementos. Se u e v são vértices pertencentes a V(G) e {u, v} ∈ E(G), então é dito que uma aresta incide em u e em v e que estes vértices são adjacentes. A aresta pode ser representada por uv.

Um outro conceito relacionado a grafos é o de valência ou grau. A valência de um vértice é a quantidade de arestas que incidem sobre ele. Se há um laço, a aresta é contada duas vezes. Em dígrafos (grafos nos quais a aresta tem sentido) existem o grau de entrada – a quantidade de arestas que apontam para um vértice - e o grau de saída – a quantidade de arestas que saem de um vértice.

Grafos frequentemente são representados como diagramas nos quais os vértices representam pontos ou círculos e as arestas representam arcos que unem os pontos. Diagramas são úteis porque permitem visualizar esquematicamente as relações entre os objetos de um conjunto. Por isso, grafos são úteis para modelar todo tipo de problema prático. 

Por exemplo, grafos estão presentes na representação da Web (ligação física entre os nós da rede), de redes de comunicação, redes de produção e distribuição de produtos, de rotas de transporte e até mesmo na química orgânica, na qual são utilizados para modelar a estrutura de moléculas.  Apesar de em todos esses exemplos existir uma ligação física entre os objetos do conjunto, não necessariamente é preciso existir uma ligação física. Pode-se definir um grafo desde que exista uma relação binária entre os elementos de um conjunto. Como exemplo, pode-se citar a genealogia, na qual um indivíduo pode ou não ser filho de alguém.

{{:t:figura1.png?nolink |}}

Não se deve confundir a representação de um grafo (geométrica ou mesmo algébrica) com o grafo, que é uma estrutura abstrata. A figura 1 à esquerda simboliza um grafo com os vértices V = {1, 2, 3, 4, 5, 6} e as arestas E = { {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6} }. Existem representações alternativas para grafos, como a representação por intersecção, na qual vértices são objetos geométricos não disjuntos e as arestas são representadas por sua intersecção.

Com a noção de grafo obtida, pode-se definir outros conceitos importantes relacionados. O conceito de passeio diz respeito à sucessão de vértices e arestas percorridos para se chegar a um vértice u partindo de um vértice w. Desta maneira, um passeio pode ser representado por p(w, u) = v0, e1, v1, e2, v2, ..., ek, vk. São três as condições que precisam ser atendidas para um passeio existir:

  * w = v0 e u = vk.
  * Existe pelo menos uma aresta.
  * Para 1 <= i <= k a aresta ei incide sobre vi-1 e vi.

{{ :t:walk-trail-path.png?nolink|}}

As condições acima apenas significam que w e u devem estar conectados entre si por pelo menos uma aresta ou que uma cadeia de arestas deve necessariamente conduzir de um vértice a outro. É possível que alguns vértices e arestas se repitam em um passeio. No grafo da figura 2 ao lado, para se chegar a d partindo de a, por exemplo, pode-se seguir o passeio e9, c, e2, b, e6, a, e9, c, e8, d.

Em um grafo simples, não pode haver mais de uma aresta para um mesmo par de pontos, isto é, não pode haver arestas paralelas. Outra restrição é que uma aresta não pode ter como vértices um mesmo vértice, ou seja, não pode existir laço. 

Um outro conceito importante é o de caminho. Caminho é toda sequência de vértices tal que para todo vértice existe uma aresta que o conecta ao vértice seguinte. Vértices e arestas podem ser repetidos. No grafo da figura 1, a sequência {1, 2, 5, 1, 2, 3} é um caminho.

O comprimento de um caminho é a quantidade de arestas do caminho, sendo que uma aresta pode ser contada duas ou mais a vezes, a depender de quantas vezes se passa por ela. Também pode-se determinar o custo de um caminho quando existem números associados a cada aresta, somando-se os números das arestas percorridas. 
 
Outros conceitos relevantes relacionados a caminhos são dispostos a seguir:

  * **Caminho Euclidiano:** cada aresta é percorrida somente uma vez.
  * **Caminho Hamiltoniano:** cada vértice é percorrido somente uma vez.
  * **Caminhos independentes:** caminhos que não compartilham nenhum vértice entre si. 
  * **Ciclo:** é um caminho cujo vértice final é o mesmo que o vértice inicial. Os ciclos ainda podem ser subdivididos em:
  * **Laços:** ciclos de comprimentos 1, com somente um vértice.
  * **Ciclos simples:** possuem comprimento de no mínimo 3 arestas e o vértice inicial só é atingido novamente no fim do caminho.
  * **Ciclo acíclico:** quando não é simples.

===== História =====
----

O primeiro grafo conhecido foi criado por Leonhard Euler em 1736, quando este propôs uma solução ao problema das pontes de Königsberg. Situada Prússia do século XVIII, hoje denominada Kaliningrado e pertencente à Rússia, Königsberg possuía duas ilhas que se conectavam entre si e com a parte continental através de sete pontes.

{{ :t:konigsberg.png?nolink |}}

Discutia-se na cidade o seguinte problema: seria possível passar por todas as sete pontes sem passar por uma ponte mais de uma vez? Euler representou o problema na forma de um grafo, tomando as intersecções entre as pontes como pontos e as pontes como arestas. Ele então percebeu que só seria possível atingir o objetivo se houvesse no máximo dois pontos com quantidade ímpar de arestas. Isso se deve ao fato de que de cada ponto deveriam partir duas arestas, uma para entrar e outra para sair. Os pontos ímpares se referem ao pontos do início e do fim do percurso, pois estes não precisam de uma entrada e de uma saída, respectivamente.

Inicialmente, o valor da descoberta de Euler passou despercebido, sendo visto como uma solução a uma charada. Isso permaneceu assim, até que em 1847 Gustav Robert Kirchhoff utilizou grafos para representar circuitos elétricos, criando a teoria das árvores. Mais tarde, Cayley, apoiando-se na teoria das árvores, encontrou aplicações na enumeração de hidrocarbonetos alicíclicos saturados. Outra contribuição foi a de William Rowan Hamilton, que foi responsável pela criação do grafo hamiltoniano, que consiste em um caminho fechado que é obtido passando-se somente uma vez por cada vértice.

Com o desenvolvimento dos computadores após a Segunda Guerra Mundial, tornou-se possível utilizar algoritmos para processar grafos. Alguns algoritmos importantes que trabalham com grafos são o algoritmo de Dijkstra, o algoritmo de Kruskal, o algoritmo do vizinho mais próximo e o algoritmo de Prim. O novo recurso da computação acabou por amplificar a influência da teoria dos grafos para as mais diversas áreas.

===== Tipos de grafos =====
----

Apesar de grafos simples não tolerarem laços ou arestas paralelas, essas características e mesmo outras podem estar presentes em outros tipos de grafos. É a reunião de determinadas características em um grafo que determina o seu tipo, sendo possível a um grafo assumir um ou mais tipos ao mesmo tempo. Por exemplo, um grafo com laços e arestas paralelas é denominado **multigrafo**.

Também é possível que arestas que conectam vértices diferentes tenham sentido. Quando isso ocorre, é dito que esse grafo é um **dígrafo** ou um grafo direcionado. A representação s, t : E -> V indica que s(e) é o vértice de origem e t(e) é vértice alvo para o qual a aresta aponta.  Já um **grafo não direcionado**, ou simplesmente grafo, é formado por arestas que não possuem sentido e podem incidir sobre dois vértices ou somente um.

{{ :t:grafo3.png?nolink |}}

A figura acima traz vários conceitos relacionados a grafos. Em a3, observa-se uma aresta do tipo laço. Em a2 e a1, verifica-se a presença de arestas paralelas. As retas a4 e a5 são retas adjacentes pois compartilham o mesmo vértice, enquanto que os vértices 1 e 2 são adjacentes pois são unidos pela reta a1. Além disso, o vértice 5 exemplifica o vértice isolado, não unido a nenhum outro por um arco.

Um grafo simples também pode ser classificado como um **grafo completo** se todos os seus pares de vértices forem adjacentes, ou seja, a quantidade de arestas é exatamente o número máximo, n(n-1) / 2. Alguns outros tipos são enunciados abaixo:

  * **Grafo bipartido:** é formado por dois conjuntos de vértices, V1 e V2, sendo que V 1 ∩ V 2 = ∅ e cada vértice vi de V1 está conectado a um vértice vj de V2.
  * **Grafo rotulado:** quando se associa a uma aresta ou a um vértice um rótulo, que  pode ser uma letra, um nome ou um número. Neste último caso, também é possível chamar o grafo de valorado. Tais valores numéricos podem ser entendidos como o custo da reta ou do ponto e são utilizados em problemas de rota ótima, como por exemplo, no problema do caixeiro viajante. Este é um problema de otimização que busca determinar o menor trajeto para se percorrer um determinado número de cidades, passando somente uma vez por cada uma. Fica claro que esse problema pode ser modulado por grafos, nos quais as arestas simbolizam as estradas, e os vértices, as cidades. 
  * **Grafo vazio:** quando o conjunto de arestas é vazio.
  * **Grafo trivial:** possui somente um vértice e o conjunto E é vazio.
  * **Grafo regular:** todos os vértices estão conectados ao mesmo número de vértices, ou seja, possuem a mesma valência.
  * **Pseudografo:** contém arestas paralelas e laços.
  * **Grafo conexo:** quando é possível chegar a qualquer vértice partindo-se de qualquer vértice.
  * **Árvore:** grafo simples, conexo e acíclico.
  * **Floresta:** conjunto de árvores.

===== Representação de grafos no computador =====
----

Grafos podem ser representados na forma geométrica ou na forma algébrica. Esta última forma é a utilizada para armazenar grafos em computadores. As estruturas de dados utilizadas na representação algébrica de um grafo dependem da estrutura do grafo e do algoritmo que irá operar sobre ele, mas, no geral, utiliza-se listas e matrizes. Listas costumam ser utilizadas em grafos esparsos, aqueles nos quais o número de arestas é pequeno. Matrizes são utilizadas em grafos densos, nos quais a quantidade de arestas se aproxima ou é igual à maior quantidade possível. Contudo, esta última estrutura demanda maior memória para armazenar o grafo.

Existem dois tipos de listas comuns. A lista de adjacência associa a um vértice todos os outros vértices com os quais ele tem uma aresta. O outro tipo é a lista de incidência, que associa a um determinado vértice todas as arestas que incidem nesse vértice.

As matrizes possuem tipos análogos: matrizes de incidência e matrizes de adjacência. Nas matrizes de adjacência, dispõem-se os vértices nas linhas e nas colunas de uma matriz A = [aij]. Se os vértices i e j são adjacentes, então atribui-se o número 1 à posição aij. Do contrário atribui-se 0. Nas de incidência, dispõem-se os vértices nas linhas e as arestas na colunas. Se o vértice i é o ponto inicial da aresta j, atribui-se 1 à posição bij da matriz B = [bij]. Do contrário, ou caso a aresta seja um laço, atribui-se 0.

Se o grafo é direcionado, a matriz de incidência B = [bij] recebe 1 se o vértice i é o ponto inicial da aresta j, -1 se é o ponto final ou 0 se nenhuma das condições anteriores for satisfeita ou for um laço.

Como já foi exposto, alguns grafos podem atribuir valores numéricos a arestas ou vértices. Grafos assim são representados algebricamente por uma matriz de custo, na qual os vértices são dispostos em linhas e em colunas. Assim, se um par de vértices {i, j} ∈ E(G), atribui-se o valor correspondente à posição aij da matriz A = [aij]. Se o par de vértices não possui uma aresta incidente, então, atribui-se 0 ou ∞. Tais valores associados podem indicar distância, fluxo, capacidade, etc.

===== Problemas Clássicos =====
----

Já foram apresentados o problema das pontes de Königsberg e o problema do caixeiro viajante. Existem outros problemas famosos, como o problema do Teorema de quatro cores, que se originou da discussão a respeito de quantas cores são necessárias para se colorir cada região de um mapa com uma cor diferente das cores das regiões adjacentes.

A seguir, uma lista de outros problemas famosos:

  * Problemas de conjuntos de grafos: problema do conjunto independente, problema do clique
  * Problema do caminho mínimo
  * Árvore de extensão mínima
  * Problemas de Roteamento: problema da inspeção de rotas
  * Problema de fluxo de rede: problema de fluxo máximo

===== Referências =====
----

  - MELO, Gildson Soares. **Introdução à Teoria dos Grafos**. Orientador: Napoleón Caro Tuesta. 2014. 35 f. Dissertação (Mestrado) - Curso de Matemática, Rede Nacional PROFMAT-CCEN-UFPB, Universidade Federal da Paraíba, João Pessoa, 2014. Disponível em: https://repositorio.ufpb.br/jspui/bitstream/tede/7549/5/arquivototal.pdf. Acesso em: 27 ago. 2022.
  - FEOFILOFF P.; KOHAYAKAWA, Y.; WAKABAYASHI. Y. **Uma Introdução Sucinta à Teoria dos Grafos**. 61 f. 2011. Departamento de Ciência da Computação do Instituto de Matemática e Estatística da Universidade de São Paulo, São Paulo, 2011. Disponível em: https://www.ime.usp.br/~yw/publications/books/TeoriaDosGrafos.pdf. Acesso em: 27 ago. 2022.
  - **TEORIA DOS GRAFOS E APLICAÇÕES**. Synergismus scyentifica UTFPR, Pato Branco, 2009. Disponível em: http://revistas.utfpr.edu.br/pb/index.php/SysScy/article/view/709. Acesso em 27 ago. 2022.
  - Biggs, N.; Lloyd, E. and Wilson, R. (1986), **Graph Theory**, 1736-1936, Oxford University Press
  - Holanda, Bruno. «**Teoria dos Grafos**» (PDF). OBM. Consultado em 14 de junho de 2018
  - Cayley, A. (1857), «**On the theory of the analytical forms called trees**», Philosophical Magazine, Series IV, 13 (85): 172–176, doi:10.1017/CBO9780511703690.046
  - Tutte, W.T. (2001), **Graph Theory**, ISBN 978-0-521-79489-3, Cambridge University Press, p. 30, consultado em 14 de março de 2016
  -  «**The Four Color Theorem**». Mathpages.com. Consultado em 3 de junho de 2016
  -  Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1994), «**Algorithms for Drawing Graphs: an Annotated Bibliography**», Computational Geometry: Theory and Applications, 4: 235–282, doi:10.1016/0925-7721(94)00014-x
  -  Longabaugh, William (2012), «**Combing the hairball with BioFabric: a new approach for visualization of large networks**» (PDF), BMC Bioinformatics, 13, PMID 23102059, doi:10.1186/1471-2105-13-275
  -  Goodrich, Michael T.; Tamassia, Roberto (2001). **Estruturas de Dados e Algoritmos em Java 2ª ed.** Porto Alegre: Bookman. p. 502-503. ISBN 85-363-0043-4
  -  Goodrich, Michael T.; Tamassia, Roberto (2004). **Projeto de Algoritmos. Fundamentos, Análise e Exemplos da Internet**. Porto Alegre: Bookman. p. 299-303. ISBN 85-363-0303-4
  -  West, Douglas Brent (2001). «Chapter 1 - Fundamental Concepts». **Introduction to Graph Theory** 2nd ed. USA: Prentice Hall. p. 20. ISBN 0-13-014400-2