• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.45.1999.tde-20210729-205403
Document
Auteur
Nom complet
Mario Leston Rey
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 1999
Directeur
Titre en portugais
T-junções, T-cortes e funções conservativas
Mots-clés en portugais
Ciência Da Computação
Otimização Combinatória
Resumé en portugais
O problema da determinação de uma T-junção mínima e os desdobramentos desse problema constituem o assunto central desta dissertação. Determinar uma T-junção mínima é equivalente a decidir se um grafo com pesos mais ou menos 1 nas arestas é livre de circuitos negativos. Exploramos o problema sob esta ótica e apresentamos o Teorema de Sebö-Lucchesi que caracteriza grafos livre de circuitos negativos. Apresentamos, também, o algoritmo de Sebö que determina caminhos de peso mínimo em grafos sem circuitos negativos. Algoritmos que determinam uma T-junção mínima produzem também uma coleção 2-disjunta máxima de T-cortes. Já a determinação de uma coleção 1-disjunta máxima é um problema difícil. Discutimos o algoritmo de Korach e Pennque extrai de uma coleção 2-disjunta máxima de T-cortes uma coleção 1-disjunta 'grande'. O estudo de T-junções mínimas leva naturalmente à consideração de conjuntos máximos de arestas negativas que não induzem circuitos negativos. Apresentamos uma relação minimax, devida a Frank, entre tais conjuntos de arestas e decomposições do grafo em orelhas
Titre en anglais
not available
Resumé en anglais
The problem of finding a minimum T-join and several related problems are the central topic of this thesis. Determining a minimum T-join is equivalent to deciding whether a graph with weights mais ou menos on the edges is free of negativecircuits. We study the problem under this view and discuss the Sebö-Lucchesi Theorem that characterizes graphs with no negative circuits. We also present Sebö's algorithm That determines minimum weight paths in graphs without negative circuits.Algorithms that etermine minimum T-joins also produce a maximum 2-packing of T-cuts. Determining a maximum 1-packing, however, is a hard problem. We discuss the algorithm of Korach and Penn that extracts from a maximum 2-packing of T-cuts a'large' 1-packing. The study of minimum T-joins lead naturally to the consideration of maximum sets of negative edges that do not induce negative circuits. We present a minimax relation, due to Frank, between such sets of edges andear-decompositions of graphs
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
ReyMarioLeston.pdf (39.63 Mbytes)
Date de Publication
2021-07-29
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2024. Tous droits réservés.