CAP-223

GrafosMuitos problemas formulados em objetos econexões entre eles

Mapa com rotas aéreasmaneira mais rápida de x para ymaneira mais barata de x para y

interconexões (rotas aéreas) entreobjetos (cidades)

Sequenciar tarefas (job scheduling)objetos são tarefas a serem executadasinterconexões indicam seqüência das tarefas

CAP-223

Grafos (cont.)História

Euler (1736) - pontes de Königsberg

Baseado na disposição das pontes, mostrouque era impossível percorrer por todaspassando somente uma vez

CAP-223

Grafos (cont.)Kirchoff (1847) - estudo das árvores para problemas de circuitos elétricosHamilton (1859) - problemas de caminhoJordan (1869) - procura formalizar teoria de árvoresSéculo XX - desenvolveu rapidamenteFord e Fulkerson (1962) - aplicação na teoria de fluxos de rede

Apesar das tendências em considerar o estudo defluxo em rede, muitos outros problemas podem serresolvidos através da teoria dos grafos

CAP-223

Grafos (cont.)

Grafo é um objeto matemático queconsegue modelar tais situações

Grafo

Vértices Arestas

Objetos com nomee outras propriedades

Conexão entre doisvértices

CAP-223

Grafos (cont.)Matematicamente, um grafo G = (V, E)V é um conjunto de vérticesE é um conjunto de arestas (edges)onde cada aresta é um par de vérticesExemplo: (v, w)Um grafo é representado graficamenteusando pequenos círculos para vértices eretas ou curvas para arestas a

b c d

e f

CAP-223

V = a, b, c, d, e, fE = (a, b), (b, c), (b, e), (c, e), (c, d), (d, f)(a, b) é uma aresta entre vértice a e vértice bArestas do tipo (a, a) não são permitidasA cardinalidade ou ORDEMORDEM é igual à quantidade deseus elementos.C(V) = 6Um grafo pode ser direcionadodirecionado ou não direcionadonão direcionadoUm grafo é dito direcionado, ou também chamado de digrafodigrafo, quando o sentido das ligações entre os vértices é importante

a

b c d

e f

Grafos (cont.)

CAP-223

Grafos (cont.)A

F

B C G

D

E

Caminho de vértice x aCaminho de vértice x avértice yvértice y é uma lista devértices na qual sucessivosvértices estão conectadospor arestas no grafo

{(B,A), (A,F), (F,E), (E,G)}Grafo é conectadoconectado se um caminho de cadavértice para qualquer outro vérticeCaminho simplesCaminho simples é um caminho no qual nenhumvértice é repetido (B - A - F - E - G)CicloCiclo é um caminho simples com exceção de que o primeiro e oúltimo vértices são os mesmos (A - F - E - G - A)

CircuitoCircuito é um ciclo onde pode haver repetição devé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 Pedrosão adjacentesEsta aresta é dita incidentea ambos os vértices

Grafo direcionado Adjacência Sucessor - w é sucessor dev se aresta sai de v e chega em wExemplo: Emerson e Antonio são sucessores de AlfredoAdjacência Antecessor - w é antecessorde v se aresta sai de w e chega em vExemplo: Alfredo e Cecília são antecessores de Antonio

CAP-223

Grafos (cont.)Grau de um vértice está relacionado com aincidência das arestas

Grau (Pedro) = 3Grau (Maria) = 2

Grau de Emissão/Recepção

Grau Emissão (Alfredo) = 2Grau Emissão (Cecília) = 1Grau Emissão (Renata) = 0Grau Recepção (Antonio) = 2Grau Recepção (Renata) = 1Grau Recepção (Alfredo) = 0

CAP-223

Grafos (cont.)Vértice v é fontefonte seGrau Recepção (v) = 0Exemplo: Isadora, Alfredo e Cecília

Vértice v é sumidourosumidouro seGrau Emissão (v) = 0Exemplo: Emerson e Renata

Um grafo é regularregular se todos os seus vértices temo mesmo grau

Grafo regular-3Todos os seus vérticestem grau = 3

CAP-223

Grafos (cont.)Um subgrafosubgrafo 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 pelomenos um vértice e suas respectivas arestasincidentes

a b a b G G’ G’ c d c d c

CAP-223

Grafos (cont.)Um subgrafo G1 (V1, E1) de um grafoG (V, E) é um subgrafo geradorsubgrafo gerador (deG (V, E) se V = V1

3

2

1

6

5

4

3

2

1

6

5

4

CAP-223

Grafos (cont.)Quando o subgrafo gerador é uma árvoreela é chamada de árvore geradoraárvore geradora (spanningtree) [remover arestas até eliminar os ciclos,mas mantendo a conexidade]

3

2

1

6

5

4

3

2

1

6

5

4

CAP-223

Grafos (cont.)

Grafo G (V, E) é conexoconexo quando existecaminho entre cada par de vértices de G.

Caso contrário é desconexodesconexo.

CAP-223

Grafos (cont.)G (V, E) é um grafo conexo

Cada aresta e = (v,w) possui um peso d(e)

PesoPeso de uma árvore geradora T (V, ET) éa soma dos pesos das arestas de G queformam T.

Árvore geradora máximaÁrvore geradora máxima (MaximumSpanning Tree)Árvore geradora mínimaÁrvore geradora mínima (MinimumSpanning Tree)

CAP-223

Grafos (cont.)Grafo parcialparcial é um grafo onde os vérticessão iguais mas as arestas não são.

CAP-223

Grafos (cont.)Grafo complementarcomplementar de G possui a mesmaordem (cardinalidade) de G mas as arestas nãoexistentes em G

G

G G

CAP-223

main

p f k m n

g h

Grafos - Aplicações

Verificação de existência de funções inúteis

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 formaque 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 demenor custo entre quaisquer duas cidades

CAP-223

Grafos - Aplicações (cont.)Problema dos dissidentes políticos

Prisioneiros divididos em celas. Para escaparprecisa explodir os portões.

Destruir o menor número de portõese 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úmerode instituições (ensino/pesquisa). Em algumascidades há um POP (Ponto de Presença)

Havendo mais de umarota possível entre doisPOPscomo determinar qual arota mais apropriada?

CAP-223

Grafos - Aplicações (cont.)Problema dos canibais e missionários

3 canibais e 3 missionários precisam atravessar orio. Barco com capacidade de 2 pessoas.Restrição - número de canibais não podem sermaior 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 osvértices são máquinas e arestas são conexõesentre 2 máquinas juntamente com o custo.

Possibilidade de comunicaçãosempre 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 cadauma das três casas sem haver cruzamentode 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 distintade seus vizinhos

Minimizar o número decores do mapaComo colorir o mapacom o menor númerode cores?