Teoria dos Grafos - Parte 2

Prévia do material em texto

TEORIA DOS GRAFOS 
AULA 2 
 
 
 
 
 
 
 
 
 
Prof. Guilherme Augusto Pianezzer 
 
 
 
 
 
 
2 
CONVERSA INICIAL 
Caro(a) leitor(a), em conteúdos anteriores, determinamos o que é um 
grafo, avaliando as suas principais características. Além disso, você começou 
seus primeiros ensaios programando um grafo em Python. Agora, vamos 
investigar os conceitos de conexidade e conectividade, além de elaborar, 
também em Python, um algoritmo conhecido como algoritmo de Malgrange, 
responsável por determinar as componentes conexas de um grafo orientado. 
TEMA 1 – CONEXIDADE E CONECTIVIDADE 
Na etapa anterior, avaliamos que é possível determinar percursos saindo 
de um vértice e chegando a um outro. O que temos é uma lista que indica os 
vértices subsequentes por que precisamos passar até chegar ao vértice final. 
Entretanto, nem sempre é possível estabelecer um percurso entre dois pontos. 
Esse conceito é essencial para os principais algoritmos de determinação de 
caminho mínimo. 
1.1 Conexidade em grafos não orientados 
Vamos considerar os grafos não orientados, como o grafo 𝐺1 da figura a 
seguir. 
Figura 1 – Grafo não-orientado composto de 5 vértices 
 
Nesse exemplo, é evidente que existe um percurso saindo de um vértice 
qualquer e chegando em qualquer outro. Isso fica ainda mais claro quando 
observamos o grafo 𝐺2 da figura a seguir. 
 
 
 
3 
Figura 2 – Grafo não-orientado composto de 7 vértices 
 
Nesse caso, observamos que não há, por exemplo, percurso saindo do 
primeiro vértice e chegando ao sétimo. Utilizando os conceitos da etapa anterior, 
note que o fecho transitivo de 1 não contém 7. Afinal: 
𝑅(1) = {2,3,4} 
𝑅(7) = {5,6} 
A situação indica que o fecho transitivo de 1 contém os vértices atingíveis 
a partir de 1, enquanto o fecho transitivo de 7 contém os vértices atingíveis a 
partir do vértice 7. O que difere o grafo 𝐺1 do grafo 𝐺2 é que o primeiro é conexo 
– portanto, apresenta a propriedade da conexidade. 
Quando o grafo é conexo, como o grafo 𝐺1, podemos ir de um vértice a 
outro transitando pelas arestas. Aqui, percebemos uma característica do grafo 
𝐺1. Para chegar ao vértice 4, é essencial, independentemente do vértice de 
partida, passar pela aresta que liga o vértice 5 ao vértice 4. A esse vértice damos 
o nome de ponte do grafo. A sua remoção faz do grafo 𝐺1, um grafo não conexo. 
1.2 Conexidade em grafos orientados 
Vamos considerar agora os grafos orientados. Existem quatro tipos de 
conexidade analisadas nesse tipo de grafo. A importância de estabelecer 
classificações é que cada algoritmo vai funcionar para determinados casos. 
1.2.1 Grafo não conexo 
Um grafo não conexo é aquele em que pelo menos um par de vértices 
não é ligado por nenhuma cadeia. É o caso do grafo a seguir. 
 
 
 
4 
Figura 3 – Grafo orientado não conexo 
 
1.2.2 Grafo simplesmente conexo (s-conexo) 
Um grafo orientado é chamado simplesmente conexo ou s-conexo 
quando a sua versão não orientada for conexa. 
Figura 4 – Dois grafos orientados simplesmente conexos 
 
Veja o caso da Figura 4, que apresenta dois grafos distintos orientados. 
Perceba que, a partir do vértice 4, o vértice 1 não é atingível. Entretanto, se esse 
grafo fosse não orientado, todos os vértices seriam atingíveis por um outro 
vértice qualquer. Afinal, o que provoca a dificuldade de atingir os vértices é 
justamente a orientação. Assim, definimos o grafo simplesmente conexo como 
aquele que é conexo em sua versão não orientada. 
1.2.3 Grafo semi-fortemente conexo (sf-conexo) 
Um grafo orientado é semi-fortemente conexo ou s-conexo se, dado 
qualquer par de vértices 𝑣1, 𝑣2, pelo menos um deles é atingível a partir do outro, 
isto é, existe um caminho que sai de 𝑣1 e chega em 𝑣2 ou existe um caminho 
que sai de 𝑣2 e chega em 𝑣1. 
 
 
 
