Teoria dos 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 <v é amigo de w> é uma relação simétrica, ou seja, se <v é amigo de w> então <w é amigo de v>. 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, Rosane, 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 <v é pai/mãe de w>, não é o caso de <w é pai/mãe de v>. 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