​

Definição de Grafo:

Grafo é uma Estrutura Matemática G(V,A), onde:V=Conjunto (finito ou não) de Vértices ou Nós. V ≠ Ø (Conjunto Vazio); A=Conjunto de Arcos (elementos do Produto cartesiano V x V={(x,y); x e y são Vértices de V}. Isto é, A ⊆ VxV. No caso de Grafos Orientados. Seja a=(x,y) um arco unindo os vértices x e y. Então diz-se que:

x=i(a)=início do arco a;

         =antecessor de y;

          =pai de y;

 

y=t(a)=término de a;

         =sucessor de x;

         =filho de x;

x e y  =ex(a)=extremos ou extremidades de a.

 

Definições: Se a=(x,x), diz-se que a é um Laço. Se existir a nos dois sentidos, então a é uma Aresta.

 

Definição - Sucessores e Antecessores: Conjunto de Sucessores de um Vértice é o conjunto definido por:

 

 

 

Definição – Grau de um Vértice: Grau de Saída de um Vértice x é denominado por d0(x), e é definido por:

 

 

 

Grau de Entrada de um Vértice x é denotado por di(x), e é definido por:

 

 

 

Definição – SubGrafos e Grafos Parciais

Um SubGrafo de G(V,A) é um grafo G(N,AN), onde N ⊂ V e AN é o subconjunto de arcos de A que pertencem ao Produto Cartesiano NxN.

 

Um Grafo Parcial de G(V,A) é um grafo G(V,A’), onde A’ ⊂ A.

 

Um SubGrafo Parcial de G(V,A) é uma grafo G(N,AN’) que é um Grafo Parcial do SubGrafo G(N,AN).

 

 

Definição – Caminhos e Cadeias

Caminho de Comprimento g é uma Sequência de g Arcos=(a1, a2, . . ., ag), tal que t(ai)=i(ai+1), para i=1, 2, . . ., g-1.

 

Circuito de Comprimento g é um Caminho Fechado de Comprimento g, ou seja, é um Caminho tal que i(a1)=t(ag).

 

Cadeia de Comprimento g é uma Sequência de g Arcos, onde ex(ai)=ex(ai+1) e ex(ai)=ex(ai-1), para i=1, 2, . . ., g-1.