intro aos grafos

Prévia do material em texto

1
Clique para editar o estilo do subtítulo mestre
BCM0506: Comunicação e 
Redes
Semana 2
 Introdução aos Grafos
Santo André, Fevereiro de 2017
2
Roteiro da Aula
Motivação: Pontes de Königsberg
Definições, Propriedades e Exemplos
Aplicações de Grafos
Caixeiro viajante
Caminho mais curto
Fluxo máximo
Árvores
Representação de Grafos
Parte das figuras desta aula foram retiradas do site http://www.wikipedia.org
3
As 7 Pontes de 
Königsberg
4
Como começou
Cidade de Königsberg, Prússia
Ficava em ambos os lados 
do Rio Pregel (ou Prególia)
Tinha 2 ilhas centrais, com
as áreas conectadas por 7 pontes 
Foi feita uma proposta a Euler
Como fazer para passar por toda a cidade de modo 
que cada ponte seja cruzada uma única vez?
Exercício: Encontre uma solução para este problema
5
Modelagem do Problema
Euler demonstrou em 1735 que não existe nenhuma 
rota que resolva o problema!
Para tal, o primeiro passo foi simplificar o problema
Caminhos dentro dos pedaços de terra não 
interessavam
O que interessa são apenas as conexões entre os 
pedaços de terra, isto é, as pontes
6
Grafos
Chamamos a estrutura matemática resultante de 
grafo
Os pontos são chamados de vértices
e as conexões de arestas
A forma de um grafo influi apenas
na sua visualização, mas matemati-
camente é irrelevante
Exercício: Tente desenhar o grafo ao lado com outras 
formas. Seja criativo!
7
Solução
Se uma pessoa entra num pedaço de terra e sai dele, 
é preciso que no respectivo grafo cada vértice 
 tenha um número par de arestas
Com exceção dos vértices onde
a caminhada começa e termina
Olhando o grafo ao lado, por que é 
impossível encontrar um caminho que 
cruze cada ponte uma única vez?
Exercício: Tente resolver o problema de dois modos
1) Construindo uma nova ponte
2) Derrubando uma ponte existente
8
Resolução dos Exercícios
 Construindo uma nova ponte Derrubando uma das 
