аЯрЁБс>ўџ ,.ўџџџ+џџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџьЅСq`№ПпbjbjqPqP8$::пџџџџџџЄВВВВВВВЦюююю Ц_ р********о р р р р р р $? hЇN В***** ВВ** Š Š Š *В*В*о Š *о Š Š ВВŠ * 0"›•uєдю0 .Š в / 0_ Š ѕ^ ѕŠ ѕВŠ H**Š *****  t ***_ ****ЦЦЦЄj„ЦЦЦjЦЦЦВВВВВВџџџџ Resumo: O Problema da Сrvore Geradora com Rotulaчуo Mэnima (MLSTP, do inglъs minimum labeling spanning tree problem) щ um problema de otimizaчуo combinatѓria que consiste em encontrar uma сrvore de cobertura em um grafo com arestas rotuladas, isto щ, um grafo no qual cada aresta possui um rѓtulo associado, utilizando o menor nњmero de rѓtulos. Este problema щ NP-difэcil e tem atraэdo bastante atenчуo em pesquisas nos њltimos anos. Por sua vez, o Problema Generalizado da Сrvore Geradora com Rotulaчуo Mэnima (GMLSTP, do inglъs generalized minimum labeling spanning tree problem) щ uma generalizaчуo do MLSTP na qual se permite que mњltiplos rѓtulos sejam associados a uma aresta. Ambos os problemas tem aplicaчѕes prсticas em сreas importantes, como Projeto de Redes de Computadores, Projeto de Redes de Transporte Multimodais e Compactaчуo de Dados. Esta tese aborda vсrios problemas de conectividade definidos em grafos com arestas rotuladas, em especial o Problema da Сrvore Geradora com Rotulaчуo Mэnima e sua versуo generalizada. As contribuiчѕes neste trabalho podem ser classificadas entre teѓricas e prсticas. Dentre as contribuiчѕes teѓricas, introduzimos novos conceitos, definiчѕes, propriedades e teoremas њteis em relaчуo a grafos com arestas rotuladas, bem como um estudo poliщdrico sobre o GMLSTP. Dentre as contribuiчѕes prсticas, propusemos novas heurэsticas — como o algoritmo baseado na metaheurэstica MSLB e a heurэstica construtiva pMVCA — e mщtodos exatos — como novas formulaчѕes matemсticas e algoritmos branch-and-cut — para resolver o GMLSTP. Os experimentos computacionais realizados utilizando conjuntos de instтncias bem estabelecidos para o MLSTP sуo relatados, mostrando que as novas abordagens introduzidas neste trabalho alcanчaram os melhores resultados para mщtodos heurэsticos e exatos em comparaчуo com estado da arte da literatura. Palavras-chave: Grafo com arestas rotuladas; Сrvore de cobertura; Meta-heurэstica; Combinatѓria poliщdrica; Branch-and-bound. Abstract: The minimum labeling spanning tree problem (MLSTP) is a combinatorial optimization problem that consists in finding a spanning tree in a simple edge-labeled graph, i.e., a graph in which each edge has one label associated, by using a minimum number of labels. It is an NP-hard problem that has attracted substantial research attention in recent years. In its turn, the generalized minimum labeling spanning tree problem (GMLSTP) is a generalization of the MLSTP that allows the situation in which multiple labels can be assigned to an edge. Both problems have several practical applications in important areas such as computer network design, multimodal transportation network design, and data compression. This thesis addresses several connectivity problems defined over edge-labeled graphs, in special the minimum labeling spanning tree problem and its generalized version. The contributions in this work can be classified between theoretical and practical. On the theoretical side, we have introduced new useful concepts, definitions, properties and theorems regarding edge-labeled graphs, as well as a polyhedral study on the GMLSTP. On the practical side, we have proposed new heuristics —such as the metaheuristic-based algorithm MSLB, and the constructive heuristic pMVCA— and exact methods—such as new mathematical formulations and branch-and-cut algorithms— for solving the GMLSTP. Computational experiments over well established benchmarks for the MLSTP are reported, showing that the new approaches introduced in this work have achieved the best results for both heuristic and exact methods in comparison with the state-of-the-art methods in the literature. Keywords: Edge-labeled graph; Spanning tree; Metaheuristic; Polyhedral Combinatorics; Branch-and-bound.  OuЙК  v w й к  G † ‡ л м 4 5 ф х H I Ѓ Є   Y Z В Г [\ИЙSTUce€‚•—ІЈчгПгПгПгПгПгПгПгПгПгПгПгПгПгПгПгПгПгПгЈ”|гПгПгПг/h Иh И5CJOJPJQJ^JaJnHtH&h ИCJOJPJQJ^JaJnHtH,h Иh ИCJOJPJQJ^JaJnHtH&h ИCJOJPJQJ^JaJnHtH&h ИCJOJPJQJ^JaJnHtH/h Иh И5CJOJPJQJ^JaJnHtH0  TUгдежзийклмнопрстуфхц№ёюююрррррррррррррррррррррююd№Є7$8$H$gd И$d№Є7$8$H$a$gd Ип§ЈПСбвгцюя№ёKLЅІ§ў]^ИЙstЩЪ)*‚ƒрс@A™šьиьиФиЈy^^^^^^^^^^^^^4h Иh ИCJOJPJQJ^JaJmH nHsH tH,h Иh ИCJOJPJQJ^JaJnHtH.h ИCJOJPJQJ^JaJmH nHsH tH7h Иh И5CJOJPJQJ^JaJmH nHsH tH&h\rИCJOJPJQJ^JaJnHtH&h ИCJOJPJQJ^JaJnHtH&h ИCJOJPJQJ^JaJnHtH$š№ёGHЂЃќ§Z[vw“”•ЂЃЄБВГЫЭнпхЭхЭхЭхЭхЭхВ–х{Эх{Эх{Эх{Э{х4h Иh ИCJOJPJQJ^JaJmH nHsH tH7h Иh И5CJOJPJQJ^JaJmH nHsH tH4h Иh ИCJOJPJQJ^JaJmH nHsH tH.h ИCJOJPJQJ^JaJmH nHsH tH4h Иh ИCJOJPJQJ^JaJmH nHsH tHёvwпюррd№Є7$8$H$gd И$d№Є7$8$H$a$gd И61hP:pБ…А‚. АЦA!АЅ"АЅ#‰$‰%ААФАФ Ф†œ 666666666666666666666666666666666666666666 6666666666 666666666666 666666666666666666666666666666666666666666666666666666666666666666N@ёџN Б…Normal dЄШCJ^J_HaJmHsHtH >A@ђџЁ> 0Fonte parсg. padrуoTi@ѓџГT 0 Tabela normalі4ж l4жaі ,kєџС, 0 Sem lista п$џџџџ TUгдежзийклмнопрстуфхц№ёvwс˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€TvwсKˆ0€Kˆ0€Iˆ0Kˆ00Јšп ёп пOVW_`himnulv !()12:;?@G5@„’ГИў СбЇ Д ъ я ЄБОЫсˆ’ГИ•с3цёсОЫс хWA~(,-=h4oБ…ІH• kЇ И\rИ* К‰Bј%ўсџ@€ЬЬXмЬЬп@@џџUnknownџџџџџџџџџџџџGџ:рAxР џTimes New Roman5€Symbol3& џ:рCxР џArialMNimbusRomNo9L-ReguUNimbusRomNo9L-ReguItalMNimbusRomNo9L-Medi7&џрџЌ@ŸCalibri"Aˆ№ФЉ› j'zƒtGR R !№Ѕ‰ДД24ии№ќџ(№џ$PџџџџџџџџџџџџџџџџџџџџџA~(2џџResumoUsuarioHelioўџр…ŸђљOhЋ‘+'Гй0l˜ЈДФамь ќ ( 4 @LT\dфResumoUsuarioNormalHelio3Microsoft Office Word@ъVњ@ъЮnŠYд@\"ŒuєдR ўџеЭеœ.“—+,љЎ0№ hp|„Œ” œЄЌД М Яфиц Resumo Tэtulo ўџџџўџџџ !"ўџџџ$%&'()*ўџџџ§џџџ-ўџџџўџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџRoot Entryџџџџџџџџ РF нŸ•uєд/€1TableџџџџџџџџWordDocumentџџџџџџџџ8$SummaryInformation(џџџџDocumentSummaryInformation8џџџџџџџџџџџџ#CompObjџџџџџџџџџџџџuџџџџџџџџџџџџџџџџџџџџџџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџўџ џџџџ РF#Documento do Microsoft Office Word MSWordDocWord.Document.8є9Вq