Grafo
Origem: Wikipédia, a enciclopédia livre.
 |
Este artigo ou secção deverá ser fundido no artigo ou secção Teoria dos grafos. Se não concorda, discuta sobre esta fusão na página de discussão daquele artigo. |
Em matemática e ciência da computação, grafo é o objeto básico de estudo da teoria dos grafos. Tipicamente, um grafo é representado como um conjunto de pontos (vértices) ligados por retas (as arestas). Dependendo da aplicação, as arestas podem ser direcionadas, e são representadas por "setas".
Os grafos são muito úteis na representação de problemas da vida real, em vários campos profissionais. Por exemplo, pode-se representar uma mapa de estradas através dos grafos e usar algoritmos específicos para determinar o caminho mais curto entre dois pontos, ou o caminho mais económico. Assim, os grafos podem possuir também pesos (ou custo), quer nas arestas quer nos vértices, e o custo total em estudo será calculado a partir destes pesos.
Outro exemplo da utilização de grafos são as redes PERT no âmbito do planejamento de projetos. Neste caso, a cada aresta está associado o custo de execução, e as tarefas precedentes de uma outra serão suas afluentes.
Outro exemplo banal é o caso das redes de computadores, sendo cada terminal representado por um vértice, o cabo de rede pelas arestas e o custo associado a latência, por exemplo, ou o número de máquinas que a comunicação atravessa entre os nós. É nestes princípios que assenta todo o protocolo IP que torna possível a Internet ser uma realidade. Grafos têm sido utilizados para representar o formalismo das Redes Complexas, onde o número de nós e de conexões entre esses nós é muito alto e complexamente estabelecido.
Índice |
[editar] Introdução
Uma possível definição para grafos: "O grafo propriamente dito é uma representação gráfica das relações existentes entre elementos de dados. Ele pode ser descrito num espaço euclidiano de n dimensões como sendo um conjunto V de vértices e um conjunto A de curvas contínuas (arestas)". Podemos avaliar um grafo através de seu tipo, propriedades e aplicações[1].
[editar] Busca em Grafo
Vários problemas representados por um grafo podem ser resolvidos efetuando uma busca nesse grafo. A busca em grafo consiste em explorar um grafo, de forma que obtenha um processo sistemático de como caminhar por seus vértices e arestas. Às vezes é preciso visitar todos os vértices de um grafos, as vezes o problema pode ser resolvido visitando somente um subconjunto dos vértices. Se o grafo é uma árvore, esta questão se torna simples, podem utilizar as visitas em pré-ordem, ou ordem de nível.
[editar] Algoritmos de percurso
Existem dois métodos de percurso em grafos: DFS Depth First Search (Percurso em Profundidade) e o BFS - Breadth First Search (Percurso em Largura). A idéia básica do DFS (busca em profundidade) é buscar "mais a fundo" no grafo quando possível. Assim, a partir de um vértice v, as arestas ainda não exploradas o são e, ao final, a busca retrocede. A idéia do BFS (busca em largura) é bastante simples: os vértices do grafo são visitados nível a nível, ou seja, todos os vértices a uma distância k do vértice inicial são visitados antes de qualquer vértice a uma distância k +1 do inicial.
[editar] Bibliografia
- http://www.icmc.sc.usp.br/manuals/sce183/gfbus.html
- http://www.inf.ufsc.br/grafos/represen/busca.html
- Cormen. Thomas (2000); Leiserson, Charles.; Rivest, Ronald. Introduction to Algorithmics, McGraw-Hill.
