Orientador: Varese Salvador Timóteo / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-17T09:47:55Z (GMT). No. of bitstreams: 1 Pereira_VanessaHelena_M.pdf: 2435236 bytes, checksum: c61f3c9e770fd549a5b0fac102f12ffc (MD5) Previous issue date: 2010 / Resumo: A necessidade da operação intermitente de redes complexas leva ao estudo das falhas nas redes de topologia livre de escala (Scale-Free) de Barabási-Albert. Neste trabalho introduzem-se as teorias fundamentais ao estudo das redes complexas, além da revisão de vários trabalhos científicos relacionados às falhas e aos mecanismos de contenção destas. Utilizando o software Attacker-Defender, são construídas várias redes complexas Scale-Free de diferentes tamanhos, representadas por grafos. Estas redes são utilizadas para simular dois tipos de falhas mais frequentes: falhas aleatórias e falhas direcionadas aos hubs (nós com maior número de arestas incidentes) em duas etapas. Na primeira etapa, em dez tamanhos de redes são testadas quatro situações distintas. Na segunda etapa, em sete tamanhos de redes, são testadas dez diferentes vulnerabilidades. A partir da análise dos resultados da primeira etapa, observa-se qual dos quatro cenários analisados é o mais vantajoso para contenção de falhas nas redes. A análise da segunda etapa permite definir a descrição matemática do comportamento dos nós sobreviventes e atingidos no pós-falha, em cada uma das redes, para cada tipo de falha, através de métodos e funções específicas encontradas. / Abstract: The need for the intermittent operation of complex networks leads to the study of failures in these networks topology called Scale-Free, Barabási-Albert. In this work we introduce the fundamental theories to the study of complex networks, in addition to reviewing various scientific studies related to the failures and the mechanisms against cascade failures. Using the Attacker-Defender software, Scale-Free complex networks of different sizes are built, represented as graphs. These networks are used to simulate the two most common types of failures: random failures and attacks to hubs (nodes with the largest number of incident edges) in two steps. In the first step in ten sizes of networks are tested in distinct four cases. In the second step, in seven sizes of networks are tested ten different vulnerabilities. From the analysis of the results of the first step, it is observed which cases are best for the networks. The analysis of the second step provides the mathematical description of the behavior of the survivors and the affected nodes, after the failure in each network for each type of failure, through methods and specific functions was found. / Mestrado / Tecnologia e Inovação / Mestre em Tecnologia

Orientador: Marco Antonio Garcia de Carvalho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-17T11:47:27Z (GMT). No. of bitstreams: 1 Ferreira_AnselmoCasteloBranco_M.pdf: 7338510 bytes, checksum: 593cb683d0380e0c894f0147a4129c77 (MD5) Previous issue date: 2011 / Resumo: O particionamento de grafos tem sido amplamente utilizado como meio de segmentação de imagens. Uma das formas de particionar grafos é por meio de uma técnica conhecida como Corte Normalizado, que analisa os autovetores da matriz laplaciana de um grafo e utiliza alguns deles para o corte. Essa dissertação propõe o uso de Corte Normalizado em grafos originados das modelagens por Quadtree e Árvore dos Componentes a fim de realizar segmentação de imagens. Experimentos de segmentação de imagens por Corte Normalizado nestas modelagens são realizados e um benchmark específico compara e classifica os resultados obtidos por outras técnicas propostas na literatura específica. Os resultados obtidos são promissores e nos permitem concluir que o uso de outras modelagens de imagens por grafos no Corte Normalizado pode gerar melhores segmentações. Uma das modelagens pode inclusive trazer outro benefício que é gerar um grafo representativo da imagem com um número menor de nós do que representações mais tradicionais / Abstract: The graph partitioning has been widely used as a mean of image segmentation. One way to partition graphs is through a technique known as Normalized Cut, which analyzes the graph's Laplacian matrix eigenvectors and uses some of them for the cut. This work proposes the use of Normalized Cut in graphs generated by structures based on Quadtree and Component Tree to perform image segmentation. Experiments of image segmentation by Normalized Cut in these models are made and a specific benchmark compares and ranks the results obtained by other techniques proposed in the literature. The results are promising and allow us to conclude that the use of other image graph models in the Normalized Cut can generate better segmentations. One of the structures can also bring another benefit that is generating an image representative graph with fewer graph nodes than the traditional representations / Mestrado / Tecnologia e Inovação / Mestre em Tecnologia

