Conceitos de grafos

Conceito Básicos da Teoria de Grafos
GRAFO
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), v e w ∈ V: as arestas do grafo.
Seja, por exemplo, o grafo G(V,A) dado por:
V = { p | p é uma pessoa }
A = { (v,w) | < v é amigo de w > }
Esta definição representa toda uma família de grafos. Um exemplo de elemento desta família (ver G1) é dado por:
V = { Maria, Pedro, Joana, Luiz }
A = { (Maria, Pedro), (Pedro, Maria), (Joana, Maria), (Maria, Joana), (Pedro, Luiz), (Luiz, Pedro), (Joana, Pedro) , (Pedro, Joana) }
G1:

Neste exemplo estamos considerando que a relação é uma relação simétrica, ou seja, se então . Como conseqüência, as arestas que ligam os vértices não possuem qualquer orientação
DIGRAFO (Grafo Orientado)
Considere, agora, o grafo definido por:
V = { p | p é uma pessoa da família Castro }
A = { (v,w) | < v é pai/mãe de w > }
Um exemplo de deste grafo (ver G2) é:
V = { Emerson, Isadora, Renata, Antonio, Cecília, Alfredo }
A = {(Isadora, Emerson), (Antonio, Renata), (Alfredo, Emerson), (Cecília, Antonio), (Alfredo, Antonio)}
G2:

A relação definida por A não é simétrica pois se , não é o caso de . Há, portanto, uma orientação na relação, com um correspondente efeito na representação gráfica de G.
O grafo acima é dito ser um grafo orientado (ou digrafo), sendo que as conexões entre os vértices são chamadas de arcos.

ORDEM
A ordem de um grafo G é dada pela cardinalidade do conjunto de vértices, ou seja, pelo número de vértices de G. Nos exemplos acima: ordem(G1) = 4 ordem(G2) = 6
ADJACÊNCIA
Em um grafo simples (a exemplo de G1) dois vértices v e w são adjacentes (ou vizinhos) se há uma aresta a=(v,w) em G. Está aresta é dita ser incidente a ambos, v e w. É o caso dos vértices Maria e Pedro em G1. No caso do grafo ser dirigido (a exemplo de G2), a adjacência (vizinhança) é especializada em:
Sucessor: um vértice w é