Grafos – detecção de ciclos e componentes conexas

Em 2005, terminei o curso de formação profissional em CAD/GIS (Sistemas de Informação Geográfica) leccionado pela AIDA (Associação Industrial do Distrito de Aveiro). A conclusão do mesmo previu a realização de um estágio profissional na área respectiva, o qual completei na XLM – Serviços de Informática, elaborando trabalhos de vectorização  de cartas geográficas de Angola e subsequente georreferenciação para a PT-Inovação.

Como me começava a familiarizar com as linguagens de programação Visual LISP e VBA, um colega de turma que desenvolvia trabalhos na Universidade de Aveiro como estagiário, propôs-me o problema:

De um conjunto arbitrário de poli-linhas, construir um outro conjunto onde todos os polígonos são representados por poli-linhas fechadas.

O objectivo prático da proposta prendia-se com o tratamento de uma representação vectorial de modo a poder extrudir as representações de casas. Não cheguei a apresentar uma resolução ou sequer averiguar a existência de ferramentas que completassem o objectivo devido à falta de tempo (ambos os estágios estavam a terminar). Contudo, o problema é claramente redutível ao problema da detecção de ciclos em teoria de grafos.

Há bem pouco tempo, e uns anos mais tarde, o problema surgiu-me com outra roupagem. Basicamente, precisei de garantir que um determinado grafo não contivesse ciclos e fosse conexo. O problema apresenta uma solução simples baseada numa espécie de ordenação topológica de arestas. Elaborei um pequeno vídeo que descreve o procedimento.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em CAD, Computadores e Internet, Sistemas de Informação Geográfica. ligação permanente.

Uma resposta a Grafos – detecção de ciclos e componentes conexas

  1. Pingback: Grafos – detecção de ciclos e componentes conexas – implementação | Sérgio's space

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s