5 
Figura 5 – Dois grafos orientados semi-fortemente conexos 
 
Na Figura 5, observamos dois grafos semi-fortemente conexos. Para 
realizar esse teste, você precisa selecionar todos os pares possíveis de vértices. 
Veja, por exemplo, o que ocorre quando comparamos o vértice 1 e o vértice 4. 
O vértice 4 é atingível pelo vértice 1, embora o vértice 1 não seja atingível pelo 
vértice 4. Isso é válido para quaisquer pares de vértices, sendo suficiente para 
definir o caso semi-fortemente conexo. 
1.2.4 Grafo fortemente conexo (f-conexo) 
Um grafo fortemente conexo, ou ainda f-conexo, é um grafo em que, 
considerando quaisquer 𝑣1, 𝑣2, podemos atingir 𝑣1 saindo de 𝑣2 e 𝑣2 saindo de 
𝑣1. 
Figura 6 – Dois grafos orientados fortemente conexos 
 
Aqui, podemos pontuar que o teste de conexidade envolve a análise de 
vários pares de vértices, que crescem da forma 𝑛2 para a quantidade 𝑛 de 
vértices. Isso justifica a complexidade dos algoritmos computacionais que 
veremos em outras etapas. 
TEMA 2 – GRAFO REDUZIDO 
Nos algoritmos que vamos resolver, é interessante identificar a existência 
de componentes f-conexas, isto é, subgrafos construídos em busca dessa 
propriedade. 
 
 
6 
2.1 Componente f-conexa 
Para esses algoritmos, vamos selecionar um dado grafo, com subgrafos 
que também sejam f-conexa. Se identificarmos algum que seja maximal, isto é, 
que não faça parte de outros que também são f-conexos, esse será uma 
componente f-conexa. Veja, por exemplo, o grafo da Figura 7. 
Figura 7 – Grafo orientado composto de 16 vértices 
 
Percebemos que esse grafo é sf-conexo, isto é, semi-fortemente conexo. 
Entretanto, podemos selecionar subgrafos que são f-conexos maximais. Nesse 
caso, temos quatro possibilidades, que são as componentes f-conexas do grafo 
da Figura 7. Tais componentes estão apresentadas na figura a seguir. 
Figura 8 – Quatro componentes f-conexas do grafo da Figura 7 
 
2.2 Grafo reduzido 
Por definição, um grafo reduzido 𝐺𝑟 = (𝑉𝑟 , 𝐸𝑟) é um grafo formado a partir 
de 𝐺 que atende alguns requisitos. Para formá-lo, cada componente f-conexa 
será um vértice de 𝐺𝑟. Para formar as conexões entre os vértices 𝑣1, 𝑣2 ∈ 𝐺𝑟 
devemos verificar se existe algum vértice de 𝑣1 (lembrando que 𝑣1 é uma 
componente f-conexa, isto é, é um grafo) atingível a algum vértice de 𝑣2. Nesse 
 
 
7 
caso, formamos um arco saindo de 𝑣1 para 𝑣2. Embora a definição textual pareça 
complicada, observe a Figura 9, que apresenta o grafo reduzido da Figura 8. 
Figura 9 – Grafo reduzido da Figura 8 
 
