Teoria dos grafos

Conceitos 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: são os vértices ou nós 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 é o dado por: V={Maria, Pedro, Joana, Luiz} e A= {(Maria, Pedro),(Joana, Maria), (Pedro, Luiz), (Joana, Pedro)}:

[pic]

G1 (este mostra o esquema de um grafo)

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 . Como conseqüência, as arestas que ligam cós vértices não possuem qualquer orientação.

Dígrafo (Grafo orientado)

Considere agora um grafo definido por:
V={p|p é uma pessoa da família Castro}
A={(v,w)| < v é pai/mãe de w>}
Um exemplo deste grafo é : V-{Emerson, Isadora, Renata, Antônio, Rosane, Cecília, Alfredo}
A={(Isadora, Emerson),(Antônio,Renata),(Alfredo, Emerson), (Cecília, Antônio), (Alfredo, Antônio)}. Veremos o esquema no grafo:

[pic]
G2 (Dígrafo ou Grafo orientado)

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 apresentação gráfica de G. O grafo acima é dito por um grafo orienta ou dígrafo, 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 exemplo abaixo veremos com mais clareza: Ordem (G1)=4 Ordem (G2)=6

Adjacência

É um grafo simples, dois vértices v e w são adjacentes (ou vizinhos) se há uma aresta a= (v,w) em G. Esta aresta é dita ser incidente a ambos, v e w. É o caso dos vértices Maria e