Grafos
Muitos problemas formulados em objetos e
conexões entre eles
Mapa com rotas aéreas
maneira mais rápida de x para y
maneira mais barata de x para y
interconexões (rotas aéreas) entre
objetos (cidades)
Sequenciar tarefas (job scheduling)
objetos são tarefas a serem executadas
interconexões indicam seqüência das tarefas
CAP-223
Grafos (cont.)
História
Euler (1736) - pontes de Königsberg
Baseado na disposição das pontes, mostrou
que era impossível percorrer por todas
passando somente uma vez
CAP-223
Grafos (cont.)
Kirchoff (1847) - estudo das árvores para problemas
de circuitos elétricos
Hamilton (1859) - problemas de caminho
Jordan (1869) - procura formalizar teoria de árvores
Século XX - desenvolveu rapidamente
Ford e Fulkerson (1962) - aplicação na teoria de
fluxos de rede
Apesar das tendências em considerar o estudo de
fluxo em rede, muitos outros problemas podem ser
resolvidos através da teoria dos grafos
CAP-223
Grafos (cont.)
Grafo é um objeto matemático que
consegue modelar tais situações
Grafo
Vértices
Objetos com nome
e outras propriedades
Arestas
Conexão entre dois
vértices
CAP-223
Grafos (cont.)
Matematicamente, um grafo G = (V, E)
V é um conjunto de vértices
E é um conjunto de arestas (edges)
onde cada aresta é um par de vértices
Exemplo: (v, w)
Um grafo é representado graficamente
usando pequenos círculos para vértices e
retas ou curvas para arestas
a

b


c

e
d

f
CAP-223
Grafos (cont.)
a

b


c

e
d

