Teoria dos grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 8 (1888 palavras )
  • Download(s) : 0
  • Publicado : 21 de novembro de 2012
Ler documento completo
Amostra do texto
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 umafamí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 ligamcó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 oesquema 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 umgrafo 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 ePedro em G1. No caso do grafo ser dirigido assim em G2, a adjacência é especializado em:
Sucessor: um vértice w é sucessor de v se há um arco que parte de v e chega em w. Em G2, por exemplo, diz-se que Emerson e Antônio 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ãoantecessores de Antônio.



Grau


O grau de um vértice é dado pelo u número de arestas que lhe são incidentes. Em G1 por exemplo:
Grau (Pedro)=3
Grau (Maria)=2
No caso do grafo ser dirigido assim como G2, a noção de grau é especializada em:
Grau de emissão que é um vértice v correspondente ao número de arcos que partem de v. Em G2, por exemplo:
Grau de emissão (Antônio)=1Grau de emissão (Alfredo)=2
Grau de emissão (Renata)=0

Grau de recepção é um vértice v correspondente ao número de arcos que chegam a v. Em G2, por exemplo:
Grau de recepção(Antônio0=2
Grau de recepção(Alfredo)=0
Grau de recepção(Renata)=1


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ãoorientado.

[pic]
G3: mostra os laços em três ocorrências em um grafo não orientado.



Grafo Regular


Um grafo é chamado de regular quando todos os seus vértices tem o mesmo grau. O grafo G4, por exemplo, é dito ser regular – 3 pois todos os seus vértices tem grau 3. fazer o grafo.

[pic]
G4. Ex: grafo regular


Grafo Completo


Um grafo é dito sercompleto quando há uma aresta entre cada par de seus vértices. Estes grafos são designados por kn, onde n é a ordem do grafo. Demonstrar outro grafo.
Um grafo Kn possui o número máximo possível de arestas para um dado n. Ele é também regular (n-1) pois todos os seus vértices tem grau n-1.
[pic]
Ex: Grafo completo.

Grafo Bipartido


Um garfo é chamado bipartido quando seu...
tracking img