Upload
jorge-antonio-silva
View
17
Download
0
Embed Size (px)
DESCRIPTION
É a determinação de ligações eficazes, com custo mínimo. Levando em consideração ligações diagonais, e até seu ângulo dentro da árvore.
Citation preview
Problema de Steiner em Grafos
CENTRO UNIVERSITRIO DE VOLTA REDONDA CURSO DE GRADUAO EM SISTEMAS DE INFORMAO
TPICOS ESPECIAIS III JORGE ANTNIO DA SILVA
Indice
Denio do Problema de Steiner em Grafos Aplicao do Problema de Steiner em Grafos Exemplos: AlgoriNmos Referncias
Denio
a determinao de ligaes ecazes, com custo mnimo. Levando em considerao ligaes diagonais, e at seu ngulo dentro da rvore.
Denio
Nem sempre o menor comprimento representa a oNmizao. O Problema de Steiner possui variaes em que as arestas da rvore s podem seguir direes horizontal e verNcal, como no caso de circuitos eltricos, por exemplo.
Aplicao
Projeto de circuitos VLSI, redes, logsNca e biologia computacional.
Aplicao
Na rea de redes de computadores, aplicam-se rvores de Steiner na distribuio de vdeo, conferncias mulNmdia que uNlizam comunicao mulNcast para transmisso de dados.
Exemplo
a
d c
b 2
2
4 4
4 4
Exemplo
a
d c
b
2
4 4
4 4
2
Algoritmos
Algoritmos
Algoritmos
Referncias
RIBEIRO, C. C. Metaheurs*cas. Escola Brasileira de Computao, 1998. Disponvel em: hfp://www.inf.puc-rio.br/~celso. Acessado em Junho de 2015.
MATSUBARA, C. M. Algoritmos para o problema da rvore de Steiner com coleta de prmios. Defesa de Mestrado, 2012. Disponvel em: hfp://www.ime.usp.br/~camilam/apresentacao_CamilaMariMatsubara.pdf. Acessado em Junho de 2015.
Referncias BATISTA, V. R. NASCIMENTO, M. Z. rvores de Steiner:
Uma Introduo Teoria Com Alguns Resultados. Disponvel em: hfp://www.impa.br/opencms/pt/pesquisa/pesquisa_coloquio_brasileiro_de_matemaNca/CBM29/afach/poster_wendhel_coimbra.pdf. Acessado em Junho de 2015.
HAI, Z. Ecient Steiner Tree Construc*on Based on Spanning Graphs. Disponivel em: hfp://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.7295&rep=rep1&type=pdf. Acessado em Junho de 2015.