Análise de Algoritmos | Aulas | Dicionário | Índice

Grafos

Um grafo é um tipo de digrafo em que a relação de adjacência é simétrica (ou seja, v é adjacente a w se e somente se w é adjacente a v). Um grafo é, portanto, nada mais que uma matriz booleana quadrada simétrica. Grafos são um modelo natural para muitos fenômenos e muitos problemas computacionais, como o problema das Árvores geradoras de peso mínimo, por exemplo, de que tratamos em outra página.

Esta página discute certos conceitos para grafos (conexão, componente, circuito, etc.) que não se manifestam em digrafos em geral. Também discute certos tipos de grafos como árvores e florestas.

O que é um grafo

Um grafo (= graph = undirected graph) é um digrafo dotado da seguinte propriedade: para cada arco vw, o par wv também é um arco. Dizemos que o arco wv é antiparalelo ao arco vw. Para enfatizar a simetria, podemos dizer grafo não-dirigido no lugar de grafo.

É conveniente tratar cada par de arcos antiparalelos de um grafo como um novo objeto, que chamamos aresta (= edge). Uma aresta é, portanto, um par não ordenado de vértices, ou seja, um conjunto com exatamente dois vértices. Os dois vértices que constituem uma aresta são as pontas da aresta. Uma aresta com pontas u e v pode ser denotada indiferentemente por uv ou vu.  O conjunto de arestas de um grafo G pode ser denotado por E(G) ou simplesmente E.  Os números de vértices e de arestas de G serão denotados por n(G) e m(G) respectivamente.

Para quaisquer dois vértices u e v de um grafo existe no máximo uma aresta uv. Em outras palavras, nossos grafos não têm arestas paralelas. Nossos grafos também não têm laços (= loops), uma vez que as duas pontas de cada aresta são distintas.

Você pode imaginar que um grafo é uma espécie de mapa rodoviário: os vértices são cidades e as arestas são estradas de mão dupla que interligam as cidades.

Exemplo A:  A figura abaixo mostra duas imagens de um mesmo grafo com vértices 1 .. 5. Do lado direito, cada aresta é representada por um linha. Do lado esquerdo, cada aresta é representada por um par de arcos antiparalelos. (O grafo é o mesmo que aparece no início desta página na forma de matriz. Lá, os vértices são os índices das linhas, e também os índices das colunas.)

         

A matriz de adjacência de um grafo é simétrica (ou seja, M[v, w] = M[w, v] para todo par (v, w) de vértices) e tem diagonal nula (ou seja, M[v, v] = 0 para todo vértice v).

As listas de adjacência de um grafo têm a seguinte propriedade: para cada par (v, w) de vértices, w está em Adj[v] se e somente se v está em Adj[w].

Subgrafos.  Um subgrafo de um grafo é um subdigrafo que juntamente com cada arco vw contém o arco antiparalelo wv. Um sub­grafo é gerador (= spanning) que tem todos os vértices do grafo. Um sub­grafo é induzido se contém todas as arestas do grafo que têm ambas as pontas no subgrafo.

A figura à direita mostra um subgrafo gerador (linha escuras) de um grafo.

Alguns subgrafos simples merecem uma notação especial.  Se vw é uma aresta de um grafo G, denotamos por  G − vw  o subgrafo que se obtém ao remover vw de G.

Se H é um subgrafo de um grafo G e vw é uma aresta de G, denotamos por  H + vw  o subgrafo que se obtém ao acrescentar a aresta vw e os vértices v e w a H.  (Podemos usar essa notação mesmo que um ou ambos os vértices, e até mesmo a aresta, já estejam em H.)

Caminhos e circuitos

O conceito de caminho já foi definido no contexto de digrafos. Mas é necessário fazer uma definição ligeiramente mais restritiva no contexo de grafos.

Um caminho (= path) num grafo é uma sequência de vértices em que cada vértice é adjacente ao anterior e não há arestas repetidas. Mais exatamente, um caminho é uma sequência  (v₀, v₁, … , v_k-1, v_k)  de vértices tal que os pares

v₀v₁,  v₁v₂,  … ,  v_k-1v_k

são arestas distintas duas a duas.  É claro que (v₀, v₁, … , v_k-1, v_k) é um caminho se e somente se (v_k, v_k-1, … , v₁, v₀) é um caminho.  Um caminho é simples se não tem vértices repetidos.

Um circuito (= circuit) é um caminho fechado (ou seja, o primeiro vértice coincide com o último) com três ou mais arestas.

Um circuito é simples se não tem vértices repetidos exceto o último, que é igual ao primeiro.  (Compare com a definição de ciclo num digrafo.)

Grafos conexos

Um grafo é conexo (= connected) se cada um de seus vértices estiver ao alcance de cada um dos demais.  Em outras palavras, um grafo é conexo se, para cada par (v, w) de seus vértices, existe um caminho de v para w.

Um grafo é desconexo se não for conexo. Para provar que um dado grafo G é desconexo, basta exibir um subconjunto não vazio e próprio, digamos X, de V(G) tal que nenhuma aresta tem uma ponta em X e outra no complemento de X.  Dizemos que um tal conjunto X é isolado.

Componentes de grafos

Uma componente de um grafo G é qualquer sub­grafo conexo maximal de G.  Em outras palavras, uma componente de G é o sub­grafo induzido pelo conjunto de todos os vértices que estão ao alcance de um dado vértice.

É claro que cada vértice de um grafo pertence a uma e uma só componente. Portanto, as componentes de um grafo determinam uma partição do conjunto de vértices do grafo.

Árvores e florestas e árvores

Uma árvore (= tree = free tree) é um grafo conexo, digamos T, dotado da seguinte propriedade: para cada aresta a, o grafo T − a não é conexo. Portanto, uma árvore é um grafo minimamente conexo.

Segue da definição que um grafo é uma árvore se e somente se, para quaisquer dois vértices r e s do grafo, existe um único caminho com origem r e término s. (Ademais, esse caminho é simples.)

Uma floresta (= forest = unrooted forest) é um grafo cada uma de cujas componentes é uma árvore.

Um grafo é uma floresta se e somente se, para quaisquer dois vértices distintos r e s do grafo, existe no máximo um caminho com origem r e término s.

Segue daí que um grafo é um floresta se e somente se não tem circuitos.