Um grafo é um conjunto de pontos, que representam objectos reais, ligados por arestas, que representam relações entre os objectos reais.
Na figura seguinte podemos ver alguns exemplos adicionais do que os nodos (vértices) e arestas podem representar.
Alguns exemplos de grafos:
Os grafos foram inventados por Euler em 1736 para resolver o famoso problema das pontes de Königsberg (a). A questão era saber se era possível atravessar as sete pontes do rio Pregel (b), passando sobre cada uma delas uma só vez, e regressar ao ponto de partida. A ideia de Euler consistiu em representar as quatro zonas da cidade, delimitadas pelo rio, por nodos e as pontes por arestas entre esses nodos (c). O objecto assim construído é um exemplo de um grafo. Pensando neste modelo, é evidente que um tal caminho só é possível se cada nodo estiver ligado a um número par de arestas, pois se se chega a uma zona por uma ponte, a condição de que cada ponte é percorrida uma só vez implica que se possa sair por uma outra. Dado que todos os nodos do grafo têm grau (número de arestas que saem de um nodo) ímpar, um caminho com aquelas propriedades é impossível.(in Escola de Redes)
Sem comentários:
Enviar um comentário