Instituto de Ciências Matemáticas e de Computação
Departamento de Computação e Estatística
SCE183 - Algoritmos e Estruturas de Dados 2
Profs. Resp: Graça Pimentel e Maria Cristina

Matriz de Distâncias

Dado um grafo, definimos uma aresta em função dos vértices que ela conecta. Em alguns problemas, entretanto, torna-se necessário definir uma certa magnitude associada a cada aresta.

Esta magnitude pode ser uma distância geográfica, um tamanho geométrico, um custo de tempo ou dinheiro. Quando esta magnitude deve ser definida para cada aresta é conveniente definirmos a matriz de distâncias.

Uma matriz de distâncias L de um grafo G(V,A) é tal que:

1) cada linha corresponde a um vértice de G
2) cada coluna corresponde a um vértice de G
3) lij é igual a magnitude definida para a aresta (vi,vj). Tal valor será não negativo, a menos que se explicite o contrário.

Por convenção, a distância entre os vértices não adjacentes é assumida ser infinita.
O valor de um caminho é tomado como sendo a soma das magnitudes de todas as arestas incluídas no caminho.

Algoritmo de Dijkstra
É utilizado para localizar o menor caminho dada a matriz de distâncias de um dígrafo.

Dado uma matriz de distâncias de um dígrafo D=(V,A), o caminho mais curto entre o vértice vp e outro vértice vq pode ser obtido por muitos algoritmos alternativos. O algoritmo apresentado por Dijkstra é provavelmente mais eficiente.

Definição:
O conjunto de vértices V é dividido em 2 subconjuntos T e W. O subconjunto T é um vetor que contém vértices com "labels" permanentes associados a eles.

Um label permanente de um vértice é a distância mínima desse vértice ao vértice vp. Essa distância é armazenada no vetor PL. Então, associado ao vetor T, existe o vetor de distâncias PL.

O conjunto W é simplesmente (V-T).
O vetor P contém o vértice adjacente a T, ao longo do caminho mínimo. O conjunto TL define os labels temporários associados com vértices em W. A matriz de distâncias L é a definida anteriormente.

V: conjunto de vértices (T e W)
PL: vetor com labels permanentes associados aos elementos de T
TL: vetor com labels temporários associados aos elementos de W

Passo 1:
Inicialmente:

T={vp}
PL={0}
P={0}
Um label temporário só é associado a cada elemento de W.

Passo 2:

Utilizando a matriz de distâncias, determine os vértices que são adjacentes a quaisquer vértices em T.
Atribua a cada um desses vértices um label temporário igual a distância desse vértice a vp.
label temporário = min em j (label permanente de vj+lij)

Passo 3:

Faça o menor label temporário encontrado ser label permanente. Transfira o vértice vi, correspondente de W para T.

Coloração dos Grafos - Algoritmo
O problema de determinação do número cromático de um grafo é, em geral, muito difícil. Apresenta-se a seguir um algoritmo aproximativo para o problema, que fornece um número de cores próximo do número cromático.

Antes de apresentar o algoritmo, duas ferramentas úteis para a solução de diversos problemas:

a) construção e análise da estrutura de adjacências do grafo. O uso desta análise é tão elementar quanto poderoso, e geralmente consiste em examinar a lista de adjacências de um vértice v pertencente a V, de modo que se possa distinguir se um vértice w pertencente a A(v) satisfaz ou não a uma certa propriedade P.

Por exemplo, existe algum w pertencente a ,b>A(v) que pertence a um certo conjunto C(k) ?

b) ordenação de vértices ou arestas. Esta técnica consiste na ordenação de vértices, ou arestas de G, segundo um certo critério, o qual naturalmente depende da aplicaço em questão.

São bastante comuns, por exemplo, ordenação de vértices segundo seus respectivos graus. Este será o nosso caso no problema da coloração. Outros critérios comuns são as ordenações de listas de adjacências segundo os graus dos vértices que as compõe; as ordenações de arestas de acordo com os pesos a elas atribuidas, etc.

Nos algoritmos de grafos, frequentemente é vantajoso utilizar um processo muito simples, denominado ordenação por caixas. Seja S um conjunto de número inteiros a ser ordenado, e sejam a e b os elementos mínimos e máximos do conjunto, respectivamente.

Defina os subconjuntos, inicialmente vazios, Sa, Sa+1,...Sb, denominados caixas. O algoritmo então verifica todos os elementos do conjunto S. Cada elemento de S de valor j é inserido na caixa j.

dados: Grafo G(V,E)
ordenar V em ordem não crescente (decrescente)
V1...Vn de graus /* n vértices */
C1=C2=...=Cn=0 /* conjunto com vértices de cor j */
colorir V1 com a cor 1 /* incluir V1 em C1 */
para (j=2...n) efetuar

r=min{i/A(vj) intersecção com Ci = 0}
colorir com a cor r (incluir vj com Cr)

Buscas em Grafos

Dado um grafo, deseja-se obter um processo sistemático de como caminhar sobre os vértices e arestas do mesmo.
Se o grafo é uma árvore, esta questão se torna simples. Uma das formas de caminhar na árvore pode ser definida recursivamente.

- se a árvore for vazia, nada a fazer
- caso contrário

visite a raiz da árvore
caminhe pela sub-árvore mais à esquerda da raiz
após pela segunda sub-árvore mais à esquerda da raiz,
após pela terceira...
e assim por diante

Algoritmo: Busca em Profundidade 

dados: G(V,E) conexo
procedimento P(V)
  marcar V
  colocar V na pilha Q
  para w pertencente a A(v) efetuar
    se w e nao marcado entao
      visitar (v,w)
      P(w)
    senao
      se w de Q e v,w nao consecutivos em Q visitar (v,w)
    retirar v de Q

Programa Principal
  desmarcar todos os vertices
  definir uma pilha Q
  escolher uma raiz s, P(s)
Dígrafos
Algoritmos de Busca