MODELAGEM E OTIMIZAÇÃO DE FLUXO EM UMA REDE REAL CONECTADA
DOI:
https://doi.org/10.20873/uft.2359-3652.2016v3nespp99Palavras-chave:
Fluxo máximo, Otimização de Sistemas, Teoria dos grafosResumo
Este trabalho aborda o problema do fluxo máximo sob a perspectiva da teoria dos grafos, com o objetivo de implementar um algoritmo para a solução do problema, que poderá ser utilizado posteriormente para otimização de redes e de roteamento de pacotes IP. Inicialmente, são trazidas contextualização e definição do problema. Em seguida são apresentados os algoritmos estudados, metodologia e experimentos realizados. Foram implementadas duas técnicas da literatura para solução do problema: O algoritmo de Ford-Fulkerson e o de Edmonds-Karp. Um sistema no formato de uma rede de fibra ótica foi modelada em forma de grafo e os algoritmos foram aplicados ao modelo como prova de conceito. Para avaliar empiricamente a correta implementação dos algoritmos, bem como seu desempenho, uma base de grafos de variados tamanhos e densidades de arestas foi gerada aletoriamente. Os algoritmos foram aplicados a estas instâncias e a comparação dos resultados mostram que o algoritmo de Edmonds-Karp possui desempenho superior.
Referências
CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Introduction to Algorithms (3 ed.), Capítulo 26. MIT Press, 2009.
EDMONDS, J.; KARP, R.M. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the Association for Computing Machinery, Vol. 19, No. 2, 1972.
FORD, L. R.; FULKERSON, D. R. "Maximal flow through a network". Canadian Journal of Mathematics, Vol 8, 1956.
GOODAIRE, E. G.; PARMENTER, M. M.
Discrete Mathematics with Graph Theory. Prentice-Hall, 1997.
LEVITIN, A. V. Introduction to the Design and Analysis of Algorithms (3 ed), Pearson; 2011.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Autores que publicam nesta revista concordam com os seguintes termos:
1. Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Creative Commons Attribution License (CC BY-NC 4.0), permitindo o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial nesta revista.
2. Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
3. Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto posterior ao processo editorial.
4. Além disso, o AUTOR é informado e consente com a revista que, portanto, seu artigo pode ser incorporado pela DESAFIOS em bases e sistemas de informação científica existentes (indexadores e bancos de dados atuais) ou a existir no futuro (indexadores e bancos de dados futuros), nas condições definidas por este último em todos os momentos, que envolverá, pelo menos, a possibilidade de que os titulares desses bancos de dados possam executar as seguintes ações sobre o artigo:
a. Reproduzir, transmitir e distribuir o artigo, no todo ou em parte sob qualquer forma ou meio de transmissão eletrônica existente ou desenvolvida no futuro, incluindo a transmissão eletrônica para fins de pesquisa, visualização e impressão;
b. Reproduzir e distribuir, no todo ou em parte, o artigo na impressão.
c. Capacidade de traduzir certas partes do artigo.
d. Extrair figuras, tabelas, ilustrações e outros objetos gráficos e capturar metadados, legendas e artigo relacionado para fins de pesquisa, visualização e impressão.
e. Transmissão, distribuição e reprodução por agentes ou autorizada pelos proprietários de distribuidoras de bases de dados.
f. A preparação de citações bibliográficas, sumários e índices e referências de captura relacionados de partes selecionadas do artigo.
g. Digitalizar e / ou armazenar imagens e texto de artigo eletrônico.
