Grafos

Definição de Grafo

Um grafo G=(V,A) consiste 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 dizendo-se nesse caso arestas paralelas. Uma aresta com as duas extremidades iguais diz-se um laçete.

Definições

Chama-se ordem do grafo G ao número de vértices de G, |V|, que representa o cardinal de V.
Uma aresta a em A diz-se incidente com um vértice v em V, se v fôr uma extremidade de a.
Chama-se grau de um vértice v em V ao número deg(v) de arestas incidentes com o vértice v. Os lacetes contam como incidindo duas vezes em v . Um vértice v em V diz-se vizinho de outro vértice w em V se existir uma aresta a em A incidente com v e w.

No exemplo seguinte estão assinaladas a verde todas as arestas incidentes com o vértice d .

Os vértices vizinhos do vértice d:

Teorema

Em qualquer grafo G a soma dos graus de todos os seus vértices é igual ao dobro do número de arestas.

No grafo seguinte estão indicados os graus de todos os vértices. Este grafo tem 11 arestas enquanto a soma de todos os graus é igual a 22.

Grafos Simples

Um grafo G diz-se simples se não tiver lacetes e não tiver arestas paralelas, i.e. se para cada par de vértices distintos existir no máximo uma aresta incidente com ambos.