Miguel Araújo

Recebeu um Mestrado em Engenharia Informática e Computação pela Faculdade de Engenharia da Universidade do Porto e é actualmente aluno de doutoramento do Programa CMU|Portugal investigando data mining e detecção de anomalias em grafos.

Grafos – 2ª Parte

Depois de na primeira parte (ver Edição 10) termos feito uma introdução ao mundo dos grafos e de termos lançado as primeiras bases para uma melhor compreensão destas estruturas, chegou a altura de perceber, realmente, que problemas podem ser resolvidos.

Pode ficar já claro que o número de algoritmos que resolvem problemas baseados em grafos é enorme, demasiado extenso para ficar completo um artigo, portanto nada melhor do que começar pelos mais simples (e importantes). Preferi manter o nome dos algoritmos e dos problemas em inglês para ser mais fácil encontrá-los numa pesquisa.

Continuar a ler

Grafos – 1ª Parte

Introdução: O que é um grafo

O leitor certamente que já ouviu falar em grafos. São amplamente usados em matemática, mas sobretudo em programação.

Formalmente, um grafo é uma colecção de vértices (V) e uma colecção de arcos (E) constituídos por pares de vértices. É uma estrutura usada para representar um modelo em que existem relações entre os objectos de uma certa colecção.

Pense nos vértices como “locais“. O conjunto dos vértices é o conjunto de todos os locais possíveis. Nesta analogia, os arcos (ou arestas) representam caminhos entre estes locais. O conjunto E (vou usar o termo mais comum – “E” do inglês “edges“) contém todas as ligações entre os locais.

Utilizar grafos é de grande utilidade na representação de problemas da vida real.

Continuar a ler