grafos

GRAFOS
Não é o objecto para espetar a comida…

O que são grafos?
Em matemática e em ciências informáticas, grafo é o objecto básico de estudo da teoria dos grafos. Um grafo consiste num conjunto finito de pontos (vértices) e um conjunto finito de arestas, e cada uma destas arestas liga dois vértices (não necessariamente distintos).
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) onde v e w ∈ V: as arestas do grafo.

Informações sobre grafos
• Grafo: conjunto de vértices e arestas.

• Vértice: objecto simples que pode ter nome e outros atributos.
• Aresta: conexão entre dois vértices.
• Dois vértices são chamados adjacentes se são os dois pontos finais de uma aresta.
• Definimos uma conexão num grafo como uma sequência de arestas que nos permite ir de um vértice a outro continuamente.
• O comprimento de uma conexão é o número de arestas (k) que ela contém. Para o comprimento usamos: k- conexão(ões).
• Quando uma conexão é fechada, ou seja, começa e termina no mesmo vértice, é chamada de circuito.
• Uma conexão que não inclui a mesma aresta mais de uma vez é chamada de conexão simples.
• Matrizes de grafos são sempre simétricas, de dígrafos não.

Para que servem os grafos?
Grafos são usados para representar redes informáticas, redes de transportes, relacionamentos. Existem diversas aplicações para os grafos, tendo como exemplos:
• Logística de transporte;
• Distância entre cidades;
• Conexões de comunicação ligando satélites;
• Linhas de transportes públicos;
• Árvores geneológicas.

Onde são utilizados os grafos?
A teoria dos grafos estuda objectos combinatórios, os grafos, que são um bom modelo para muitos problemas em vários ramos da matemática, da informática, da engenharia e da indústria. Muitos dos problemas sobre grafos tornaram-se célebres porque são um interessante desafio intelectual e porque
têm