Análise e Técnicas de Algoritmos
Período 2003.1

Grafos e Algoritmos de Grafos

Definições e Propriedades Básicas

Muitos dos problemas estudados na teoria dos grafos podem ser utilizados na prática. Vamos apresentar alguns problemas clássicos da teoria dos grafos e que podem ser resolvidos utilizando algumas das técnicas que já aprendemos no curso.

Inicialmente, vamos introduzir alguns conceitos e a terminologia básica da teoria dos grafos.

Um grafo $G = (V, E)$ consiste de um conjunto de vértices, $V$, e um conjunto de arestas, $E$. Cada aresta é um par não ordenado de elementos distintos de $V$. Se $e$ é uma aresta, ela pode ser representada por um conjunto da forma $e = \{ v, w \}$ ou $vw$ ou $wv$, onde $v, w \in V$. Dois vértices são adjacentes se eles formam uma aresta. Duas arestas são adjacentes se elas têm um vértice em comum. O grau de um vértice $v$, $grau(v)$, é o número de arestas que utilizam $v$ em sua definição.

A seguinte proposição é válida: $\Sigma grau(v) = 2. \vert E \vert, \forall v \in V$.

Considerando o exemplo acima, temos que:

• O conjunto de vértices é $V = \{ a, b, c, d, e \}$.
• O conjunto de arestas é $E = \{ ab, ac, ad, bd, be, bf, cd, ce, de, ef \}$.
• $grau(a) = 3$, $grau(b) = 4$, $grau(c) = 3$, $grau(d) = 4$, $grau(e) = 4$ e $grau(f) = 2$.
• $\Sigma grau(v) = 20$.

De acordo com a nossa definição, não consideramos laços ou múltiplas arestas. Entretanto, em muitas referências a definição de grafos pode contemplar essas situações. É comum também chamar os grafos que apresentam esses elementos de pseudografo ou multigrafo.

Um grafo $G_1$ é dito subgrafo de $G$ se e somente se os conjuntos de vértices e arestas de $G_1$ são, respectivamente, subconjuntos dos conjuntos de vértices e arestas de $G$.

Na figura acima, $G_1$ é um subgrafo de $G$.

Um grafo completo é aquele em que quaisquer dois vértices de $V$ são adjacentes. Um grafo é bipartido se o conjunto de vértices $V$ pode ser dividido em dois conjuntos disjuntos e não vazios $V_1$ e $V_2$, satisfazendo a restrição de que dois vértices de um mesmo conjunto ($V_1$ ou $V_2$) não podem ser adjacentes. Na figura abaixo, $G_1$ é um grafo completo de grau $5$ e $G_2$ é um grafo bipartido.

Um caminho em um grafo é uma seqüência alternada de vértices e arestas que começa e termina com um vértice. Um caminho pode ser descrito por uma seqüência de vértices $w_1, w_2, ..., w_n$, em que $(w_i, w_{i + 1}) \in E, \forall 1 \leq i < n$. O tamanho de um caminho é o número de arcos no caminho que é igual a $n - 1$. Um percurso é um caminho onde todas as arestas são distintas. Um trajeto é um caminho em que todos os vértices são distintos. Se o primeiro vértice de um caminho ou percurso é idêntico ao último vértice, dizemos que o caminho ou percurso é fechado. Um percurso fechado é chamado de circuito. Um circuito onde todos os vértices são distintos (com exceção do primeiro e do último) é chamado de ciclo.

Considerando o grafo acima:

• $abcefcbd$ é um caminho que não constitui nem um percurso nem um trajeto.
• $abcefcd$ é um percurso, mas não é um trajeto.
• $abcefcdba$ é um caminho fechado que não forma um circuito.
• $bcefcdb$ é um circuito, mas não é um ciclo.
• $bcdb$ é um ciclo.

Um circuito Euleriano é aquele que contém todos os vértices e arestas de um grafo. S um grafo possui um cirduito Euleriano ele é chamado de Grafo Euleriano.

Um grafo é conectado se e somente se existir um caminho entre quaisquer dois vértices.

Teorema: Um grafo (com pelo menos dois vértices) é Euleriano se e somente se ele é conectado e todo vértice tem grau par.

O problema das pontes de Königsberg (ver figura abaixo) apresenta solução?

Um ciclo Hamiltoniano é aquele que contém cada um dos vértices do grafo. Se um grafo possui um ciclo Hamiltoniano ele é dito grafo Hamiltoniano.

