Aula01 Palestra Aplicacoes Grafos

Instituto de Computao - UFF

Uma Breve Introduo sobre Aplicaes de Grafos

Fbio Protti

IC/UFF


Grafo

formado por um conjunto de pontos, chamados vrtices...


Grafo

formado por um conjunto de pontos, chamados vrtices...

...conectados por um conjunto de linhas, chamadas arestas.


Grafo


Grafo Definio Informal

Abstrao que permite codificar relacionamentos entre pares de objetos


Grafos Definio Informal


Que objetos?




Ex.: Pessoas, cidades, empresas, pases, pginas web, filmes, etc.

Que objetos?





Que objetos?

Que relacionamentos?





Ex.: Amizade, conectividade, produo, lngua falada, etc.

Que objetos?

Que relacionamentos?



Objetos Vrtices do Grafo




Relacionamentos Arestas do Grafo




Relacionamentos Arestas do Grafo

Exemplos?


Exemplos de Grafos

Transporte Areo:

Objeto: Cidades

Relacionamento: Vo comercial entre duas cidades


Exemplos de Grafos

Transporte Areo:

Objeto: Cidades

Relacionamento: Vo comercial entre duas cidades

Cuiab

SP

BH Rio

Manaus

Vo entre SP e Manaus


Exemplos de Grafos

Atores e Filmes:

Objeto: Atores

Relacionamento: Atores atuaram em um mesmo filme


Exemplos de Grafos

Atores e Filmes:

Objeto: Atores

Relacionamento: Atores atuaram e um mesmo filme

Wagner Moura

Lzaro Ramos

Cludia Abreu

Selton Mello

Dbora Secco

Meu tio matou um cara


Exemplos de Grafos

Web:

Objeto: pginas web

Relacionamento: link de uma pgina para outra


Exemplos de Grafos

Web:

Objeto: pginas web

Relacionamento: link de uma pgina para outra

http://www.ic.uff.br

http://www.uff.br

http://www.ic.uff.br/Docentes/docentes.php

http://www.capes.gov.br

http://www.centrodeartes.uff.br


Definio Formal

G=(V(G), E(G), G)

Conjunto no vazio de vrtices

Conjunto disjunto de V(G), Formado por arestas

Funo que associa cada aresta de G a um par

de vrtices de G


Exemplo

G=(V(G), E(G), G), onde

V(G) ={v1, v2, v3, v4, v5}

E(G)={e1, e2, e3, e4, e5, e6, e7 , e8}

G :

G(e1)= (v1, v2), G(e2)= (v2, v3),

G(e3)= (v3, v3), G(e4)= (v3, v4),

G(e5)= (v2, v4), G(e6)= (v4, v5),

G(e7)= (v2, v5), G(e8)= (v2, v5)


Exemplo


V(G) ={v1, v2, v3, v4, v5}

E(G)={e1, e2, e3, e4, e5, e6, e7 , e8}

G :

G(e1)= (v1, v2), G(e2)= (v2, v3),

G(e3)= (v3, v3), G(e4)= (v3, v4),

G(e5)= (v2, v4), G(e6)= (v4, v5),

G(e7)= (v2, v5), G(e8)= (v2, v5)

v1

v2

v3

v4 v5


Exemplo


V(G) ={v1, v2, v3, v4, v5}

E(G)={e1, e2, e3, e4, e5, e6, e7 , e8}

G :

G(e1)= (v1, v2), G(e2)= (v2, v3),

G(e3)= (v3, v3), G(e4)= (v3, v4),

G(e5)= (v2, v4), G(e6)= (v4, v5),

G(e7)= (v2, v5), G(e8)= (v2, v5)

G

v1

v2

v3

v4 v5


Observaes

Grafos so assim chamados por poderem ser representados graficamente


Observaes


Existe uma nica maneira de desenhar um grafo?


Observaes


Existe uma nica maneira de desenhar um grafo?

NO!!!


Um pouco de Histria

A Teoria dos Grafos teve sua origem com o problema das Pontes de Knigsberg, em 1735.


Um pouco de Histria

A cidade de Knigsberg banhada pelo rio Pregel que, ao atravessar a cidade se ramifica formando uma ilha (Kneiphof) que est ligada parte restante da cidade

por sete pontes. Dizia-se que os habitantes da cidade, nos dias de descanso e sol, tentavam

efetuar um percurso que os obrigasse a passar por todas as pontes, mas apenas uma vez em cada uma. Como as suas tentativas sempre falhavam, muitos deles

acreditavam que no era possvel encontrar tal percurso. Ser que tinham razo?


Um pouco de Histria

possvel andar por toda a cidade de tal modo que cada ponte seja atravessada

exatamente uma vez?


Remodelando o problema



O problema agora consiste em percorrer todas as arestas,

passando por cada uma apenas uma vez, sem

levantar o lpis do papel.



Um caminho completo com as propriedades

descritas acima de no retraar nenhuma

aresta chamado de TRILHA de EULER


O Assassinato de Van Diamond

O bilionrio Van Diamond acaba de ser assassinado. Um conhecido detetive que nas horas vagas um estudioso da Teoria de Grafos foi chamado para investigar o caso.

O mordomo alega ter visto o jardineiro entrar na sala da piscina (lugar onde ocorreu o assassinato) e logo em seguida deixar aquela sala pela mesma porta que havia entrado.