pontes
9
Caminho Euleriano
Euler demonstrou que, para que exista um caminho 
que percorra todos os vértices passando em cada 
aresta uma única vez:
É necessário que ou nenhum ou 2 dos vértices 
tenham um número ímpar de arestas
Carl Hierholzer demonstrou posteriormente que esta 
condição é também suficiente
E assim começou o desenvolvimento da teoria dos 
grafos
10
Algumas Definições,
Propriedades e 
Exemplos
11
Definições
Podemos definir um grafo por
um par ordenado, G = (V,A), onde:
- V é um conjunto de vértices
- A é um conjunto de arestas
No exemplo ao lado, temos:
V = {1, 2, 3, 4, 5, 6}
A = { {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, 
{4,6} }
Este grafo é simples (não possui laços e há no máximo 
uma aresta entre cada par de vértices) e não-
direcionado (as arestas não possuem uma direção 
definida)
12
Propriedades
Pseudo-grafo
(ou multigrafo)
Grafo 
direcionado
Grafo ponderado
Grafo simples
Grafo 
não- direcionado
Grafo 
não- ponderado
13
Outras Propriedades
Existem outras propriedades de grafos:
Ordem: Número de vértices
Tamanho: Número de arestas
Diâmetro: O maior dos menores caminhos entre cada par de 
vértices
 Encontre o menor caminho entre cada par de vértices
 O maior deles representa o diâmetro do grafo
Exercício: Qual a ordem, o tamanho e o diâmetro dos grafos 
abaixo?
14
Outras Propriedades
Conectividade dos vértices: O menor número de 
vértices cuja retirada desconecta o grafo
 Quando removemos um vértice, todas as arestas incidentes 
sobre este vértice precisam ser removidas também
Conectividade das arestas: O menor número de 
arestas cuja retirada desconecta o grafo
Exercício: Qual a conectividade dos vértices e das 
arestas nos grafos abaixo?
15
Jogo de Xadrez 3x3
Grafos podem ser utilizados para
representar diversos problemas:
Em um tabuleiro 3x3, você deseja
mapear todos os movimentos que
podem ser realizados por um bispo
que se move nas casas brancas
O grafo à direita representa
os movimentos deste bispo
Exercício: Desenhe um grafo
que represente todos os 
movimentos da torre
16
Cubo e grafos planares
Grafos podem ser utilizados para
representar objetos, como cubos
Um grafo planar é aquele que pode
ser desenhado em um plano sem que
nenhuma aresta se cruze
Exercício 1: É possível transformar o grafo do 
cubo em um grafo planar? Se sim, redesenhe o 
grafo
Exercício 2: E no caso do grafo que representa 
todos os movimentos do bispo?
Exercício 3: E para os movimentos da torre?
17
Aplicação I:
Otimização
18
Alguns Problemas de 
Otimização
Uma empresa que realiza entregas na Grande São 
Paulo possui um centro de distribuição e um 
caminhão
Qual rota o caminhão deve percorrer de modo a 
realizar todas as entregas com a menor 
quilometragem?
Você deseja implementar em um programa de GPS 
uma funcionalidade de cálculo da melhor rota entre 
dois pontos, de modo a minimizar o tempo de 
viagem 
Como calcular a rota com o menor tempo?
Você está planejando uma rede de galerias 
subterrâneas para captação de águas da chuva, 
evitando alagamentos
Como calcular o fluxo máximo de água que a rede 
de galerias é capaz de escoar?
19
1) Caixeiro Viajante
Um problema clássico é o do 
caixeiro viajante
Imagine um caixeiro viajante 
que deseja encontrar o caminho 
mais curto que passe por todas 
as cidades de seu país
No exemplo ao lado, vemos o 
caminho mais curto que passa 
por diversas cidades da 
Alemanha
20
Modelagem por grafos
Uma maneira de resolver o problema é realizando 
sua modelagem por grafo ponderado
Cada cidade é representada por um nó
e cada estrada por uma aresta, com
peso igual ao comprimento da estrada
Mas podemos também minimizar:
(1) Tempo gasto na viagem
(2) Custo total da viagem
Exercício 1: Qual o caminho mais curto no grafo 
acima?
Exercício 2: Como você alteraria o grafo que 
representa o problema de modo a minimizar os 
fatores (1) e (2)?
21
Entrega de Encomendas
Voltando ao nosso problema inicial:
Uma empresa que realiza entregas na Grande São 
Paulo possui um centro de distribuição e um 
caminhão
Qual rota o caminhão deve percorrer de modo a 
realizar todas as entregas com a menor 
quilometragem?
Exercício: Como você 
modelaria este problema
utilizando a abordagem de 
grafos? Em particular, 
como você definiria os
nós e as arestas do grafo?
22
Solução do Caixeiro 
Viajante
O número de rotas possíveis envolvendo n cidades é 
R(n)=(n-1)!, um número que cresce muito rapidamente 
 (se n = 4, as rotas possíveis entre as cidades A, B, C e D 
seriam: ABCDA, ABDCA, ACBDA, ACDBA, ADBCA e ADCBA, isto é, 
3x2x1 = 6 = 3! = (n-1)! )
Os algoritmos exatos mais rápidos requerem um tempo 
que cresce exponencialmente com o número de cidades. 
Mas existem aproximações muito mais rápidas :-)
Tabela retirada de http://www.mat.ufrgs.br/~portosil/caixeiro.html
- Considere um computador 
que realiza 1 bilhão de somas 
por segundo
- Se o número de cidades for 
pequeno, digamos, n = 5, 
então este computador 
consegue calcular 250 
milhões de rotas por segundo
- Na medida que n cresce, 
mais somas são necessárias 
para cada rota, e menos rotas 
por segundo são calculadas
23
2) Menor Distância
Suponha que você deseje implementar em um 
programa de GPS uma funcionalidade de cálculo da 
melhor rota entre dois pontos, de modo a minimizar o 
tempo de viagem 
Como calcular a rota com o menor tempo?
Exercício: Modele o problema
utilizando grafos e pense em
como você faria para 
encontrar a menor distância 
no grafo
24
Modelagem por grafos
Você pode modelar o problema atribuindo um nó a 
cada cruzamento e uma aresta a cada trecho de rua
Cada aresta deve receber um peso, que pode ser 
o tempo para 
percorrê-lo
ou seu
comprimento 
Desenhe um grafo que
represente as ruas da
figura ao lado
25
Modelagem por grafos
A partir do modelo da cidade, seu programa pode 
calcular a melhor rota entre 2 pontos utilizando 
algoritmos bem conhecidos para encontrar a menor 
distância entre 2 pontos
Ao contrário do problema do caixeiro viajante, 
existem algoritmosque encontram a distância entre 
2 pontos de modo eficiente, isto é, polinomial com 
relação ao número de nós e arestas do grafo
Note que sem fazer uma modelagem do problema, 
não seria possível escrever o programa que realiza a 
tarefa
26
3) Fluxo Máximo
Você está planejando uma rede de galerias 
subterrâneas para captação de águas da chuva, 
evitando alagamentos
Como calcular o fluxo máximo de água que a rede 
de galerias é capaz de escoar?
O gráfico ao lado representa 8
galerias pluviais e a direção
de fluxo da água
Exercício: Qual o fluxo
máximo de água entre os
pontos s e t?
27
Problema das Tubulações
O resultado é 5 e a solução está na figura abaixo
Nem todas as tubulações estão
carregando sua capacidade
máxima de água
Agora suponha que a vazão
das tubulações não está sendo
suficiente. Um engenheiro decide
construir uma tubulação de p para t
com uma vazão 3
1) Em quanto a vazão do sistema irá aumentar?
2) Dada esta nova tubulação, que tubulação 
você alteraria para aumentar a vazão do sistema 
para 8?
28
Cenário mais realista
O problema dos alagamentos e do escoamento de 
águas é um pouco mais complicado
Em cada nó há uma quantidade a mais
de água sendo gerada devido à chuva
Se as tubulações de água saindo
de um ponto não derem conta
de escoar a chuva naquele
ponto e a água que chega de outras 
tubulações, haverá alagamento
Considerando que os números em vermelho são a chuva em 
um dado ponto. Esse sistema é capaz de levar toda a água 
para t ou haverá pontos de alagamento?
29
Outras Aplicações
 O problema do fluxo máximo tem diversas outras 
