Grafos AGM

GCC111 Projeto e Anlise de Algoritmos

Mayron Csar O. Moreira

Universidade Federal de Lavras

Departamento de Cincia da Computao

[email protected]

16 de maio de 2015

Mayron Csar O. Moreira (UFLA) GCC111 PAA 16 de maio de 2015 1 / 15

Contedo

1

Grafos - rvores Geradoras Mnimas

Introduo

Origens

O primeiro algoritmo a resolver o problema de rvore geradora mnima

(AGM) atribudo a Otakar Boruvka, em 1926;

Contexto: resolver o problema de encontrar uma eciente cobertura

eltrica de Moravia (atual Repblica Checa);

Aplicaes

Transporte areo, transporte terrestre, redes de computadores, redes

eltricas, projeto de circuitos eletrnicos, etc.

Introduo

Dados

Seja G = (V ,E ) um grafo conexo no-orientado, onde V o conjunto devrtices e E o conjunto de arestas. Para cada (u, v) E , temos um pesow(u, v).

Objetivo

Encontrar um subconjunto acclico T E que conecte todos os vrtices ecujo peso total w(T ) =

(u,v)T w(u, v) seja minimizado.

Introduo

Dados

Seja G = (V ,E ) um grafo conexo no-orientado, onde V o conjunto devrtices e E o conjunto de arestas. Para cada (u, v) E , temos um pesow(u, v).

Objetivo

Encontrar um subconjunto acclico T E que conecte todos os vrtices ecujo peso total w(T ) =

(u,v)T w(u, v) seja minimizado.

Algoritmo Genrico

Generic-MTSP()A = while A no formar uma rvore geradora

encontre a aresta (u, v) que seja segura para AA = A {u, v}

return A

Denies

Corte

Consiste em uma partio de G = (V ,E ) dada por (S ,V S). Dizemosque uma aresta (u, v) E cruza o corte (S ,V S) se um dos seus pontosest em S e o outro est em V S .

Denies

Corte

Um corte respeita um conjunto A de arestas se nenhuma aresta em Acruza o corte.

Denies

Aresta Leve

Aresta que cruza o corte com peso mnimo.

Aresta Segura

Aresta que pode ser adiciona a A a m de compor a AGM.

Teorema

Seja G = (V ,E ) um grafo valorado no orientado. Considere A umsubconjunto de E que est includo em alguma AGM para G , (S ,V S)qualquer corte de G que respeita A e (u, v) E uma aresta leve que cruza(S ,V S). Ento, a aresta (u, v) segura para A.

Corolrio

Seja C = (VC ,EC ) uma componente conexa (rvore) na orestaGA = (V ,A). Se (u, v) uma aresta leve que conecta C a alguma outracomponente em GA, ento (u, v) segura para A.

Algoritmo de Kruskal

O conjunto A uma oresta cujos vrtices so todos os vrtices dografo dado;

A aresta segura adicionada a A sempre uma aresta de peso mnimono grafo que conecta duas componentes distintas (lembre-se do

Corolrio);

Ideia: ordenar as arestas de maneira ascendente do valor de cada peso;

Ao nal do algoritmo, temos o conjunto S formando uma AGM.

Corolrio);

MST-Kruskall()A = for cada vrtice v V

Make-Set(v)ordene as arestas de E em ordem ascendente de peso wfor cada aresta (u, v) E, tomada em ordem ascendente de peso

if Find-Set(u) 6= Find-Set(v)A = A {(u, v)}Union(u, v)

return A

Complexidade

O(|E |log |V |), mas depende de como as operaes em conjuntos soimplementadas.

MST-Kruskall()A = for cada vrtice v V

Make-Set(v)ordene as arestas de E em ordem ascendente de peso wfor cada aresta (u, v) E, tomada em ordem ascendente de peso

if Find-Set(u) 6= Find-Set(v)A = A {(u, v)}Union(u, v)

return A

Complexidade

O(|E |log |V |), mas depende de como as operaes em conjuntos soimplementadas.

Algoritmo de Prim

O conjunto A forma uma rvore nica;

A aresta segura adicionada a A sempre uma aresta de peso mnimoque conecta a rvore a um vrtice no presente na rvore (lembre-se

do Teorema);

Ideia: a rvore comea por um vrtice qualquer e cresce at que

conecte todos os vrtices de V ;

Algoritmo de Prim

do Teorema);

Algoritmo de Prim

do Teorema);

Algoritmo de Prim

MST-Prim()for cada v V

u.chave =u.pi = NIL

r .chave = 0Q = Vwhile Q 6=

u = Extract-Min(Q)for cada v Adj [u]

if v Q e w(u, v) < v .chavev .pi = uv .chave = w(u, v)

Complexidade

O(|E |log |V |), mas tambm depende de como as operaes em conjuntosso implementadas.

Algoritmo de Prim

MST-Prim()for cada v V

u.chave =u.pi = NIL

r .chave = 0Q = Vwhile Q 6=

u = Extract-Min(Q)for cada v Adj [u]

if v Q e w(u, v) < v .chavev .pi = uv .chave = w(u, v)

Complexidade

O(|E |log |V |), mas tambm depende de como as operaes em conjuntosso implementadas.

rvore Geradora Mnima

Perguntas

E se todas as arestas tivessem o mesmo peso? Existe uma forma mais

eciente de resolver?

Como projeto um algoritmo para uma AGM de peso mximo?

Grafos - rvores Geradoras Mnimas

Documents

Grafos AGM