Grafo E Arvores

Universidade Federal do Vale do São Francisco
Curso de Engenharia da Computação

Matemática Discreta – 10
Prof. Jorge Cavalcanti [e-mail] - www.univasf.edu.br/~jorge.cavalcanti
1

1 - Grafos e Árvores


Muitas aplicações em computação necessitam considerar conjunto de conexões entre pares de objetos:


Existe um caminho para ir de um objeto a outro seguindo as conexões? 

Qual é a menor distância entre um objeto e outro?



Quantos outros objetos podem ser alcançados a partir de um determinado objeto?



Grafos são utilizados para modelar tais problemas.



Alguns exemplos de problemas práticos que podem ser resolvidos através de uma modelagem em grafos:


Ajudar máquinas de busca a localizar informação relevante na
Web.



Descobrir qual é o roteiro mais curto para visitar as principais cidades de uma região turística.
2

1 - Grafos e Árvores


Definição informal - Um grafo é um conjunto não-vazio de nós (vértices) e um conjunto de arcos (arestas) tais que cada arco conecta dois nós.


Os grafos que serão estudados terão sempre um número finito de nós e arcos.

3

1 - Grafos e Árvores


O grafo a seguir tem cinco nós e seis arcos: a3 a2

a1
1





2

a5

a4
3

a6

4

5

A definição informal de um grafo funciona bem se tivermos sua representação visual, mostrando que arcos se conectam aos nós.
Sem essa visualização, precisamos de uma definição formal de mostrar esse grafo.
4

1 - Grafos e Árvores


Definição Formal - Um grafo é uma tripla ordenada (N, A,
g), onde:




N = um conjunto não-vazio de nós (vértices)
A = um conjunto de arcos (arestas) g = uma função que associa a cada arco a a um par nãoordenado x-y de nós, chamado de extremidades de a a3 a2
1



a1

2

a5

a4
3

a6

4

5

Ex. 01: No grafo acima, a função g que associa arcos a suas extremidades é a seguinte: g(a1)=1-2, g(a2)=1-2, g(a3)=2-2, g(a4)=2-3, g(a5)=1-3 e g(a6)=3-4.
5

1 - Grafos e Árvores


Grafo direcionado (dígrafo) – Um grafo é uma tripla