Dígrafos ou grafos dirigidos são aqeules grafos em que cada aresta tem uma direção. Neste caso as arestas são chamadas de arcos e são definidas como um par ordenado de vértices distintos. Um vértice $w$ é adjacente a $v$ se e somente se $(v, w) \in E$. Em um grafo não dirigido com aresta $\{ v, w \}$, $w$ é adjacente a $v$ e $v$ é adjacente a $w$.

A figura acima mostra um dígrafo com 4 vértices e 5 arcos.

Um arco pode ter um terceiro componente que corresponde a um peso ou custo. Um grafo cujos arcos possuem este elemento é dito grafo ponderado ou valorado.

Os conceitos de caminho e ciclo podem ser adaptados para dígrafos, respeitando o direcinoamento definido pelos arcos. Um grafo dirigido é acíclico se ele não contém ciclos. Um grafo acíclico dirigido pode ser referenciado como DAG. Um grafo não dirigido é dito ser conectado se existe um caminho entre quaisquer dois vértices. grafo dirigido com essa propriedade é dito fortemente conectado. Se um grafo dirigido não é fortemente conectado e o correspondente grafo não dirigido é conectado, dizemos que o grafo dirigido é fracamente conectado.

Sobre o grafo acima:

• É um DAG.
• Não é fortemente conectado.
• Existe um caminho de $a$ para $d$, mas não de $d$ para $a$.

Árvores

Uma árvore é um grafo não dirigido, conectado e acíclico. De forma equivalente, podemos dizer que uma árvore é um grafo que apresenta exatamente um único caminho entre qualquer par de vértices. Podemos destacar algumas propriedades básicas de árvores:

• Uma árvore com $n$ vértices tem exatamente $n - 1$ arestas.
• Se uma única aresta é adicionada a uma árvore, o grafo resultante contém exatamente um ciclo.
• Se uma única aresta é removida de uma árvore, o grafo resultante não é conectado.

Árvores enraizadas são aquelas onde é possível distinguir um vértice especial denominado de raiz. É comum chamar os vértices de uma árvore enraizada de nós.

É importante lembrar os conceitos de:

• Ancestral e descendente.
• Pai e filhos.
• Folhas e nós internos.
• Grau de um nó.
• Altura e profundidade.
• Árvores binárias e completas.

Aplicações

A teoria dos grafos é uma ferramenta fundamental na área da computação. Existem centenas de problemas computacionais que podem ser resolvidos com o auxílio de grafos. Alguns exemplos clássicos são: reconhecimento de cadeias de RNA, o problema do caixeiro viajante, cliques, problemas de escalonamento, fluxo de atividades, etc.

Um exemplo de uma situação real que pode ser modelada por um grafo é o sistema de aeroportos.

• Cada aeroporto é um vértice.
• Dois vértices são conectados por um arco se existir um vôo sem parada entre os aeroportos representados pelos vértices.
• O arco pode possuir um peso, representando tempo, distância, ou custo do vôo.
• Poderíamos considerar o grafo como sendo um grafo dirigido (os pesos dos arcos poderiam ser diferentes em cada sentido, por exemplo).
• Talvez fosse interessante fazer com que o grafo fosse fortemente conectado. Logo, seria possível voar de um aeroporto para qualquer um outro.

Representação de Grafos

Existem diferentes formas de representar um grafo $G = (V, E)$. Vamos considerar duas delas:

1. Coleção de listas de adjacência.
2. Matriz de adjacência.

A representação com listas de adjacência é mais utilizada porque provê uma forma compacta de representar grafos esparsos, isto é, grafos onde $\vert E\vert$ é bem menor do que $\vert V\vert^2$.

A representação com matriz de adjacência é indicada no caso de grafos densos, onde $\vert E\vert$ é perto de $\vert V\vert^2$.

Listas de Adjacência

A representação com listas de adjacência de um grafo $G = (V, E)$ consiste de um array $Adj$ de $\vert V\vert$ listas, um para cada vértice de $V$. Para cada $u \in V$, a lista de adjacência $Adj[u]$ contém um ponteiro para todos os vértices $v$, onde existe um arco $(u, v) \in E$. Logo, $Adj[u]$ consiste de todos os vértices de $G$ que são adjacentes a $u$. Esses vértices são armazenados em ordem arbitrária.

A figura abaixo mostra um grafo não dirigido e sua representação com listas de adjacência.

