BUSCA DE SUBGRAFOS POR MEIO DE RÓTULOS

Resumo

Grafos são amplamente usados em diversas aplicações, como encaminhamento de pacotes na internet, cálculo da melhor rota para chegar a um destino ou descobrir a forma mais eficiente para a distribuição de recursos. Entretanto, por diversos motivos, encontrar ou reconhecer uma parte do grafo pode se fazer necessário para a execução de uma tarefa. Em razão disso, a busca de subgrafos torna-se uma operação importante e objeto de busca de algoritmos eficientes para fazê-lo.  Nessa pesquisa, em específico, trabalha-se com grafos rotulados. Os subgrafos procurados possuem determinadas características, tais como ser acíclico e possuir no máximo uma distância δ entre seus vértices de mesmo rótulo no grafo. Esse δ é um parâmetro passado na função que representa a proporção entre o grafo que está sendo procurado e o subgrafo retornado como resposta da função. Para os testar a função implementada, foi utilizado um conjunto de dados reais baseados na análise da estrutura topológica da interação entre proteínas, formando um grafo com 2361 vértices e 7181 arestas. Quando executado o algorítimo, a procura por um certo subgrafo linear, em um processador i5 com 4 GB de memória RAM,  encontra as soluções possíveis em cerca de 70 milisegundos. O algorítimo implementado ainda não permite grafos com nós com mais de um filho, devido à complexidade. Essa será  entretanto a próxima etapa deste trabalho.