MODELAGEM E OTIMIZAÇÃO DE FLUXO EM UMA REDE REAL CONECTADA
DOI:
https://doi.org/10.20873/uft.2359-3652.2016v3nespp99Palabras clave:
Fluxo máximo, Otimização de Sistemas, Teoria dos grafosResumen
Este documento aborda el problema de flujo máximo desde la perspectiva de la teoría de grafos, a fin de aplicar un algoritmo para resolver el problema, que luego se pueden utilizar para optimizar las redes y el enrutamiento de paquetes IP. Inicialmente, son llevados de contextualización y definición del problema. A continuación se presenta los algoritmos estudiados, la metodología y los experimentos. Ellos se llevaron a cabo dos técnicas literarias para resolver el problema: El algoritmo de Ford-Fulkerson y Edmonds-Karp. Un sistema en forma de red de fibra óptica se modeló en forma de gráfico y algoritmos se aplicaron al modelo como prueba de concepto. Para evaluar empíricamente la correcta aplicación de los algoritmos y su rendimiento, gráficos de base de diferentes tamaños y densidad de borde fue generado aletoriamente. Los algoritmos se aplican a estos casos y la comparación de los resultados muestran que el algoritmo de Edmonds-Karp tiene un rendimiento superior.
Citas
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.
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
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.