Note que cada componente f-conexa, no grafo reduzido, se tornou um 
vértice desse novo grafo. Note também que a classificação da conexidade do 
grafo reduzido é a mesma do grafo original. Nesse caso, ambos são sf-conexos. 
TEMA 3 – ALGORITMO: DETERMINAÇÃO DAS COMPONENTES F-CONEXAS 
Você deve ter percebido que as componentes f-conexas permitem reduzir 
grafos e escrever as suas versões mais simples. Isso é especialmente 
interessante quando resolvermos problemas de logística e otimização de 
caminhos. 
3.1 Estruturas de dados para o algoritmo de Malgrange 
Nesta seção, vamos determinar o algoritmo de Malgrange, que por sua 
vez permite determinar as componentes f-conexas de determinado grafo. Para 
isso, precisamos resgatar algumas estruturas de dados que devem ser definidas, 
computacionalmente, em Python. 
Nesse caso, escolhemos 𝐺 = (𝑉, 𝐸). O grafo analisado será composto 
pelos vértices 𝑉 e pelas arestas 𝐸. Note que 𝑉 é uma lista de vértices, enquanto 
𝐸 será definido pela lista de adjacência. Como exemplo, vamos utilizar o grafo 
da Figura 10. 
Figura 10 – Grafo para análise do algoritmo de Malgrange 
 
 
 
8 
Aqui, devemos lançar as informações sobre os vértices 
computacionalmente, considerando descendentes e ascendentes. Embora 
tenhamos lançado, em conteúdo anterior, apenas os vértices adjacentes, é 
interessante classificá-los (descendentes ou ascendentes), pois se trata de um 
grafo orientado. 
Tabela 1 – Lista de adjacência para o grafo orientado da Figura 10 
Vértice Vértices 
descendentesVértices 
ascendentes 
1 2,3 5 
2 4,6 1,5 
3 4 1,4 
4 3 2,3 
5 1,2 6,7 
6 5 2,8 
7 5,8 8 
8 6,7 7 
Além disso, o algoritmo vai utilizar algumas variáveis. Vamos chamar de 
𝑌 o vetor que armazena os vértices que ainda não pertencem a uma 
componente. 𝐼 será um indexador que monitora as componentes conexas 
encontradas. Também vamos definir o vetor 𝑅+ e o vetor 𝑅−, que armazenam, 
respectivamente, os descendentes e os ascendentes do vértice analisado. 
3.2 Algoritmo de Malgrange 
Vamos abordar o algoritmo de Malgrange em duas etapas. Na primeira, 
vamos apresentar a estrutura do algoritmo, considerando os laços de repetição 
que precisam ser utilizados. Também vamos reutilizar o exemplo citado para 
aplicar o algoritmo e verificar o resultado encontrado. 
Algoritmo de Malgrange: determinando as componentes f-conexas de 
um grafo orientado. 
 Início Grafo 𝐺 = (𝑉, 𝐸) 
 𝑌 ← 𝑉 
𝐼 ← 0 
Enquanto 𝑌 ≠ ∅ fazer 
 𝐼 ← 𝐼 + 1; 
 
 
9 
𝑅+ ← ∅; 
𝑅− ← ∅; 
Escolher 𝑣 ∈ 𝑌; 
𝑊 ← ∅; 𝑅+ ← {𝑣}; 
 Enquanto 𝑁+(𝑅+) − 𝑅+ ≠ ∅ fazer 
 𝑊 ← 𝑁+(𝑅+(𝑣)) − 𝑅+(𝑣); 
𝑅+ ← 𝑅+(𝑣) ∪ 𝑊; 
𝑊 ← ∅; 𝑅− ← {𝑣}; 
 Enquanto 𝑁−(𝑅−) − 𝑅− ≠ ∅ fazer 
