Algoritmo Guloso
característica: simplicidade
Solução de natureza simples

Problema Geral:
Dado um conjunto S, deseja-se determinar um subconjunto S' contido em S tal que:

1. S' satisfaz uma dada propriedade P
2. S' é máximo (ou mínimo) em relação a algum critério dado alfa.

1. S'i-1 união ao conjunto S satisfaz P e
2. s é tal que S'i-1 união a S é maior (ou menor) ou igual, segundo alfa, do que Si-1 união r que satisfaz P, para todo r pertencente a S-S'i-1.

"A cada passo i, determina-se o elemento s pertencente a S que, adicionado a S'i-1, maximiza (ou minimiza) alfa e, além disso, satisfaz P.

Há ocasiões em que o emprego dessa técnica não conduz ao resultado exato do problema. O processo garante que o subconjunto obtido satisfaz P, mas há aplicações em que não se pode garantir a maximalidade (minimalidade) de S' usando essa técnica.

Um problema que pode ser resolvido utilizando-se essa técnica é o seguinte:

Árvore Geradora Máxima

O problema é obter-se a árvore geradora máxima, dado um grafo. Aplicando-se a técnica do algoritmo guloso, temos:

Deseja-se obter um subconjunto Et contido em E tal que:

i)(V,Et) seja uma árvore (conexo, sem ciclos)
ii)Somatório de d(v,w) seja máxima (v,w) pertence a Et

Algoritmo guloso:

definir inicialmente Et={}
a cada passo escolher uma aresta (v,w) ainda não considerado, tal que:

• a inclusão da aresta a Et não produz ciclos, e
• o peso total de Et união {(u,v)} entre todas as arestas que satisfazem (i)

Após essa verificação incorporar a aresta a Et e repetir o processo até que todas as arestas tenham sido consideradas.

Seja determinar a árvore geradora com maior peso do grafo abaixo:

Utilizando os seguintes resultados:

seja G(V,E) um grafo conexo, T(V,Et) a árvore geradora obtida pela aplicação do algoritmo guloso. Então T possui peso máximo.

Algoritmo: Árvore Geradora Máxima

Dados: G(V,E) conexo, V={1....n}
definir conjuntos Sj={vj},i<=j<=n e Et={}
seja e1,...em as arestas de G, ordenadas segundo pesos não crescentes.
para j=1...m efetuar:
  seja v,w o par de vértices extremos de e
  se v, w pertencem respectivamente a Sp, Sq disjuntos, então:
    Sp=Sq união {Sq}
    eliminar Sq
    Et:=Et união {ej}
fim

Técnica: Alteração Estrutural
Seja G(V,E) um grafo. A técnica consiste em aplicar algum tipo de operação em G, de modo a transformá-lo em outro grafo G'(V',E').

Supondo que se deseja resolver um problema P, no grafo G. Seja P' um problema relacionado a P e tal que se possa resolver P' em G'. Obviamente, se for possível extrapolar a solução de P de G, a partir se obtido de P' em G', resolve-se o problema inicial desejado.

Transformações Comuns
i) eliminação de vértices ou arestas
transformação simples: problemas de natureza simples
ii) adição de vértices ou arestas
iii) condensação: consiste em transformar certos componentes distintos do grafo, em um único. Esses componentes, em geral são subconjuntos de vértices ou arestas.

Aplicação: Número Cromático
Seja G(V,E) o grafo não direcionado dado. Se G for completo, seu número cromático é igual a n. Caso contrário, existem dois vértices distintos v, w não adjacentes.

A idéia é efetuar duas alterações estruturais diferentes em G utilizando os vértices v e w.

• denota-se alfa v,w(G) o grafo obtido a partir de G, pela adição da aresta (v,w).
• denota-se beta v,w(G) o grafo obtido a partir de G pela condensação dos vértices v e w num único vértice z, eliminando-se as arestas paralelas que porventura tenham se formado.

Exemplo:

---

Teoria dos Grafos
Trabalho Prático