Teoria dos grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 10 (2377 palavras )
  • Download(s) : 0
  • Publicado : 28 de novembro de 2011
Ler documento completo
Amostra do texto
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 dew> é 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 umcorrespondente 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 umgrafo 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 é sucessor de v se há um arco que parte de v e chega em w. Em G2, porexemplo, diz-se que Emerson e Antonio são sucessores de Alfredo.

Antecessor: um vértice v é antecessor de w se há um arco que parte de v e chega em w. Em G2, por exemplo, diz-se que Alfredo e Cecília são antecessores de Antonio.

GRAU

O grau de um vértice é dado pelo número de arestas que lhe são incidentes. Em G1, por exemplo:

grau(Pedro) = 3
grau(Maria) = 2No caso do grafo ser dirigido (a exemplo de G2), a noção de grau é especializada em:

Grau de emissão: o grau de emissão de um vértice v corresponde ao número de arcos que partem de v. Em G2, por exemplo:

grauDeEmissão(Antonio) = 1
grauDeEmissao(Alfredo) = 2
grauDeEmissao(Renata) = 0

Grau de recepção: o grau de recepção de um vértice v correspondeao número de arcos que chegam a v. Em G2, por exemplo:

grauDeRecepção(Antonio) = 2
grauDeRecepção(Alfredo) = 0
grauDeRecepção(Renata) = 1

FONTE

Um vértice v é uma fonte se grauDeRecepção(v) = 0. É o caso dos vértices Isadora, Alfredo e Cecília em G2.

SUMIDOURO

Um vértice v é um sumidouro se grauDeEmissão(v) = 0. É o caso dos vértices Renata eEmerson em G2.

LAÇO

Um laço é uma aresta ou arco do tipo a=(v,v), ou seja, que relaciona um vértice a ele próprio. Em G3 há três ocorrências de laços para um grafo não orientado.

G3:

GRAFO REGULAR

Um grafo é dito ser regular quando todos os seus vértices tem o mesmo grau.

O grafo G4, por exemplo, é dito ser um grafo regular-3 pois todos os seus vértices tem grau 3....
tracking img