𝑊 ← 𝑁−(𝑅−(𝑣)) − 𝑅−(𝑣); 
𝑅− ← 𝑅−(𝑣) ∪ 𝑊; 
Componente(𝑰) ← 𝑹+ ∪ 𝑹−; 
𝑌 ← 𝑌-componente(𝐼); 
Fim. 
TEMA 4 – APLICAÇÃO DO ALGORITMO DE MALGRANGE 
A partir do grafo da Figura 10, podemos aplicar o algoritmo de Malgrange 
para determinar as componentes f-conexas e escrever o seu grafo em forma 
reduzida computacionalmente. 
4.1 Estudo de caso 
Para realizar esse papel, devemos acompanhar a execução do algoritmo, 
investigando o que ocorre com os dados. A título de aprendizado, é interessante 
que você escolha outros exemplos e faça a execução “a lápis” do algoritmo, para 
verificar se é capaz de determinar as f-componentes e compreender, de fato, o 
que o algoritmo está fazendo. 
Imagine que você inicializa o algoritmo considerando os vértices e a lista 
de adjacência da Tabela 1. Ao inicializar o algoritmo, as primeiras linhas fazem 
com que: 
𝑌 ← 𝑉 
𝐼 ← 0 
𝑅+ ← ∅ 
𝑅− ← ∅ 
𝐼 ← 1 
 
 
10 
Na sequência, escolhemos um vértice qualquer. Por exemplo, o vértice 1. 
Nesse caso, teremos: 
𝑣 ← {1} 
𝑊 = ∅ 
𝑅+ ← {1} 
Como 𝑁+(𝑅+) = {2,3} pela lista de adjacência, devemos proceder o loop, 
dado que 𝑁+(𝑅+) − 𝑅+ ≠ ∅. Logo, atualizamos 𝑊 dado por 𝑊 ← 𝑁+(𝑅+(𝑣)) −
𝑅+(𝑣), obtendo 𝑊 = {2,3}. Atualizamos 𝑅+ ← 𝑅+(𝑣) ∪ 𝑊, obtendo 𝑅+ = {1,2,3}. 
Operamos novamente, encontrando 𝑁+(𝑅+) = {2,3,4,6}. Como 𝑁+(𝑅+) −
𝑅+ ≠ ∅, atualizamos novamente 𝑊, dado por 𝑊 ← 𝑁+(𝑅+(𝑣)) − 𝑅+(𝑣), obtendo 
𝑊 = {4,6}, e atualizamos novamente 𝑅+, obtendo 𝑅+ ← 𝑅+(𝑣) ∪ 𝑊, dado por 
𝑅+ = {1,2,3,4,6}. 
Realizamos o teste mais uma vez. Temos que 𝑁+(𝑅+) = {2,3,4,5,6}. 
Como, mais uma vez, 𝑁+(𝑅+) − 𝑅+ ≠ ∅, atualizamos 𝑊 dado por 𝑊 ←
𝑁+(𝑅+(𝑣)) − 𝑅+(𝑣), obtendo 𝑊 = {5}, e atualizamos novamente 𝑅+, obtendo 
𝑅+ ← 𝑅+(𝑣) ∪ 𝑊, dado por 𝑅+ = {1,2,3,4,5,6}. 
Ao realizar o teste uma última vez, observamos que 𝑁+(𝑅+) − 𝑅+ = ∅. 
Assim, podemos partir para o próximo loop. Esse conjunto é o fecho transitivo 
direto do primeiro vértice. 
Para continuar, atualizamos 𝑅− e 𝑊, obtendo: 
𝑊 = ∅ 
𝑅− = {1} 
Fazemos algo similar a partir daqui, utilizando como verificador os vértices 
ascendentes. Temos que 𝑁−(𝑅−) = {5}, de forma que 𝑁−(𝑅−) − 𝑅− ≠ ∅. Logo, 
atualizamos 𝑊, dado por 𝑊 ← 𝑁−(𝑅−(𝑣)) − 𝑅−(𝑣), obtendo 𝑊 = {5}. Também 
atualizamos 𝑅− ← 𝑅−(𝑣) ∪ 𝑊, obtendo 𝑅− = {5}. 
Operamos novamente, encontrando 𝑁−(𝑅−) − 𝑅− ≠ ∅. Como ainda é 
válida a condição do loop, dado que 𝑁−(𝑅−) = {6,7}, atualizamos 𝑊 dado por 
𝑊 ← 𝑁−(𝑅−(𝑣)) − 𝑅−(𝑣), obtendo 𝑊 = {6,7}, e atualizamos 𝑅− ← 𝑅−(𝑣) ∪ 𝑊, 
obtendo 𝑅− = {5,6,7}. 
Realizando o teste mais uma vez, verificamos que 𝑁−(𝑅−) = {2,6,7,8}. 
Assim, 𝑁−(𝑅−) − 𝑅− ≠ ∅. Logo, atualizamos 𝑊 dado por 𝑊 ← 𝑁−(𝑅−(𝑣)) −
 
 
11 
𝑅−(𝑣), obtendo 𝑊 = {2,8}; também atualizamos 𝑅− ← 𝑅−(𝑣) ∪ 𝑊, obtendo 𝑅− =
{2,5,6,7,8}. 
Ao aplicar o teste outra vez, verificamos que 𝑁−(𝑅−) = {1,2,5,6,7,8}. 
Assim, 𝑁−(𝑅−) − 𝑅− ≠ ∅. Logo, atualizamos 𝑊 dado por 𝑊 ← 𝑁−(𝑅−(𝑣)) −
𝑅−(𝑣), obtendo 𝑊 = {1}, e atualizamos 𝑅− ← 𝑅−(𝑣) ∪ 𝑊, obtendo 𝑅− =
{1,2,5,6,7,8}. 
Agora, aplicamos o teste mais uma vez, saindo do loop, dado que 
𝑁−(𝑅−) = {1,2,5,6,7,8}. Ao sair do loop, obtemos: 
𝑅+{𝑣} = {1,2,3,4,5,6} 
𝑅−{𝑣} = {1,2,5,6,7,8} 
Note que: 
𝑅+(𝑣) ∩ 𝑅−(𝑣) = {1,2,5,6} 
Atualizando: 
Componente(1) = {1,2,5,6} 
Essa intersecção já é uma componente f-conexa do grafo da Figura 10 
(observe a figura). Aqui, atualizamos o vetor 𝑌, que carrega os vértices que ainda 
não estão em alguma componente f-conexa. Nesse caso, tínhamos que 𝑌 =
{1,2,3,4,5,6,7,8}. Atualizando por 𝑌 ← 𝑌 − 𝐶𝑜𝑚𝑝𝑜𝑛𝑒𝑛𝑡𝑒(1), passamos a ter 𝑌 =
{3,4,7,8}. Veja que, como 𝑌 ≠ ∅, devemos continuar aplicando o algoritmo. 
TEMA 5 – GRAFO REDUZIDO DO ESTUDO DE CASO 
A título de exercício, é interessante que você continue a aplicação do 
algoritmo em outras duas iterações, para verificar se ele é capaz de encontrar 
as outras duas componentes f-conexas do problema. O que você irá encontrar 
será componente(2) = {3,4} e componente(3) = {7,8}. 
5.1 Grafo reduzido 
O grafo da Figura 10 apresenta, portanto, 3 componentes f-conexas que 
podem ser determinadas computacionalmente. Verificamos que elas são dadas 
por: 
componente(1) = {1,2,5,6} 
componente(2) = {3,4} 
componente(3) = {7,8} 
 
 
12 
Note, portanto, que a versão reduzida desse grafo pode ser representada 
pela Figura 11. 
Figura 11 – Grafo da Figura 10 reformulado em forma reduzida 
 
