Grafo

Origem: Wikipédia, a enciclopédia livre.

Um grafo com 6 vértices e 7 arestas.

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 de petri no âmbito do planeamento de projectos. Neste caso, 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.

[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.