A2 TADS4 Estrutura De Dados Teleaula 8 Tema 8 Impressao

18/09/2014

Estrutura de Dados
Tema 8: Grafos e suas Aplicações

O que é um Grafo?
É uma estrutura formada por um conjunto de não vazio de vértices (ou nós) e por um conjunto de arestas (ou arcos), ligando estes vértices. A
C

B

Área de segurança para intérprete de Libras.

D

O que é um Grafo?
No grafo a seguir temos o seguintes conjuntos:
V = {A, B, C, D, E}
A = {(A,A), (A,B), (A, B), (A,C), (B,D), (B,E), (C,E)}
A
C

B
D

Área de segurança para intérprete de Libras.

E

1

18/09/2014

O que é um Grafo?
Seja G um grafo onde V é o conjunto dos vértices e A é o conjunto das arestas.
Afirmar que A contém a aresta v-w, é o mesmo que afirmar que A contém a aresta w-v (com v e w  V).

Área de segurança para intérprete de Libras.

Definições importantes
• Um grafo é simples (ou regular) se não possuir laços e nem mais de uma aresta ligando dois vértices. Grafo simples
A

E

C

B
D

Multigrafo

A

E

Área de segurança para intérprete de Libras.

C

B
D

Definições importantes
• A vizinhança de um nó é definida assim:
N(v) = {w  V | v-w  A}.
Nestes casos podemos dizer que o vértice w é adjacente a v e que a aresta v-w incide no vértice v.
N(A) = {B, C, E}
A

E

C

B

Área de segurança para intérprete de Libras.

D

2

18/09/2014

Definições importantes
• O grau de um vértice é a quantidade de arestas que incidem nele.
• Um vértice é dito isolado se possuir grau zero.
F

A

C

B

E

D

G(A) = 3
G(B) = 2
G(C) = 1
G(D) = 3
Área de segurança para
G(E) = 2 intérprete de Libras.
G(F) = 0

Definições importantes
• Um grafo completo com n vértices é um grafo simples onde existe uma aresta ligando todo par não ordenado vértices distintos.
• O número máximo de arestas em um grafo com n vértices é n * (n-1) /2.
A
B

Área de segurança para intérprete de Libras.

C

E

D

Definições importantes
• Um grafo não precisa ser uma árvore, mas toda árvore é um grafo.
Não árvore
A
A

D

C

B
D

C

B

E

árvore

E

Área de segurança para intérprete de Libras.

3

18/09/2014