BCC204 - Teoria dos Grafos

BCC204 - Teoria dos Grafos

Marco Antonio M. Carvalho

(baseado nas notas de aula do prof. Haroldo Gambini Santos)Departamento de Computação

Instituto de Ciências Exatas e BiológicasUniversidade Federal de Ouro Preto

22 de outubro de 2019

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 1 / 27

Avisos

Site da disciplina:I http://www.decom.ufop.br/marco/

Lista de e-mails:I bcc204@googlegroups.com

Para solicitar acesso:I http://groups.google.com/group/bcc204

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 2 / 27

Conteúdo

1 Ordenação Topológica

2 Busca em Profundidade - DFS

3 Algoritmo de Kahn

4 Aplicações

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 3 / 27

Avisos

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 4 / 27

Ordenação Topológica

DefiniçãoUma Ordenação Topológica de um grafo acíclico direcionado (GAD), é umaordenação linear de seus vértices, na qual cada vértice aparece antes de seusdescendentes.

Em outras palavras, é uma ordenação linear de vértices na qual cada vérticeprecede os vértices que formam seu fecho transitivo direto.

Cada GAD possui uma ou mais ordenações topológicas.

Caso um grafo possua ciclos ou seja não direcionado, não é possível estabeleceruma relação de precedência entre os vértices, e portanto, é impossível estabeleceruma ordenação topológica.

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 5 / 27

Ordenação Topológica

HistóricoAlgoritmos de ordenação topológica começaram a ser estudados na década de 60,no contexto da técnica PERT/CPM.

O PERT prevê o cálculo da duração de atividades complexas a partir da médiaponderada de três durações possíveis dessas atividades.

O CPM é um método de identificação do caminho crítico dada uma sequência deatividades, isto é, quais atividades de uma sequência não podem sofrer alteraçãode duração sem que isso reflita na duração final de um projeto.

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 6 / 27

Ordenação Topológica

ExemploUm exemplo simples do encadeamento de atividades é relacionado na tabelaabaixo, para a fabricação de uma estante.

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 7 / 27

Ordenação Topológica

ExemploConsiderando que a coluna Duração tenha sido calculada pelo método PERT, épossível, com base na tabela, organizar um grafo do sequenciamento lógico dasatividades de fabricação da estante:I Os vértices representam eventos instantâneos que caracterizam o início e o

término das atividades especificadas nos arcos;I A sequência das atividades é o principal ponto destacado;I O arco pontilhado representa a dependência lógica da atividade de montagem

das tábuas em relação à atividade de compra dos parafusos.I Essa “atividade” é denominada atividade fantasma, e sua duração é igual a

zero (instantânea).

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 8 / 27

Ordenação Topológica

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 9 / 27

Ordenação Topológica

ExemploÉ possível ainda representar a duração de cada atividade representada no grafo ecalcular o tempo mais curto (TC ) e o tempo mais longo de conclusão das tarefas(TL).

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 10 / 27

Ordenação Topológica

AlternativaAlternativamente, o grafo resultante pode ser modelado de outra maneira:I Tarefas a serem desempenhadas em um projeto são representadas por vértices;I Existe um arco entre as tarefas v e w caso a tarefa v obrigatoriamente deva

ser terminada antes que a tarefa w seja começada;I Uma ordenação topológica dos vértices nos fornece uma maneira de realizar

todas as tarefas sem violar as precedências entre tarefas.

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 11 / 27

Ordenação Topológica

AlgoritmosExistem diferentes algoritmos para obtenção de ordenações topológicas em grafos,os de melhor desempenho possuem complexidade linear.

Dois dos mais utilizados são o baseado na Busca em Profundidade (ou DFS) e oAlgoritmo de Kahn.

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 12 / 27

Busca em Profundidade e Ordenação Topológica

PrincípioAtenção, este algoritmo considera o sentido oposto dos arcos em relação aooriginal apresentado nos diagramas!

O algoritmo considera que, caso um vértice x dependa de um vértice y , entãoexiste um arco de x para y .

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 13 / 27

Busca em Profundidade - DFS

TerminologiaI L: Lista que conterá os elementos da ordenação topológica;I Um vértice pode ser não marcado, temporariamente marcado ou

definitivamente marcado;I Inicialmente, todos os vértices são não marcados;I Ao serem atingidos pela primeira vez, os vértices são temporariamente

marcados;I Após terem todas as suas dependências examinadas, os vértices são

definitivamente marcados;I Caso um vértice temporariamente marcado seja examinado novamente, o

grafo possui pelo menos um ciclo.

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 14 / 27

Busca em Profundidade - DFS

Entrada: Grafo G = (V , A)1 L← ∅;2 enquanto existir vértice não marcado e sem arcos de entrada faça3 selecione um vértice v não marcado;4 visite(G , v , L);5 fim

1 função visite(G,v,L)2 se v é temporariamente marcado então retorna Erro;//detecção de ciclo ;3 se v é não marcado então4 marque temporariamente v ;5 para cada arco (vw) faça6 visite(G , w , L);//chamada recursiva da função7 fim8 marque definitivamente v ;9 adicione v ao final de L;

10 fim

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 15 / 27

Exemplo

Lembre-se de inverter o sentido dos arcos!

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 16 / 27

Exercício 1

Lembre-se de inverter o sentido dos arcos!

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 17 / 27

Algoritmo de Kahn

AplicaçãoO algoritmo de Kahn data de 1962 e possui como princípio determinar a cadainstante os vértices que não possuam arcos de entrada e inserir na solução.

A cada vértice inserido na solução, todos seus arcos correspondentes são removidosdo grafo.

Também detecta a existência de ciclos no grafo.

TerminologiaI L: Lista que conterá os elementos da ordenação topológica;I S : Conjunto de vértices que não possuem arcos de entrada.

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 18 / 27

Algoritmo de Kahn

Entrada: Grafo G=(V , A)1 L← ∅;2 S ← vértices sem arcos de entrada;3 enquanto S 6= ∅ faça4 Remova um vértice v de S ;5 Insira o vértice v em L;6 para cada arco (vw) faça7 Remova o arco vw de A;8 se w não possui mais arcos de entrada então9 Insira o vértice w em S ;

10 fim11 fim12 fim13 se A 6= ∅ então retorna Erro;//o grafo possui pelo menos um ciclo ;14 senão retorna L;//a ordenação topológica ;

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 19 / 27

Exemplo

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 20 / 27

Exercício 2

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 21 / 27

Aplicações

ExemplosI Roteiros de instalação de pacotes;I O make (do makefile);I Confecção de dicionários;I Organização de bancos de dados;I Sistemas geográficos;I Alocação de projetos (Project Scheduling).

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 22 / 27

Aplicações: Dependências do pacote GCC

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 23 / 27

Aplicações: Caminho Crítico

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 24 / 27

Aplicações: Caminho Crítico (2)

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 25 / 27

Ordenação Topológica

CuriosidadeEm plataformas Linux, há o comando tsort, que realiza uma ordenação topológicaem uma lista de adjacências informada pelo usuário.

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 26 / 27

Dúvidas?

Marco Antonio M. Carvalho (UFOP) BCC204 22 de outubro de 2019 27 / 27