Orientador: Margarida Pinheiro Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-18T06:57:47Z (GMT). No. of bitstreams: 1 Gower_RobertMansel_M.pdf: 908087 bytes, checksum: f8067f63c68dadafecf74e1387966331 (MD5) Previous issue date: 2011 / Resumo: Dentro do contexto de programação não linear, vários algoritmos resumem-se à aplicação do método de Netwon aos sistemas constituídos pelas condições de primeira ordem de Lagrange. Nesta classe de métodos é necessário calcular a matriz hessiana. Nosso foco é o cálculo exato, dentro da precisão da máquina, de matrizes hessianas usando diferenciação automática. Para esse fim, exploramos o cálculo da matriz hessiana sob dois pontos de vista. O primeiro é um modelo de grafo que foca nas simetrias que ocorrem no processo do cálculo da hessiana. Este ângulo propicia a intuição de como deve ser calculada a hessiana e leva ao desenvolvimento de um novo método de modo reverso para o cálculo de matrizes hessianas denominado edge pushing. O segundo ponto de vista é uma representação puramente algébrica que reduz o cálculo da hessiana à avaliação de uma expressão. Esta expressão pode ser usada para demonstrar algoritmos já existentes e projetar novos. Para ilustrar, deduzimos dois novos algoritmos, edge pushing e um novo algoritmo de modo direto, e uma série de outros métodos conhecidos [1], [20, p.157] e [9]. Apresentamos estudos teóricos e empíricos sobre o algoritmo edge pushing. Analisamos sua complexidade temporal e de uso de memória. Implementamos o algoritmo como um driver do pacote ADOL-C [19] e efetuamos testes computacionais, comparando sua performance com à de dois outros drivers em dezesseis problemas da coleção CUTE [5]. Os resultados indicam que o novo algoritmo é muito promissor. Pequenas modificações em edge pushing produzem um novo algoritmo, edge pushing sp, para o cálculo da esparsidade de matrizes hessianas, um passo necessário de uma classe de métodos que calculam a matriz hessiana usando colorações de grafos, [14, 19, 30]. Estudos de complexidade e testes numéricos são realizados comparando o novo método contra um outro recentemente desenvolvido [30] e os testes favorecem o novo algoritmo edge pushing sp. No capítulo final, motivado pela disponibilidade crescente de computadores com multiprocesadores, investigamos o processamento em paralelo do cálculo de matrizes hessianas. Examinamos o cálculo em paralelo de matrizes hessianas de funções parcialmente separáveis. Apresentamos uma abordagem desenvolvida para o cômputo em paralelo que pode ser usando em conjunto com qualquer método de cálculo de hessiana e outra estratégia específica para métodos de modo reverso. Testes são executados em um computador com memória compartilhada usando a interface de programação de aplicativo OpenMP / Abstract: In the context of nonlinear programming, many algorithms boil down to the application of Newton's method to the system constituted by the first order Lagrangian conditions. The calculation of Hessian matrices is necessary in this class of solvers. Our focus is on the exact calculation, within machine precision, of Hessian matrices through automatic differentiation. To this end, we detail the calculations of the Hessian matrix under two points of view. The first is an intuitive graph model that focuses on what symmetries occur throughout the Hessian calculation. This provides insight on how one should calculate the Hessian matrix, and we use this enlightened perspective to deduce a new reverse Hessian algorithm called edge pushing. The second viewpoint is a purely algebraic representation of the Hessian calculation via a closed formula. This formula can be used to demonstrate existing algorithms and design new ones. In order to illustrate, we deduce two new algorithms, edge pushing and a new forward algorithm, and a series of other known Hessian methods [1], [20, p.157] and [9]. We present theoretical and empirical studies of the edge pushing algorithm, establishing memory and temporal bounds, and comparing the performance of its computer implementation against that of two algorithms available as drivers of the software ADOL-C [14, 19, 30] on sixteen functions from the CUTE collection [5]. Test results indicate that the new algorithm is very promising. As a by-product of the edge pushing algorithm, we obtain an efficient algorithm, edge pushing sp, for automatically obtaining the sparsity pattern of Hessian matrices, a necessary step in a class of methods used for computing Hessian matrices via graph coloring, [14, 19, 30]. Complexity bounds are developed and numerical tests are carried out comparing the new sparsity detection algorithm against a recently developed method [30] and the results favor the new edge pushing sp algorithm. In the final chapter, motivated by the increasing commercial availability of multiprocessors, we investigate the implementation of parallel versions of the edge pushing algorithm. We address the concurrent calculation of Hessian matrices of partially separable functions. This includes a general approach to be used in conjunction with any Hessian software, and a strategy specific to reverse Hessian methods. Tests are carried out on a shared memory computer using the OpenMP paradigm / Mestrado / Analise Numerica / Mestre em Matemática Aplicada

