Introdução à Teoria dos Grafos

Grafo - estrutura matemática usada para representar as relações entre as coisas ou objectos.

Os grafos possuem nós ou vértices (coisas/objectos) e arestas (relações entre as coisas). Se designarmos por V ( conjunto não-vazio de vértices) e A (conjunto das arestas, constituído por pares não ordenados de vértices) então o grafo G é o par (V, A).

 Exemplos:
1. Mapa rodoviário -> nele as cidades (vértices) relacionam-se entre si através das várias estradas (arestas).
2. Sistema de distribuição de água /electricidade/gás -> nele as casas (vértices) relacionam-se entre si (e entre as centrais de distribuição) através dos canos de água/postes de electricidade/canos de gás (arestas).
3. Rede do Metropolitano -> nela as estações (vértices) estão ligadas entre si através de vias onde circulam os comboios (arestas)

Um grafo G=(V, A) consiste, pois, em:


- um conjunto finito de pontos V. Os elementos de V dizem-se os vértices de G.

- um conjunto finito A de pares não ordenados de V, que se dizem as arestas de G.

Uma aresta a em A é um par não ordenado {v, w} de vértices v, w em V, que se dizem as extremidades   de a.

Duas arestas distintas podem ter as mesmas extremidades (mesmos vértices) dizendo-se nesse caso arestas paralelas.

Uma aresta com as duas extremidades iguais diz-se um lacete.

Um vértice que não tem ligação com nenhum outro vértice é um vértice isolado.

Um grafo  sem arestas é um grafo nulo.

Grafo simples é todo aquele que não possui arestas paralelas nem lacetes.

ADJACÊNCIA,ORDEM, DIMENSÃO E GRAU

Num grafo, dois vértices dizem-se adjacentes se tiverem uma aresta que os una.

Num grafo, duas arestas dizem-se adjacentes se tiverem um vértice em comum.

A ordem de um grafo representa o número de vértices desse grafo.

A dimensão de um grafo representa o número de arestas desse grafo.

O grau ou valência de um vértice é igual ao número de arestas que começam (ou terminam) nesse vértice.

Grafo regular é um grafo cujos  vértices têm o mesmo grau.

MULTIGRAFO

Multigrafo é um grafo em que entre dois dos seus vértices existem duas ou mais arestas ou em que existem lacetes.


Em qualquer grafo:

soma de todos os graus dos vértices = 2 x número de arestas

A figura   traz a representação gráfica do grafo G acima, onde
 G = (V, A) = ({v0, v1, v2, v3, v4, v5}, {(v0, v3), (v0, v2), (v1, v2), (v2, v3), (v3, v4)}) =
     = ({v0, v1, v2, v3, v4, v5}, {e0, e1,e2, e3, e4})


Os seus vértices correspondem a pontos distintos do plano em posição aleatória e  as suas arestas correspondem a rectas ou curvas que unem estes pontos.

Um grafo completo com n vértices, designado Kn, é um grafo simples onde todo par de vértices é ligado por uma aresta. Por outras palavras, um grafo completo é um grafo simples que contém o número máximo de arestas.

Eis alguns exemplos de grafos completos:

O grafo K1 chama-se grafo trivial.

Assim, o número de arestas de um grafo completo é

sendo n o número de vértices do grafo.