aplicações. Pense em como você modelaria
1) A capacidade de uma rede de transmissão de 
dados
2) A capacidade de tráfego de carros em um 
conjunto de ruas, levando em conta os semáforos
30
Aplicação II:
Organização de Dados
em Computadores
31
Árvores
Árvores são um tipo de grafo muito utilizado na 
computação para organizar os dados de um 
programa
São definidos como grafos acíclicos e conectados
Os grafos abaixo são exemplos de árvores:
32
Estrutura de Dados
Dados computacionais são armazenados nos nós da 
árvore
No exemplo ao lado, cada nó armazena 
um número, mas outros itens, como 
textos, imagens e arquivos também 
poderiam ser armazenados
Mas qual a vantagem de armazenar
dados em árvores?
Para dados hierárquicos, como sistemas de 
arquivos, esta é a organização natural
Para a manutenção de um conjunto ordenados de 
dados é também eficiente
33
Armazenamento de Dados
Muitas vezes precisamos manter um conjunto 
ordenado de dados no computador
Principal vantagem é que a busca é muito mais 
eficiente
Imagine você realizando a busca por:
Um nome em uma lista telefônica no qual os 
nomes estão fora de ordem
Por uma determinada casa em uma rua onde os 
números da casa foram definidos de modo 
arbitrário
34
Árvore com Dados 
Ordenados
A árvore abaixo mantém uma lista de números 
organizados de modo ordenado
Exercício: Tente descobrir qual a regra
utilizada para que os nós da árvore 
se mantenham ordenados
Árvore Binária de Busca
35
Por que a busca é 
eficiente?
O computador consegue analisar um nó de cada 
vez e sempre começa a busca pelo nó raiz
Suponha que desejemos obter o conteúdo
do nó denominado pelo número 14: 
Árvore não ordenada: necessário
verificar nó por nó
Árvore ordenada: basta
verificar alguns nós
Se a busca for por um número
não presente, como o 18, a
vantagem da ordenação é ainda maior
36
Aplicações do 
armazenamento
Podemos utilizá-las sempre que quisermos 
armazenar um conjunto de dados de modo 
ordenado
Obs: Árvores nem sempre são a estrutura de 
dados mais eficiente em computação, mas este 
é um tópico para outras disciplinas
Exercício: para cada um dos exemplos abaixo, 
pense em dois critérios de ordenação a utilizar
Nomes de clientes de uma empresa
Lista de produtos em estoque
Lista de voos em um aeroporto
37
Sistemas de Arquivos
Sistemas operacionais modernos, como Windows e 
Linux, possuem sistemas de arquivos
Possuem uma organização hierárquica, com diretórios 
(pastas) que podem conter arquivos e outros 
diretórios
38
Sistemas de Arquivos
Normalmente executamos nos sistemas de arquivos as 
operações de busca, inserção e remoção de entradas
Estas operações são eficientes em árvores, como podemos ver 
no exemplo abaixo
39
Sistemas de Arquivos
Suponha agora que desejamos transferir um diretório, 
contendo toda uma subárvore, para outra localização
Como podemos ver, este processo é bastante simples 
e rápido :-)
40
Outras Aplicações
41
Redes 
Metabólicas
Nossas células 
funcionam 
através da 
interação entre 
diversas 
moléculas, como 
enzimas, 
proteínas e ácidos 
nucleicos
A figura ao lado 
mostra parte de 
uma rede 
metabólica
42
Redes Metabólicas
Podemos modelar redes metabólicas por grafos, onde 
os nós correspondem às moléculas e as arestas às 
interações
Estudar estas redes é importante pois:
Permite entender o funcionamento dos seres vivos
Permite descobrir as causas e o tratamento para 
doenças, como câncer e diabetes
Hoje existe um grande números de bancos de dados 
contendo informações sobre genes, proteínas, enzimas 
e suas redes metabólicas
Ex:KEGG: Kyoto Encyclopedia of Genes and Genomes
http://www.genome.jp/kegg/kegg.html
43
Internet
44
Internet
Grafos são utilizados para modelar diversas situações:
- Canais de comunicação entre computadores de 
usuários, roteadores e servidores web
- Estrutura lógica das páginas da Internet, com as 
relações entre os sítios da Internet através de 
hyperlinks
- Hierarquia de servidores no caso de serviços, como o de 
descoberta de endereços IP de servidores a partir de 
seus nomes (ex: www.ufabc.edu.br)
- Organização das páginas de um sítio da Internet
45
Representação de 
Grafos
46
Algoritmos de Grafos
Algoritmos envolvendo grafos são comuns em 
computadores, pois estes permitem a resolução de 
importantes problemas
Caixeiro viajante
Menor distância entre 2 pontos
Fluxo máximo
Organização de dados em computadores
47
Representação de Grafos
Mas como representar grafos em computadores?
As duas maneiras mais utilizadas são:
Lista de adjacência
Matriz de adjacência
48
Lista de Adjacência
Representamos um grafo por
um conjunto de listas, uma por nó X
Cada lista contém todos os 
nós com os quais o nó X se conecta
Na figura ao lado, vemos a
representação de um grafo
Notem que cada aresta
é representada 2 vezes,
uma para cada nó que ela
conecta
49
Matriz de Adjacência
O grafo é representado por uma matriz,
na qual cada elemento (x,y) recebe o valor
1 se houver uma conexão entre os nós
x e y, e 0 caso contrário
Na figura ao lado, vemos a representação 
de um grafo com a matriz de adjacência
Notem que:
Para o grafo não direcionado, 
 a Matriz de Adjacência é simétrica
Se houver poucas arestas, a matriz
será esparsa
50
Representação de Grafos
Podemos também representar grafos direcionados e 
que contenham laços, como abaixo:
Neste caso, as representações contêm a aresta 
apenas em uma direção, como a aresta de 3 para 5
Para o grafo direcionado, basta 1 bit para 
representar cada aresta
51
Exercícios
52
Tarefa
 
Considere as 10 cidades no mapa do estado de São 
Paulo (arquivo anexo). Nele há um grafo que 
representa suas conexões por estradas.
Atribua pesos às arestas utilizando um critério 
desejado (tempo estimado de viagem, distância, 
etc.)
Finalmente, determine:
a) Qual é o diâmetro do grafo, isto é, a maior das 
menores distâncias entre cada par de cidades? 
Obs: considere os pesos de cada aresta
b) Qual a conectividade dos vértices e das arestas?
53
Exercício 2
Crie a matriz de adjacência e a lista de adjacência 
para os 2 grafos abaixo:
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53