Orientadores: Marcelo Firer, Luiz Antonio Barrera San Martin / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-05T23:33:46Z (GMT). No. of bitstreams: 1 Talpo_HumbertoLuiz_D.pdf: 1408389 bytes, checksum: b11f884cbf1e05f81138a8e91a5980dc (MD5) Previous issue date: 2006 / Resumo: Seja G uma árvore homogênea e Aut(G) seu grupo de automorfismos. Um automorfismo f Î Aut(G) é par se d(f(x),x) º0 mod 2 para todo vértice x Î G, onde d(.,.) é a função distância definida pelo comprimento do menor caminho ligando os vértices. O conjunto Aut+(G) de todos os automorfismos pares é um subgrupo de índice 2 em Aut(G). Definimos uma geodésica g Ì G como um subgrafo isomorfo a Z (onde Z é visto como um grafo que possui arestas unindo inteiros consecutivos). Uma reflexão em uma geodésica g é um automorfismo involutivo f (f² =1) tal que f(x) = x se, e somente se, x Î G. Denotamos por R o conjunto de todas as reflexões em geodésicas. Neste trabalho (Capítulo 2) provamos que, dada uma árvore homogênea de grau par G, o número de cobertura de Aut+(G) pelas reflexões em geodésicas é 11, no seguinte sentido: dado f Î Aut+(G) existem f1, f2,... fk com k £ 11, tais que f(x) = fk °fk-1°...°f1(x) para todo vértice x em G. Além disso, considerando árvores homogêneas, sabemos que o grupo de automorfismos é completo e o subgrupo de automorfismos pares é simples. Flexibilizamos a condição de homogeneidade e conseguimos demonstrar (Capítulo 3) para o caso de árvores semi-homogêneas, que o grupo de automorfismos é simples e completo / Abstract: Let G be a homogeneous tree and Aut(G) its group of automorphism. An automorphism Î Aut(G) is said to be even if d(f(x),x) º0 mod 2 for every vertex x Î G of , where d(.,.) is the canonical distance function defined by the minimum length of paths connecting the vertices. The set Aut+(G) of all even automorphism is a subgroup of index 2 in Aut(G). We define a geodesic g Ì G as a subtree isomorphic to the standard tree of the integers Z, that is, a homogeneous subtree of degree 2. A reflection in a geodesic g is an involutive automorphism f (f² =1) such that f(x) = x if x Î G. We denote by R the set of all reflections in geodesics. In this work (Chapter 2) we prove that, for every even degree tree G, the covering number of Aut+(G) by reflections in geodesics is 11, in the sense that give f Î Aut+(G) there are f1, f2,... fk with k £ 11, such that f(x) = fk °fk-1°...°f1(x) for every vertex x in G.Moreover, if we consider homogeneous trees we know that automorphisms group is complete and the even automorphisms subgroup is simple. We vary the homogeneous condition and we prove that (Chapter 3) for the semi-homogeneous trees, the automorphisms group is simple and complete / Doutorado / Doutor em Matemática