f
V = a, b, c, d, e, f
E = (a, b), (b, c), (b, e), (c, e), (c, d), (d, f)
(a, b) é uma aresta entre vértice a e vértice b
Arestas do tipo (a, a) não são permitidas
A cardinalidade ou ORDEM é igual à quantidade de
seus elementos.C(V) = 6
Um grafo pode ser direcionado ou não direcionado
Um grafo é dito direcionado, ou também chamado de digrafo,
quando o sentido das ligações entre os vértices é importante
CAP-223
Grafos (cont.)
A
B
C
D
F
E
G
Caminho de vértice x a
vértice y é uma lista de
vértices na qual sucessivos
vértices estão conectados
por arestas no grafo
{(B,A), (A,F), (F,E), (E,G)}
Grafo é conectado se  um caminho de cada
vértice para qualquer outro vértice
Caminho simples é um caminho no qual nenhum
vértice é repetido (B - A - F - E - G)
Ciclo é um caminho simples com exceção de que o primeiro e o
último vértices são os mesmos (A - F - E - G - A)
Circuito é um ciclo onde pode haver repetição de
vértices no caminho (A - C - A - G - E - D - F - A)
CAP-223
Grafos (cont.)
Adjacência de dois vértices v e w ocorre quando 
uma aresta (v, w) entre v e w
Vértices Maria e Pedro
são adjacentes
Esta aresta é dita incidente
a ambos os vértices
Grafo direcionado
Adjacência Sucessor - w é sucessor de
v se aresta sai de v e chega em w
Exemplo: Emerson e Antonio são
sucessores de Alfredo
Adjacência Antecessor - w é antecessor
de v se aresta sai de w e chega em v
Exemplo: Alfredo e Cecília são
antecessores de AntonioCAP-223
Grafos (cont.)
Grau de um vértice está relacionado com a
incidência das arestas
Grau (Pedro) = 3
Grau (Maria) = 2
Grau de Emissão/Recepção
Grau Emissão (Alfredo) = 2
Grau Emissão (Cecília) = 1
Grau Emissão (Renata) = 0
Grau Recepção (Antonio) = 2
Grau Recepção (Renata) = 1
Grau Recepção (Alfredo) = 0
CAP-223
Grafos (cont.)
Vértice v é fonte se
Grau Recepção (v) = 0
Exemplo: Isadora, Alfredo e Cecília
Vértice v é sumidouro se
Grau Emissão (v) = 0
Exemplo: Emerson e Renata
Um grafo é regular se todos os seus vértices tem
o mesmo grau
Grafo regular-3
Todos os seus vértices
tem grau = 3
CAP-223
Grafos (cont.)
Um subgrafo G’ = (V’, E’) de um grafo G = (V, E)
é um grafo tal que V’  V e E’  E.
O subgrafo é sempre obtido pela supressão de pelo
menos um vértice e suas respectivas arestas
incidentes
a
b
a
G’
G
c
d
c
b
G’ c 
d
CAP-223
Grafos (cont.)
Um subgrafo G1 (V1, E1) de um grafo
G (V, E) é um subgrafo gerador (de
G (V, E) se V = V1
3
3
4
2
5
1
6
4
2
5
1
6
CAP-223
Grafos (cont.)
Quando o subgrafo gerador é uma árvore
ela é chamada de árvore geradora (spanning
tree) [remover arestas até eliminar os ciclos,
mas mantendo a conexidade] 3
3
4
2
5
1
6
4
2
5
1
6
CAP-223
Grafos (cont.)
Grafo G (V, E) é conexo quando existe
caminho entre cada par de vértices de G.
Caso contrário é desconexo.
CAP-223
Grafos (cont.)
G (V, E) é um grafo conexo
Cada aresta e = (v,w) possui um peso d(e)
Peso de uma árvore geradora T (V, ET) é
a soma dos pesos das arestas de G que
formam T.
Árvore geradora máxima (Maximum
Spanning Tree)
Árvore geradora mínima (Minimum
Spanning Tree)
CAP-223
Grafos (cont.)
Grafo parcial é um grafo onde os vértices
são iguais mas as arestas não são.
CAP-223
Grafos (cont.)
Grafo complementar G de G possui a mesma
ordem (cardinalidade) de G mas as arestas não
existentes em G
G
G
CAP-223
Grafos - Aplicações
Verificação de existência de funções inúteis
 main
 p

f

g
h
m
k
n
CAP-223
Grafos - Aplicações (cont.)
Problema do caixeiro viajante
•Área de venda de um caixeiro viajante
com várias cidades
•Muitas conectadas (aos pares) por rodovias
•Necessidade de visitar cada cidade
Como estabelecer uma viagem circular
(volta ao ponto de partida) de tal forma
que cada cidade é visitada somente uma vez?
CAP-223
Grafos - Aplicações (cont.)
Problema da Coleta de Correspondência
•ECT mantém vários pontos de coleta
•O motorista tem que coletar passando
por todos os postos
Como modelar o problema?
Como encontrar a melhor rota?
CAP-223
Grafos - Aplicações (cont.)
Problema do caminho do custo mínimo
Transporte de carga - selecionar caminho de
menor custo entre quaisquer duas cidades
CAP-223
Grafos - Aplicações (cont.)
Problema dos dissidentes políticos
Prisioneiros divididos em celas. Para escapar
precisa explodir os portões.
Destruir o menor número de portões
e garantindo que todos escapem.
Quantos portões devem ser explodidos?
CAP-223
Grafos - Aplicações (cont.)
Problema da RNP (Rede Nacional de Pesquisa)
Rede de computadores que interliga grande número
de instituições (ensino/pesquisa). Em algumas
cidades há um POP (Ponto de Presença)
Havendo mais de uma
rota possível entre dois
POPs
como determinar qual a
rota mais apropriada?
CAP-223
Grafos - Aplicações (cont.)
Problema dos canibais e missionários
3 canibais e 3 missionários precisam atravessar o
rio. Barco com capacidade de 2 pessoas.
Restrição - número de canibais não podem ser
maior que o número de missionários
Como administrar a travessia?
CAP-223
Grafos - Aplicações (cont.)
Problema de rede de computadores
Projeto de redes de computadores onde os
vértices são máquinas e arestas são conexões
entre 2 máquinas juntamente com o custo.
Possibilidade de comunicação
sempre a um custo mínimo
Determinar quais ligações inúteis?
CAP-223
Grafos - Aplicações (cont.)
Problema de 3 casas e 3 serviços
É possível conectar cada serviço a cada
uma das três casas sem haver cruzamento
de tubulações?
CAP-223
Grafos - Aplicações (cont.)
Problema de coloração de mapas
Na atualização de mapa político de um estado,
cada município é colorida com uma cor distinta
de seus vizinhos
Minimizar o número de
cores do mapa
Como colorir o mapa
com o menor número
de cores?
CAP-223