Abstrato

GERAÇÃO DE TODAS AS ÁRVORES SPANNING UMA ABORDAGEM COMBINATORIAL

Saptarshi Naskar, Krishnendu Basuli e Samar Sen Sarma

Este artigo trata de toda a geração de árvore geradora de um grafo simples, simétrico e conexo. Como o número de árvores geradoras de um grafo é assintoticamente exponencial, o nosso esforço é gerar todas as árvores numa quantidade razoável de tempo e espaço [1]. O método aqui é qualitativa e quantitativamente melhor que os métodos existentes. A razão por detrás da afirmação é o número mínimo de comparação de árvores duplicadas e nenhum teste de circuito para a sua realização [1,6-11]. Esperamos que a melhoria do algoritmo resida no objetivo de não gerar árvores duplicadas.