Revendo a classificação dos grafos a respeito da conexidade, 
percebemos que ambos são grafos sf-conexos. Note que a versão reduzida do 
grafo mantém a sua classificação. 
NA PRÁTICA 
Figura 12 – Grafo direcionado com 14 vértices 
 
Considere o grafo da Figura 12, que apresenta uma rede de fofocas entre 
14 pessoas diferentes. O sentido da seta mostra para quem cada pessoa conta 
a fofoca. 
a) Utilizando a linguagem de programação Python e os conhecimentos 
desenvolvidos na última atividade prática, forneça, computacionalmente, 
a lista de adjacência (diferenciando descendentes de ascendentes) do 
problema. 
b) Implemente, em Python, o algoritmo de Malgrange, encontrando as 
componentes f-conexas do grafo fornecido. 
 
 
13 
c) Represente, graficamente (pesquise o uso de bibliotecas em Python), o 
grafo da Figura 12 e a sua versão reduzida pelas componentes f-conexas 
da alternativa b. 
FINALIZANDO 
Caro(a) leitor(a), com os estudos desta etapa, você já está desenvolvendo 
a sua maturidade computacional. Esperamos que você consiga programar os 
seus primeiros algoritmos em Python, para resolver problemas da teoria dos 
grafos. Com isso, já estabelecemos as bases para começar a discutir problemas 
de caminho mínimo, de grande interesse nas áreas de logística.