Se $G$ é um grafo dirigido, a soma dos tamanhos de todas as listas de adjacências é $\vert E\vert$. A figura abaixo mostra um grafo dirigido e sua representação com listas de adjacência.

Em ambos os casos, grafos dirigidos ou não, a representação com listas de adjacÊncia possui uma propriedade desejável que indica que a quantidade de memória requerida é $O(max(V, E)) = O(V + E)$.

As listas de adjacência também pode ser utilizadas no caso de grafos ponderados e outras variantes de grafos.

A maior desvantagem desse método de representação é a de não possuir uma forma eficiente de dizer se um determinado arco $(u, v)$ está presente no grafo.

Matriz de Adjacência

A representação por matriz de adjacência de um grafo $G = (V, E)$ requer que os vértices sejam arbitrariamente numerados de $1, 2, ..., \vert V\vert$. A matriz de adjacência de um grafo de uma matriz $A = (a_{ij})$, de ordem $\vert V\vert \times \vert V\vert$, onde

$$\mbox{$a_{ij}$} = \left\{ \begin{array}{ll} 1 & \mbox{se $(i... ...\in E$} \\ 0 & \mbox{caso contrário} \end{array} \right.$$

A figura abaixo mostra um grafo não dirigido e sua representação com matriz de adjacência. Esse tipo de representação requer $O(V^2)$ de memória, independentemente do número de arcos do grafo.

Da mesma forma, a matriz de adjacência pode ser usada para representar grafos dirigidos.

Como na representação com listas de adjacência, a matriz de adjacência pode ser usada para representar grafos ponderados. Em vez de usar $1$ para indicar a presença do arco, utiliza-se o peso do arco.

Embora a representação com lista de adjacência seja pelo menos tão eficiente quanto a representação com matriz de adjacência, a simplicidade de uma matriz de adjacência a torna preferível no caso de grafos pequenos. No caso de grafos não ponderados, a representação com matriz de adjacência tem a vantagem de requerer apenas um bit por entrada.

Busca em Grafos

Existem dois tipos principais de pesquisa (caminhamento) em grafos:

1. Busca em amplitude (breadth-first search).
2. Busca em profundidade (Depth-first search).

Busca em Amplitude

A busca em amplitude representa um dos mais simples algoritmos de busca em grafo. Apesar de sua simplicidade, esse método funciona como modelo para vários importantes algoritmos de grafos como, por exemplo, o algoritmode caminho mais curto de Dijkstra e o algoritmo da árvore mínima de cobertura de Prim.

Se um grafo $G = (V, E)$ e um vértice inicial $s$. A busca em amplitude processa os vértices por níveis, começando pelos vértices mais proóximos do vértice inicial $s$ e deixando os vértices mais distantes para depois. Esse tipo de busca é bastante similar ao caminhamento por níveis em árvores.

O algoritmo de busca em amplitude pode ser resumido nos seguintes passos e funciona tanto para grafos dirigidos ou não:

• Distinguir o vértice inicial $s$.
• Sistematicamente explorar os arcos de $G$ para descobrir todo vértice alcançáveis a partir de $s$.
• Computar a distância (menor número de arcos) de $s$ para todos os vértices alcançáveis.
• Produz uma árvore de amplitude cuja raiz é $s$ e contém todos os vértices alcançáveis.
• Para todo vértice $v$ alcançável a partir de $s$, o caminho na árvore de amplitude corresponde ao menor caminho de $s$ para $v$ em $G$.

O algoritmo, portanto, descobre todos os vértices com distância $k$ a partir de $s$ antes de descobrir os vértics com distância $k + 1$.

Para manter controle do processamento dos vértices no algoritmo, é necessário marcar os vértices. Utilizamos um sistema de 3 cores: branca, azul e vermelha.

• Todos os vértices começam com cor branca e podem mudar para cor azul e posteriormente para vermelho.
• Quando um vértice é encontrado pela primeira vez, ele passa a ser colorido.
• É necessário duas cores diferentes do branco para garantir a sistemática da amplitude.
• Se $(u, v) \in E$ e $u$ é vermelho, então o vértice $v$ ou é azul ou vermelho, ou seja, todo vértices adjacente a um vértice vermelho já descoberto.
• Um vértice azul pode ter um vértice adjacente de cor branca.

Como dito anteriormente, a busca em amplitude constroi uma árvore de amplitude, inicialmente contendo apenas a raiz que é o nó de origem. Sempre que um vértice branco $v$ é descoberto a partir de um vértice já descoberto $u$, ele é adicionado à árvore, juntamente com o arco $(u, v)$. O vértice $u$ é o predecessor de $v$ na árvore. Como cada vértice só é descoberto uma única vez, ele possui apenas um predecessor.

O algoritmo BFS abaixo corresponde ao algoritmo de busca por amplitude e assume que o grafo $G = (V, E)$ é representado com listas de adjacência. Para cada vértice no grafo, o algoritmo mantém estruturas auxiliares:

• A variável $cor[u]$ mantém a informação sobre a cor de cada vértice.
• A variável $\pi [u]$ mantém a informação sobre o predecessor de cada vértice. Quando nã existe predecessor $\pi [u] = NIL$.
• $d[u]$ mantém o valor da distância do vértice inicial até $u$.
• Uma fila $Q$ com política FIFO para gerenciar a lista de vértices de cor azul.

Exemplo

O exemplo abaixo mostra a utilização do algoritmo BFS em um grafo não dirigido.

Busca em Profundidade

A busca em profundidade é uma generalização do caminhamento em pré-ordem. Como o próprio nome indica, a idéia principal é buscar verticalmente sempre que possível. Nesta estratégia, sempre que um novo vértice $v$ é descoberto, ele deve ser explorado por completo. Quando não existe mais nenhum vértice a ser explorado, efetua-se um bactrack para o vértice que propiciou a descoberta de $v$.

Alguns detalhes do algoritmo de busca em profundidade:

• Da mesma forma que na busca em amplitude, sempre que um vértice $v$ é descoberto, a busca em profundidade também guarda a informação do vértice predecessor.
• Na busca em profundidade, uma floresta de árvores composta pelos vértices predecessores é formada. Isso porque a busca pode ser repetida a partir de origens múltiplas.
• Além de criar a floresta de árvores, o algoritmo de busca em profundidade associa uma marca de tempo em cada vértice. Cada vértice $v$ tem duas marcas de tempo $d[v]$ e $f[v]$ que indicam, respectivamente, quando $v$ foi primeiramente descoberto (colorido com azul) e quando a lista de adjacência para $v$ foi totalmente examinada (e colorida com vermelho).
• Essas marcas de tempo são utilizadas em alguns algoritmos de grafos e ajudam a verificar o comportamento da busca em profundidade.

Exemplo

O exemplo a seguir, mostra o progresso da execução do algoritmo DFS sobre um grafo dirigido.

O algoritmo de busca em profundidade pode ser facilmente modificado para classificar os tipos de arcos do grafo $G$. Podemos distinguir 4 tipos de arcos:

1. Arcos da árvore: arcos que fazem parte da floresta de árvores.
2. Arcos de retorno: arcos que conectam um vértice a um ancestral em uma árvore de profundidade.
3. Arcos para frente: arcos que não fazem parte da árvore que conectam um vértice a um descendente.
4. Arcos de cruzamento: todos os outros arcos.

Essa classificação pode servir para indicar certos aspectos do grafo. Por exemplo, podemos afirmar que um grafo é acíclico se ele não possuir arcos de retorno.

Ordenação Topológica

A ordenação topológica pode ser vista como uma aplicação da técnica de busca em profundidade, que consiste em ordenar o conjunto de vértices de um grafo acíclico dirigido.

Podemos definir uma ordenação topológica de um grafo acíclico dirigido $G = (V, E)$ como uma ordenação linear de todos os vértices que satisfaz a seguinte condição:

Se $G$ contém um arco $(u, v)$, então $u$ aparece antes de $v$ na ordenação.

O seguinte algoritmo ordena topologicamente um grafo acíclico dirigido.

Esse algoritmo é $O(V + E)$ pois, o algoritmo DFS é $O(V + E)$ e a inserção na lista encadeada é $O(1)$.

Exemplo

Grafos acíclicos dirigidos são usados em muitas aplicações para indicar precedência entre eventos. Por exemplo, a estrutura de pré-requisitos das disciplinas do Curso de Ciência da Computação na UFPB.

A ordenação topológica das disciplinas seria qualquer seqüência de disciplinas que não violasse a estrutura de pré-requisitos.

Para ilustrar a aplicação apresentada, vamos considerar a figura a seguir. Ela apresenta uma estrutura de pré-requisitos entre 9 disciplinas de um determinado curso. O tempo de inicial e final dos vértices, obtidos através do algoritmo de busca em profundidade estão também indicados.

Uma possível solução para a ordenação topológica do grafo está mostrada a seguir.

Árvore de Cobertura Mínima

Considere um mapa modelado por um grafo: os vértices correspondem a cidades e os arcos representam estradas de terra batida entre cidades adjacentes, com os rótulos indicando a respectiva distância. O Governo do Estado planeja asfaltar algumas estradas, tornando possível sair de qualquer cidade para outra em estrada asfaltada. Que estradas deveriam ser asfaltadas, minimizando o total de asfalto a ser gasto? Esse problema na teoria dos grafos é conhecido como o problema de encontrar a árvore de cobertura mínima.

Uma árvore de cobertura de um grafo conectado $G$ é um subgrafo que forma uma árvore e que inclui cada um dos vértices de $G$. Uma árvore de cobertura mínima para um grafo valorado é uma árvore de cobertura em que a soma dos pesos das arestas é mínima.

A figura acima apresenta um grafo e sua árvore de cobertura mínima (em azul).

Uma solução genérica para encontrar a árvore de cobertura mínima utiliza uma estratégia gulosa. Em cada passo da esratégia gulosa, uma nova aresta $(u, v)$ é escolhida para compor a solução $A$. Em cada passo, $A$ contém um subconjunto de alguma árvore de cobertura mínima. A nova aresta escolhida deve respeitar essa propriedade (essa seria a nossa função de viabilidade). Dizemos, portanto, que uma aresta que pode ser incluído no conjunto $A$ é uma aresta segura.

Uma solução genéria seria:

Uma forma de reconhecer uma aresta segura é:

• Definir um corte no grafo, particionando o conjunto de vértices.
• Uma aresta cruza o corte se cada um dos vértices que formam a aresta está em partições diferentes.
• O corte deve respeitar $A$. Isso acontece se nenhuma aresta de $A$ cruza o corte.
• A aresta segura é a aquela de menor peso que cruza o corte.

Vamos mostrar duas formas diferentes de implementar a escolha da aresta segura.

Algoritmo de Kruskal

• Kruskal utiliza conjuntos disjuntos.
• O tempo de execução depende de como conjuntos disjuntos foram implementados.
• Kruskal é $O(E \log E)$

Algoritmo de Prim

• A solução se parece com a solução de Dijkstra para encontrar o menor caminho.
• Utiliza uma fila de prioridade como estrutura auxiliar.
• Prim é $O(E \log V)$.

Menor Caminho de Origem Única

Considere o problema em que um motorista deseja determinar o menor caminho entre Campina Grande e Natal. Com um mapa da Região Nordeste que marca a distância entre as principais cidades, como é possível determinar o menor caminho? Uma possível solução é definir todas as rotas possíveis e selecionar aquela com a menor distância. Na verdade, essa não é uma solução interessante.

Esse problema pode ser resolvido na teoria dos grafos por algoritmos que calculam o menor caminho de origem única. Esses algoritmos podem, de fato, ser utilizados em variações de problemas de cálculo de menor caminho.

Uma forma de representar o menor caminho é utilizar dois valores $d[v]$ e $\pi [v]$ associados a cada um dos vértices $v \in V$. $d[v]$ mantém o valor da menor distância da origem até $v$, enquanto $\pi [v]$ indica o vértice predecessor de $v$ no menor caminho encontrado. As soluções que vamos apresentar utilizam essas duas variáveis. O algoritmo abaixo indica como essas duas variáveis devem ser inicializadas. $s$ é o vértice de origem.

Para encontrar o menor caminho, as variáveis $\pi$ e $d$ vão sendo ajustadas segundo uma estratégia de relaxamento de arestas. O processo de relaxamento consiste em testar se é possível melhorar o menor caminho.

O algoritmo que executa o relaxamento em uma aresta $(u, v)$ é o seguinte:

Algoritmo de Dijkstra

• Resolve o problema de menor caminho de origem única em grafos dirigidos e valorados.
• Arestas não podem ter peso negativo.
• $O(E \log V)$ se todos os vértices são alcançáveis a partir da origem.

Algoritmo de Bellman-Ford

• Resolve o problema de menor caminho de origem única em grafos dirigidos e valorados.
• Arestas podem ter peso negativo.
• Bellman-Ford é $O(V.E)$.