Orientador: Claudio Leonardo Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-07T04:48:23Z (GMT). No. of bitstreams: 1 Miranda_AlbertoAlexandreAssis_M.pdf: 924668 bytes, checksum: 5707312a9e0513f890e4affc3858fbb6 (MD5) Previous issue date: 2006 / Resumo: Um grafo G que tem emparelhamento perfeito é o Pfaffiano se existe uma orientação D das arestas de G, tal que todo circuito conforme de G tem orientação ímpar em D. Um subgrafo H de G é conforme se G- V (H) tem emparelhamento perfeito. Uma orientação de um circuito par é ímpar se numa dada direção de percurso do circuito o número de arestas que concorda com a direção é ímpar. Calcular o número de emparelhamentos perfeitos de um grafo, no caso geral, _e NP-difícil [11, pág. 307]. No entanto, para grafos Pfaffiano, seu cálculo torna-se polinomial [11, pág. 319]. A caracterização de grafos bipartidos Pfaffiano, feita por Little, tem quase trinta anos [9]. No entanto, somente nos últimos anos apareceram algoritmos polinomiais para reconhecimento de tais grafos, por McCuaig [13] e independentemente por Robertson, Seymour e Thomas [14]. A solução para este problema resolve também uma série de problemas, muitos deles clássicos, em teoria dos grafos, economia e química, como descrito no artigo de McCuaig [13, págs. 16 a 35]. Nesta dissertação, apresentamos uma prova de corretude do algoritmo distinta das duas provas anteriormente conhecidas / Abstract: A graph G that contains a perfect matching is Pfaffiano if there is an orientation D of the edges of G, such that every conformal circuit of G is oddly oriented in D. A subgraph H of G is conformal if G - V (H) has a perfect matching. A circuit with an even number of edges is oddly oriented if the number of edges whose orientation in D agrees with any sense of traversal of the circuit is odd. Counting the number of perfect matchings of a graph is known to be NP-hard [11, page 307]. However, when restricted to Pfaffiano graphs, this problem is solvable in polynomial time [11, page 319]. The characterisation of Pfaffiano bipartite graphs, achieved by Charles Little, is almost thirty years old [9]. However, only recently, polynomial time algorithms for determining whether a bipartite graph is Pfaffiano were discovered, by McCuaig [13] and independently by Robertson, Seymour and Thomas [14]. This problem's solution solves a lot of problems, some of them are quite famous, in graph theory, economy and chemistry, as described in McCuaig's article [13, pages 16 to 35]. On this dissertation, we present a new proof of the correctness of this algorithm distinct from the two previously known proofs / Mestrado / Mestre em Ciência da Computação