O jardineiro, contudo, afirma que ele no poderia ser a pessoa vista pelo

mordomo, pois ele havia entrado na casa, passado por todas as portas uma nica vez e, em seguida, deixado a casa.

O detetive avaliou a planta da residncia e em poucos minutos declarou

solucionado o caso.


Planta da Casa

Quem poderia ser o assassino indicado pelo detetive? Qual o raciocnio utilizado pelo detetive para apontar o suspeito?


Planta da Casa

Quem poderia ser o assassino indicado pelo detetive? Qual o raciocnio utilizado pelo detetive para apontar o suspeito?

RUA


Planta da Casa

G possui trilha de Euler sse todos seus vrtices possuem grau par.

2 3 2

4

2

5

2

2

4

2


Poder da Abstrao


Formando Pares

s es


Formando Pares

Regra:

s es


Formando Pares

Regra: Casal pode sair junto(formar um par) se existe interesse mtuo

s es


Formando Pares

Problema 1: Dadas as escolhas dos rapazes e moas, possvel formar n casais?


Formando Pares

Problema 1: Dadas as escolhas dos rapazes e moas, possvel formar n casais?

Problema 2: Qual o nmero mximo de pares que podem ser formados?


Formando Pares

Como abstrair o problema usando grafos?

Objeto: Rapazes e Moas

Relacionamento: Interesse mtuo em sair


Alocao de Professores

Regra: Cada professor leciona uma ou mais disciplinas




Problema 1: Dado o que cada professor pode lecionar, possvel que todas as disciplinas sejam oferecidas simultaneamente?




Problema 1: Dado o que cada professor pode lecionar, possvel que todas as disciplinas sejam oferecidas simultaneamente?

Problema 2: Qual o maior nmero de disciplinas que podem ser oferecidas?



Mesma Abstrao

Mesmo Algoritmo


Robustez da Malha Eltrica

Malha eltrica

(distribuio de energia)

Torres e linhas de

transmisso

Problema: Quantas linhas precisam falhar (no mnimo) para termos um apago?

Apago: desconectar parte do sistema


Robustez da Malha Eltrica


Colorindo um Mapa

Mapa de Regies (Estados)

Colorir o mapa:

- regies vizinhas cores diferentes

Problema 1: Colorir o mapa de forma a atender a restrio

Problema 2: Qual o menor no. de cores necessrias?


Colorindo um Mapa

Mapa de Regies (Estados)

Colorir o mapa:

- regies vizinhas cores diferentes

Problema 1: Colorir o mapa de forma a atender restrio

Problema 2: Qual o menor no. de cores necessrias?


Colorindo um Mapa


Alocao de Frequncias

Rede telefonia celular

Estaes base (torre)

Clulas vizinhas no podem

usar mesma frequncia (interferncia)

Problema 1: Como alocar frequncias s clulas?

Problema 2: Qual o menor nmero de frequncias necessrias?


Alocao de Frequncias


Colorao de Grafos


Colorao de Grafos

Exemplo


Colorao de Mapas Amrica do Sul


Colorao de Mapas Amrica do Sul

Qual o nmero mximo de cores necessrias para colorir um mapa?


Grafos Planares

Definio:

Um grafo G dito planar se puder ser representado graficamente no plano de modo que suas arestas no se cruzem.


Grafos Planares

O estudo dos grafos planares originou de dois problemas de recreao envolvendo o grafo completo K5 e o grafo bipartido K3,3.


Grafos Planares


K5


Grafos Planares


K5 K3,3


Grafos Planares

O primeiro problema foi apresentado por A. F. Mobius por volta do ano 1840 como segue:

Era um vez um Rei com 5 filhos. Em seu testamento ele desejou que, aps sua morte, os seus filhos dividissem seu Reino em 5 provncias de forma que o limite de cada provncia tivesse uma linha fronteira comum com cada uma das outras quatro.


Grafos Planares

Regio 1

Regio 4


Regio 2

Grafos Planares

Regio 1

Regio 4


Regio 3

Regio 2

Grafos Planares

Regio 1

Regio 4


R

Regio 3

Regio 2

Grafos Planares

Regio 1

Regio 4


R

R

Regio 3

Regio 2

Grafos Planares

Regio 1

Regio 4


Regio 3

Regio 2

Grafos Planares

Regio 1

Regio 4


Grafos Planares

Problema: possvel desenhar 5 regies mutualmente vizinhas no plano?


Grafos Planares

Depois, o Rei pediu que todos os cinco irmos unissem as capitais de cada uma de suas provncias atravs de estradas e que estas no deveriam se cruzar.


Grafos Planares

Problema: K_5 um grafo planar?


Grafos Planares

A origem do segundo problema desconhecida mas foi primeiramente mencionada por H. Dudeney em 1913 da seguinte forma:

O problema consiste em fornecer gua, gs e eletricidade a 3 casas sem cruzar seus tubos


Grafos Planares


Grafos Planares

Problema: Decidir se o grafo K3,3 planar


Motivao

Por que estudar grafos? Importante ferramenta matemtica com

aplicao em diversas reas do conhecimento

Utilizados na definio e/ou resoluo de problemas

Existem centenas de problemas computacionais que empregam grafos com sucesso.

Documents

Aula01 Palestra Aplicacoes Grafos