Orientador: Celia Picinin de Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-08T21:07:02Z (GMT). No. of bitstreams: 1 Pedrotti_Vagner_M.pdf: 1466848 bytes, checksum: 52ed7d36d9f4f7cb6bee307b689f5f78 (MD5) Previous issue date: 2007 / Resumo: Um modulo de um grafo é um subconjunto de seus vertices que não é diferenciado, em relação à adjancencia peços demais vertices do mesmo grafo. Dado um mpodulo M de um grafo G, se todo módulo de G que intercepta M está contido nele ou o contém. M é denominado módulo forte¿Observação: O resumo, na íntegra poderá ser visualizado no texto completo da tese digital / Abstract: A module of a graph is a non distinguishable subset of nodes, regarding the nodes adjacency. Let M denote any module of a graph G. If every module of G wich overlaps M either contains M or is included in it, M is called a strong module...Note: The complete abstract is available with the full electronic digital thesis or dissertations / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Orientador: Claudio Leonardo Lucchesi / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T06:54:51Z (GMT). No. of bitstreams: 1 Miranda_AlbertoAlexandreAssis_D.pdf: 571362 bytes, checksum: bd3600cbf8fe0c2875d8e5c60b6abfd3 (MD5) Previous issue date: 2009 / Resumo: A área de grafos Pfaffianos apresenta muitos problemas em aberto. Nesta tese resolvemos dois problemas sobre grafos Pfaffianos. O primeiro problema resolvido é a obtenção de um algoritmo polinomial para reconhecimento de grafos quase-bipartidos Pfaffianos. Além disso, estendemos tanto o algoritmo como a caracterização de grafos quase-bipartidos Pfaffianos para a classe dos grafos meio-bipartidos. O segundo resultado é a obtencão de vários resultados estruturais básicos sobre grafos k-Pfaffianos. Utilizando esses resultados, obtivemos um contra-exemplo para a conjectura de Norine, que afirma que o número Pfaffiano de todo grafo é uma potência de quatro: apresentamos um grafo cujo numero Pfaffiano é 6 / Abstract: The area of Pfaffian graphs contains many open problems. In this thesis, we solve two problems related to Pfaffian graphs. The first result is a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. Moreover, we extend this algorithm and the characterization of near-bipartite Pfaffian graphs to the class of half-bipartite graphs. The second result is obtaining several basic structural results concerning k-Pfaffian graphs. Using these results, we obtained a counter-example to Norine's conjecture, which states that the Pfaffian number of a graph is always a power of four: we present a graph whose Pfaffian number is 6 / Doutorado / Matematica Discreta e Combinatoria / Doutor em Ciência da Computação

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-02-17T14:13:30Z No. of bitstreams: 1 victoremanuelpintoguedes.pdf: 1012385 bytes, checksum: b255f491e5beb63bcf201beae74d43db (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-02-26T13:07:06Z (GMT) No. of bitstreams: 1 victoremanuelpintoguedes.pdf: 1012385 bytes, checksum: b255f491e5beb63bcf201beae74d43db (MD5) / Made available in DSpace on 2016-02-26T13:07:06Z (GMT). No. of bitstreams: 1 victoremanuelpintoguedes.pdf: 1012385 bytes, checksum: b255f491e5beb63bcf201beae74d43db (MD5) Previous issue date: 2014-08-09 / Este trabalho apresenta uma abordagem para a Teoria dos Grafos a ser aplicada no Ensino Médio. O objetivo é que, a partir dessa teoria, o aluno desenvolva a capacidade de elaborar métodos de resolução de problemas e de observar que problemas de Matemática Discreta não concernem somente problemas de contagem, como são usualmente abordados no Ensino Médio. Nesse trabalho, introduziremos conceitos da Teoria dos Grafos, grafos Eulerianos e Semieulerianos, buscando expor para um professor, uma abordagem possível da teoria, através dos conceitos, exemplos e problemas que devem ser exibidos para os alunos. Acreditamos que tal teoria deva ser apresentada no Ensino Médio devido a seu caráter investigativo, e por exigir do aluno uma capacidade interpretativa para buscar técnicas de resolução do problema. / This work presents an approach to Graph Theory to be applied in High School. The goal is that, from this theory, the student develops the ability to elaborate methods of solving problem and observe that discrete mathematics problems do not concern only counting problems, as they are usually approached in High School. In this paper, we introduce concepts of graph theory, Eulerian and Semieulerianos graphs, seeking to expose to a teacher, a possible approach to this theory, through the concepts, examples and problems that should be displayed to the students. We believe such a theory should be presented in High School due to its investigative character, and it requires the student an interpretative ability to pursue techniques to solve problems.

Orientador: Marco Antonio Garcia de Carvalho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-24T15:15:13Z (GMT). No. of bitstreams: 1 Chiba_ElaineAyumi_M.pdf: 5856831 bytes, checksum: f9d4b4bea391d9b772f2c53ce2466420 (MD5) Previous issue date: 2014 / Resumo: Representar os elementos de uma imagem em forma de grafos torna a estrutura organizada permitindo formular problemas de forma flexível e ser computacionalmente mais eficiente. Existem muitas técnicas da teoria de grafos sendo utilizadas em processamento digital de imagens. Em particular, o particionamento em grafos ou corte em grafos tem sido estudada por diversos autores como uma ferramenta de segmentação de imagens. Particionamento de um grafo refere-se à sua divisão em vários subgrafos tais que cada um deles representa um objeto de interesse na imagem. Neste trabalho, propomos um algoritmo de agrupamento hierárquico aglomerativo dos nós do grafo com base nas métricas de corte e corte médio. As segmentações foram avaliadas usando o benchmark da Berkeley BSDS500 que compara e classifica as segmentações em relação à outras técnicas existentes na literatura. Os resultados obtidos são promissores e nos permite concluir de que a combinação das métricas de corte e corte médio possibilitou melhores segmentações / Abstract: Representing the elements of an image in graphs makes the structure organized allowing to formulate problems in a flexible manner and can be more computationally efficient. There are many techniques of graph theory that are used in digital image processing. In particular, the graph partitioning or graph cut has been studied by several authors as a tool for image segmentation. Partitioning a graph refers to its division into several subgraphs such that each of them represents a meaningful object of interest in the image. In this work we propose a algorithm based on hierarchical agglomerative clustering of the graph nodes driven by the cut and mean cut criteria. The segmentati- ons results were evaluated using the benchmark of Berkeley BSDS500 that compares and classifies the results in relation to other existing techniques in the literature. The results obtained are promising and allows us to conclude that the combination of the cut and mean cut criteria possible best segmentations / Mestrado / Tecnologia e Inovação / Mestra em Tecnologia

Orientadores: Roberto de Alencar Lotufo, Letícia Rittner / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-25T05:00:23Z (GMT). No. of bitstreams: 1 Souza_RobertoMedeirosde_M.pdf: 27462483 bytes, checksum: fd6e6b42169addd0201eeda81c058aea (MD5) Previous issue date: 2014 / Resumo: A Árvore de Componentes é uma estrutura de dados que representa uma imagem através da relação de hierarquia de seus componentes conexos. Ela é uma estrutura adequada para a implementação de filtros conexos e que foi utilizada com sucesso em muitas aplicações. A Árvore Máxima é uma estrutura compacta para a representação da Árvore de Componentes. A principal contribuiçãoo deste trabalho é a proposta do filtro de Simplificação Maximal da Árvore Máxima (MMS) com dois possíveis critérios para efetuar o seu cálculo: um critério de limiarização normalizada (MMS-T) e um critério de Regiões Extremais Maximamente Estáveis (MMS-MSER). Uma metodologia para aplicar o filtro MMS em associação com o filtro de Extinção, que é formalmente definido nesse trabalho, é apresentada. É mostrado que após a aplicação da metodologia de simplificação, a qual escolhe o número de máximos relevantes a serem mantidos na imagem, o número de nós da Árvore Máxima simplificada é no máximo duas vezes o número de máximos mantidos. Para definir o filtro MMS, novos conceitos, como nó composto e sub-ramo são apresentados. Esses conceitos são importantes para definir muitos algoritmos da Árvore Máxima, e eles possuem interpretações interessantes em termos de processamento de imagem. Possíveis aplicações da metodologia proposta, tais como localização de texto, simplificação/segmentação de imagens e reconhecimento de objetos são ilustrados para mostrar o potencial da metodologia. Também, estudos explortatórios de detecção de regiões salientes em imagens e análise da robustez da topologia da Árvore Máxima são apresentados / Abstract: The Component Tree is a data structure that represents an image through the hierarchical relationship of its connected components. It is an adequate structure to implement connected filters, and it has been successfully used in many applications. The Max-Tree is a compact structure for the Component Tree representation. The main contribution of this work is the proposal of the Maximal Max-Tree Simplification (MMS) filter with two possible criteria to compute the filter: a normalized threshold criterion (MMS-T) and a Maximally Stable Extremal Regions (MSER) criterion (MMS-MSER). A methodology to apply the MMS filter in association to the Extinction filter, which is formally defined in this work, is presented. It is shown that after applying our simplification methodology, which sets the number of relevant maxima in the image to be kept, the number of nodes in the simplified Max-Tree is at most twice this number. In order to define the MMS filter, new concepts, such as composite node and sub-branches are introduced. These concepts are important to define many Max-Tree algorithms, and they have interesting interpretations in terms of image processing. Possible applications of the methodology proposed, such as text location, object recognition, and image simplification/segmentation are illustrated to demonstrate the potential of this methodology. Also, exploratory studies, such as detection of distinguished regions in the image, and analysis of the robustness of the Max-tree topology are presented / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica