Uma representação retangular de um grafo plano G é uma representação de G, onde cada vértice é desenhado como um retângulo de modo que dois retângulos devem compartilhar algum segmento de seus lados se e somente se existe uma aresta em G entre os vértices correspondentes aos retângulos. Ainda, a representação de G deve formar um retângulo e não deve existir buracos, ou seja, toda região interna deve corresponder a algum vértice de G. Um desenho retangular de um grafo plano H é um desenho de H, onde todas as arestas são desenhadas como segmentos horizontais ou verticais. Ainda, todas as faces internas são retângulos e as arestas que incidem na face externa também formam um retângulo. Nesta dissertação, apresentamos os principais trabalhos existentes na literatura para problemas associados à representação retangular. Também apresentamos resultados para problemas associados ao desenho retangular. Por fim, apresentamos o algoritmo que desenvolvemos para determinar as coordenadas dos vértices de um desenho retangular quando a orientação das arestas já foram determinadas. / A rectangular representation of a plane graph G is a representation of G, where each vertex is drawn as a rectangle, such as two rectangles have to share some boundary if and only if exist an edge in G between the corresponding vertices. Also, the representation of G must form a rectangle and does not contain any holes, in other words, every point inside the formed rectangle must correspond to some vertex of G. A rectangular drawing of a plane graph H is a drawing of H, where all edges are drawn either in vertical or in horizontal. Also, every internal face is a rectangle and the edges which are incident in the external face define a rectangle. In this dissertation, we present the main studies in the literature for problems associated with the rectangular representation. We also present results for problems associated with rectangular drawing. Finally, we present the algorithm we developed to determine the coordinates of the vertices of a rectangular drawing when the orientation of the edges have been determined.

Orientador: Fabricio Aparecido Breve / Banca: Eraldo Pereira Marinho / Banca: Fernando Vernal Salina / Resumo: A segmentação de imagens é o processo de identificar e separar estruturas e objetos relevantes em uma imagem, não é uma tarefa trivial para um algoritmo computacional devido à complexidade dos elementos envolvidos no processo. A variedade de imagens e sua grande quantidade de características impossibilitam a utilização de apenas um modelo para a tarefa de segmentação. Deste modo, a aplicação de algoritmos de aprendizado de máquina, ganha importância, pois este ramo da inteligência artificial tenta reproduzir a forma de "aprender" humano. A aplicação do modelo de competição e cooperação entre partículas na segmentação de imagens mostra-se uma abordagem interessante pois possui baixo custo computacional, além de reduzir a necessidade de especialistas para a geração de dados rotulados. Este trabalho propõe melhorias na construção da rede complexa que o modelo de competição e cooperação entre partículas utiliza-se, através da alteração das características extraídas dos píxeis, mudança na forma de ligação dos vértices do modelo utilizando a similaridade das características e a vizinhança espacial dos píxeis da imagem e a influência gerada por uma partícula sob outros vértices vizinhos dentro da rede complexa. A metodologia proposta resultou em uma melhoria do nível de automação do processo, eliminando a necessidade de incrementar ou decrementar a importância de uma característica sob as outras. Comparativamente, durante os testes realizados com 151 imagens e 4530 amostras de... / Abstract: Image segmentation is the process of identifying and separating relevant structures and objects in an image, it is not a trivial task for a computational algorithm due to the complexity of the elements involved in the process. The variety of images and its vast number of characteristics make it impossible to use only a model for the segmentation task. In this way, the application of machine learning algorithms is highlighted, because this branch of artificial intelligence tries to reproduce the way of human learning. The application of the competition and cooperation model among particles in the image segmentations is considered an interesting approach since it has low computational cost, besides reducing the need of specialists for generating labeled data. This work proposes improvements in the making of the complex network that the competition and cooperation model among particles uses, through the alteration of the characteristics extracted from pixels, changes in the shape of the model's connection of the vertices using the similarity of the characteristics and the image pixel's spatial neighboring and the influence generated by a particle under the other neighbor vertices within the complex network. The proposed methodology resulted in an improvement of the process's automation level, eliminating the need to increase or decrease the importance of a characteristic under others. Comparatively, during the tests made with 151 images and 4530 execution samples for each ... / Mestre

[pt] Nessa dissertação vamos introduzir, elaborar e combinar ideias da Teoria de martingais, a Teoria de grafos aleatórios e o Teorema Central do Limite. Em particular, veremos como martingais podem ser usados para representar desvios de contagem de subgrafos. Usando esta representação e o Teorema Central do Limite para martingais, conseguiremos demonstrar um Teorema Central do Limite para a contagem de subgrafos livres de triângulos no grafo aleatório Erdos-Rényi G(n,m) . Além disso, nossa demonstração também nos trará informação sobre a taxa de convergência, mostrando que a distribuição dos desvios converge rapidamente para a distribuição normal. / [en] In this dissertation we shall introduce, elaborate and combine ideas from martingale Theory, random graph Theory and the Central Limit Theorem. In particular, we will see how martingales can be used to represent deviations of subgraph counts. Using this representation and the Central Limit Theorem for martingales, we will be able to demonstrate a Central Limit Theorem for the triangle-free subgraph count in the Erdos-Rényi G(n,m) random graph. Furthermore, our proof also gives us information about the rate of convergence, showing that the distribution of deviations converges rapidly to the normal distribution.

Sejam GI = (VI ,AI) e GM = (VM,AM) dois grafos simples. Um mapeamento de GI para GM é um conjunto de associações, tal que cada vértice de VI está associado a um vértice de VM, e cada aresta de AI está associada a um par de vértices de VM. A cada possível associação é atribuído um custo. O problema de correspondência inexata entre grafos (PCIG) consiste em encontrar um mapeamento de GI para GM, tal que a soma dos custos de suas associações seja mínima. Nesta dissertação, resumimos os resultados encontrados na literatura sobre o PCIG e algumas de suas variações. Os resultados que incluímos aqui tratam sobre a questão de como formular o PCIG e algumas de suas variações, através de programação linear inteira. Provamos alguns resultados de complexidade computacional que relacionam variações do PCIG a problemas clássicos, como isomorfismo e partição de grafos. Fornecemos uma formulação através de programação linear inteira para o PCCA (uma variante do PCIG com conexidade e cobertura de arestas). Mostramos que o PCCA é NP-difícil quando os grafos de entrada são completos ou árvores (chamamos o segundo caso de PCCA para árvores). Apresentamos uma formulação linear inteira e um algoritmo - que é polinomial se o grau máximo dos vértices de VM for limitado por uma constante - para o PCCA para árvores. Mostramos um caso especia em que o PCCA para árvores pode ser resolvido em tempo polinomial. Por último, exibimos alguns resultados experimentais, inclusive com instâncias reais de uma aplicação do problema. / Let GI = (VI ,AI) and GM = (VM,AM) be two simple graphs. A mapping from GI to GM is an association set, such that each vertex in VI is associated to a vertex in VM, and each edge in AI is associated to a pair of vertices of VM. A cost is defined to each possible association. The inexact graph correspondence problem (IGCP) consists in finding a mapping from GI to GM, such that the sum of its associations costs is minimized. In this dissertation, we summarize the results found in the literature about the IGCP and some variations. The results included here address the question of how to formulate the IGCP and some variations, using integer linear programming. We prove some computational complexity results which relate IGCP variations with classical problems, like graph isomorphism and partitioning. We give an integer linear programming formulation to the ICEC (IGCP with connectivity and edges cover). We show that the ICEC is NP-hard when the input graphs are complete or trees (we call the second case ICEC for trees). We introduce an integer linear formulation and an algorithm - which has polynomial running time if the vertices of VM have maximum degree bounded by a constant - to the ICEC for trees. We show a especial case in which the ICEC for trees can be solved in polynomial time. Finally, we present some experimental results, also with instances of a real application of the problem.

Orientador: Prof. Dr. João Ricardo Sato / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Engenharia da Informação, 2014. / O transtorno do déficit de atenção e hiperatividade (TDAH) é um transtorno de neurodesenvolvimento, associado a fatores genéticos e ambientais, compreendendo a sintomatologia: desatenção, hiperatividade e impulsividade. Neste estudo, utilizou-se a teoria dos grafos e a ressonância magnética funcional (fMRI) para obtenção de um método de distinção entre pacientes e controles para o suporte ao diagnóstico do TDAH. O objetivo deste trabalho foi a comparação das medidas de conectividade cerebral de pacientes (TDAH) com sujeitos controle (desenvolvimento típico) por meio da fMRI, medidas de centralidade e o Support Vector Machine (SVM). Utilizou-se a base de dados ADHD-200. Construiu-se um classificador a partir das características extraídas das redes de conectividade cerebral na tentativa de se distinguir entre sujeitos controle e pacientes. O método envolveu o uso do SVM em características de imagens de fMRI, em dois pares de grupos: controle vs pacientes (TDAH) e TDAH subtipos. Foram modelados grafos ponderados e não ponderados e calculadas algumas medidas de centralidade. Na análise por site dos sujeitos controle versus TDAH desatento foram observadas diferenças na conectividade das regiões cerebrais intermediárias, com escore de 63% no limiar 0,25 da centralidade betweenness no site 4. Com grafo ponderado, outras diferenças de conectividade cerebral foram observadas, com escore de 73% para a medida betweenness entre as regiões cerebrais no site 6. A análise dos portadores de TDAH subgrupo desatento versus combinado, no site 6 foram observadas distinções na medida betweenness e no degree das conexões das regiões cerebrais, no limiar de 0,15, com escores de 73% e 77% respectivamente. Em face aos resultados apresentados é possível encontrar algumas distinções nas conexões cerebrais, principalmente entre os sujeitos portadores de TDAH desatento versus TDAH combinado, a partir da extração das características cerebrais, com utilização de algumas medidas de centralidade como variáveis preditoras para o algoritmo SVM. / The Attention Deficit and Hyperactivity Disorder (ADHD) is a neurodevelopmental disorder associated with genetic and environmental factors, including the symptoms: inattention, hyperactivity and impulsivity. In this study, we used graph theory and functional magnetic resonance imaging (fMRI) to obtain a method for distinguishing between patients and controls to support the diagnosis of ADHD. The aim of this study was to compare measures of brain connectivity between patients (ADHD) and control subjects (typically developing). We used through fMRI, measures of centrality, support vector machines (SVM) and the database ADHD-200. We built a classifier based on the features extracted from the brain connectivity networks in an attempt to distinguish between patients and control subjects. The method involved the use of SVM in connectivity features in two sets of groups: Control vs. patients (ADHD) and inattentive ADHD vs Combined. Measures of weighted and unweighted graphs were modeled and some measures of centrality were extracted. In the unweighted graph analysis by site and inattentive ADHD vs control subjects comparison, differences were found in the connectivity pattern, with a score of 63% for betweenness centrality in site 4. In weighted graph, further differences in brain connectivity were observed, with a score of 73% also in betweenness in site 6. In this same site, the analysis of patients with ADHD inattentive versus combined subgroup, achieved scores of of 73% (betwenness) and 77% (degree) in unweighted graph analysis. In conclusion, we found some differences in brain connectivity patterns, especially between subjects with ADHD inattentive versus combined ADHD. By using some measures of centrality as predictors for the SVM algorithm, we found moderate classification accuracy in individual groups¿ prediction.

Made available in DSpace on 2016-12-23T14:33:35Z (GMT). No. of bitstreams: 1 dissertacao.pdf: 2646193 bytes, checksum: 043989a54d6611e19c06eb6bcd7bba69 (MD5) Previous issue date: 2006-06-23 / Neste trabalho é proposta uma estratégia de solução para a construção otimizada de distritos postais. Distrito Postal consiste num conjunto de segmento de eixo de logradouros conectados. Dada uma localidade formada por inúmeros segmentos de logradouros, esse trabalho propõe o arranjamento de subgrupos conexos de segmentos de eixos de logradouros de modo a compor um distrito postal. A estratégia é transformar o sistema de logradouros de uma localidade em um grafo. A partir desse grafo, extrair seus respectivos subgrafos cíclicos que são entendidos como entidades atômicas. Essas entidades atômicas passam por um processo de montagem até comporem um conjunto de distritos postais. A metodologia aqui apresentada divide o trabalho em duas fases distintas: a primeira compreende o processo de obtenção dos subgrafos cíclicos; e a segunda compreende o processo de montagem de distrito postal. O processo de obtenção de subgrafos cíclicos consiste na obtenção da envoltória convexa do grafo e posterior extração dos subgrafos cíclicos tangentes às arestas dessa. Isso de forma sequencial, ou seja, determina-se a primeira envoltória convexa do grafo e extraemse seus respectivos subgrafos tangentes; determina-se a segunda envoltória convexa e extraem-se seus subgrafos, e assim sucessivamente. O trabalho de determinação da envoltória convexa e de extração dos subgrafos cíclicos é feito através de operações da geometria computacional. O processo de construção dos distritos postais se dá através da clusterização dos subgrafos cíclicos, usando como ferramenta a meta-heurística Simulated Annealing. O problema do Carteiro Chinês e Carteiro Chinês Capacitado são formulações suporte para o presente trabalho. O objetivo principal do trabalho é obter, de forma rápida e eficiente o distrito postal otimizado, com menor percurso improdutivo possível, oferecendo agilidade no processo de distribuição domiciliária de objetos postais. / This study proposes a strategia solution for the optimized construction of postal districts. Postal District is a set of segments of publics areas connecteds. Given a locality composed of uncounted segments of publics areas, this study proposes an arrangement of connects subgroups of publics areas with the goal of composing a postal district. The strategy is to transform the system of public areas of a place in a graph and from this graph, to extract their respective cyclical subgraphs that are understood as atomics entities. Those atomics entities are submited by an assembly process until compose a group of postal districts. The methodology here presented divides the study in two different phases: the first one understands the process of obtaining of the cyclical subgraphs; and the second one is understood as the assembly process of postal district The process of obtaining of cyclical subgraph consists in the obtaining of the hull convex of the graph and subsequent extracting up the cyclical subgraphs tangent to edge of that. That is, in a sequential way, in other words, it is determined the first convex hull of the graph and extract up their respective tangent subgraphs; it is determined the second convex hull and extract up their subgraphs and so forth. The study of determination of the convex hull and extracting of the cyclical subgraphs is done through operations of the computational geometry. The process of construction of the postal districts is given through the clustering of the cyclicals subgraphs, using as a tool the meta- heuristic Simulated Annealing. The Chinese Postman's Problem and Capacited Chinese Postman's Problem are formulations support for the present study. The main objective of the study is to obtain, in a fast and efficient way the optimized postal district, with smaller unproductive course possible, offering agility for the process of domiciliary distribution of postal objects.

Submitted by Anna Patricia Pachas Manrique (annapamanrique@gmail.com) on 2017-02-23T20:20:56Z No. of bitstreams: 1 20_02 (1).pdf: 1460371 bytes, checksum: e98c8f4713680550a770e8efcc7ffa14 (MD5) / Approved for entry into archive by Janete de Oliveira Feitosa (janete.feitosa@fgv.br) on 2017-08-03T17:52:37Z (GMT) No. of bitstreams: 1 20_02 (1).pdf: 1460371 bytes, checksum: e98c8f4713680550a770e8efcc7ffa14 (MD5) / Made available in DSpace on 2017-08-18T14:34:31Z (GMT). No. of bitstreams: 1 20_02 (1).pdf: 1460371 bytes, checksum: e98c8f4713680550a770e8efcc7ffa14 (MD5) Previous issue date: 2016-08-29 / The speed and comprehensiveness global level with the pathogen has spread in recent years has drawn attention to the importance of the contact’s social network structure. In fact, the topology of the networks in which members of society interact has influenced the dynamics of epidemics. Studies have shown that pathogens when disiparem in scale-free networks have different effects when compared broadcast in random networks, such as the classic models. In these there were epidemic threshold, may somehow the health ministry have a control on the dissipation of diseases by applying certain measures such as vaccines. Already in models in which are considered the networks, specifically the free network scale, the threshold disappears. Thus, the epidemic threshold depends on the topology is required to include within this structure models Because of the importance of these networks, random networks and scalefree have been implemented along the epidemics of propagation models to check the epidemic threshold and the characteristic time, noting that the epidemic threshold disappears / A velocidade e a abrangência a nível mundial com que os agentes patogênicos tem se disseminado nos últimos anos tem chamado a atenção para a importância da estrutura da rede social de contato . De fato, a topologia das redes na qual os membros da sociedade interagem têm influenciado na dinâmica das epidemias.Estudos têm demostrado que os agentes patogênicos ao se dissiparem em redes livres de escala tem efeitos diferentes se comparado quando difundidos em redes aleatórias, como nos modelos clássicos. Nestes existiam limiar de epidemia ,podendo de alguma forma as entidades de saúde ter um controle sobre a dissipação das enfermidades , aplicando certas medidas como as vacinas por exemplo. Já nos modelos nos quais são consideradas as redes , especificamente a rede livre de escala,este limiar desaparece. Desta forma, o limiar de epidemia ao depender da topologia se faz necessário incluir esta estrutura dentro dos modelos epidemiológicos. Devido a importância destas redes , redes aleatórias e principalmente redes livres de escala foram implementadas junto a modelos de propagação de epidemias para verificar o limiar de epidemia e o tempo característico , verificando que o limiar de epidemia desaparece.

Submitted by Joaquim Heck (joaquimheck@uol.com.br) on 2018-03-06T23:24:07Z No. of bitstreams: 1 PDF_CDAE_Tese_Joaquim_Heck.pdf: 10473820 bytes, checksum: ad23dda74b39a1cdacaf8ac5345e3c9d (MD5) / Approved for entry into archive by Debora Nunes Ferreira (debora.nunes@fgv.br) on 2018-03-07T12:33:18Z (GMT) No. of bitstreams: 1 PDF_CDAE_Tese_Joaquim_Heck.pdf: 10473820 bytes, checksum: ad23dda74b39a1cdacaf8ac5345e3c9d (MD5) / Made available in DSpace on 2018-03-07T12:39:47Z (GMT). No. of bitstreams: 1 PDF_CDAE_Tese_Joaquim_Heck.pdf: 10473820 bytes, checksum: ad23dda74b39a1cdacaf8ac5345e3c9d (MD5) Previous issue date: 2018-02-23 / Esta tese apresenta os resultados de um estudo em metodologia que estabeleceu um novo método específico de análise documental e histórica, denominado cartografia estrutural para revisão de literatura, e que foi aplicado de forma experimental no estudo histórico de um tema da área de Pesquisa Operacional, os Problem Structuring Methods (PSMs). A cartografia estrutural para revisão de literatura é um método rigoroso e interdisciplinar que revela a estrutura subjacente à uma literatura por meio dos conceitos metodológicos encontrados em pesquisa documental, pesquisa histórica, Teoria dos Grafos, Análise de redes de citações e Cartografia. Verificou-se, a partir dessa interdisciplinaridade, que as relações entre diferentes autores, de diferentes épocas e que publicaram em diferentes periódicos são essenciais para aprofundar a compreensão e familiarizar o pesquisador com uma determinada área do conhecimento. Depois de introduzir a natureza básica da indexação de citações e da análise de rede, esse estudo apresenta a elaboração de um atlas bibliográfico, formado por mapas visuais e diagramas. A aplicação desse método resultou na composição do atlas bibliográfico sobre os PSMs no período de 1950 a 1989. O mapeamento de ideias e conceitos em um arranjo organizado, obtido pela análise exploratória de uma rede de citações longitudinal, assegura familiaridade com os conceitos constitutivos dos PSMs. O atlas bibliográfico é constituído por três análises principais: a exploração da abrangência panorâmica, a das referências e a dos periódicos. Esse estudo fornece subsídios para uma reflexão importante sobre a noção de unidade dos PSMs e a coesão de seus conceitos constituintes encontrada em seus precedentes teóricos. Finalmente, o método de cartografia estrutural possibilita realizar uma revisão de literatura sofisticada, bem como identificar temas fundamentais para futuras pesquisas mais produtivas. / This thesis presents the results of a methodological study that has established a specific method of historical and documental investigation, denominated structural cartography for literature review, which was experimentally applied in the study of Problem Structuring Methods (PSMs) history. Structural cartography for literature review is a rigorous and interdisciplinary method that reveals the underlying structure of a field literature through the methodological notions found in historical research, documental investigation, Graph Theory, and its subfield of citation network analysis, and Cartography. Due to its interdisciplinarity, it becomes clear that the relations between different authors, from different periods of time and from different media are essential to familiarize scholars with their fields of knowledge. After introducing the basic concepts of citation indexing and network analysis, this study shows how to build a bibliographic atlas composed of visual maps and diagrams. The application of this method resulted in the bibliographic atlas on the PSMs from 1950 to 1989. The mapping of ideas and concepts in an organized arrangement, which is obtained by the analysis of a longitudinal exploratory citation network, ensures familiarity with primitive concepts. The bibliographic atlas is composed by three main analysis: the exploration of coverage, of sources and of media. Moreover, this study provided insights for an important reflection on the notion of PSMs unity and the cohesion of their constituent concepts found in their theoretical precedents. Finally, the method of structural cartography for literature review made possible to conduct sophisticate literature review and has provided substantial themes for future research.

Neste estudo são apresentados os resultados do trabalho sobre simulações de redes de conexões complexas. Foram simuladas redes regulares, intermediárias e aleatórias com o número de nós e de conexões variando entre 103 e 5x103 e entre 2x104 e 105, respectivamente, e com probabilidade variando de 0 a 1 com passo de 0.1, com o enfoque na Teoria Espectral. Utilizando a linguagem C e o software Matlab, as redes são representadas pela sua matriz adjacência, com o objetivo de observar-se o comportamento de seus autovalores através de histogramas. A finalidade é a caracterização de redes complexas. Observa-se que a distribuição dos autovalores segue a lei semicircular de Wigner. / This study presents the results of the work about simulations of networks of complex connections. They were simulate regular networks, middlemen and aleatory with the number of nodes and of connections varying between 103 and 5x104 and between 2x104 and 105, respectively, and with probability varying from 0 to 1 with step of 0.1, with the focus in the Spectral Theory. Using the language C and the software Matlab, the networks are represented by its adjacency matrix, with the objective of observing the behavior of its eigenvalues through histograms. The purpose is the characterization of complex networks. Its observed that the eigenvalues distribution follows the Wigners semicircular law.

Made available in DSpace on 2016-06-02T19:06:12Z (GMT). No. of bitstreams: 1 5931.pdf: 2655791 bytes, checksum: 6eafe016c175143a8d55692b4681adfe (MD5) Previous issue date: 2014-05-05 / Financiadora de Estudos e Projetos / Classification is a very important step in pattern recognition, as it aims to categorize objects from a set of inherent features, through its labeling. This process can be supervised, when there is a sample set of labeled training classes, semi-supervised, when the number of labeled samples is limited or nearly inexistent, or unsupervised, where there are no labeled samples. This project proposes to explore minimum information paths in graphs for classification problems, through the definition of a supervised, non-parametric, graph-based classification method, by means of a contextual approach. This method proposes to construct a graph from a set of training samples, where the samples are represented by vertices and the edges are links between samples that belongs to a neighborhood system. From the graph construction, the method calculates the local observed Fisher information, a measurement based on the Potts model, for all vertices, identifying the amount of information that each sample has. Generally, different class vertices when connected by an edge, have a high information level. After that, it is necessary to weight the edges by means of a function that penalizes connecting vertices with high information. During this process, it is possible to identify and select high information vertices, which will be chosen to be prototype vertices, namely, the nodes that define the classes boundaries. After the definition, the method proposes that each prototype sample conquer the remaining samples by offering the shortest path in terms of information, so that when a sample is conquered it receives the label of the winning prototype, occurring the classification. To evaluate the proposed method, statistical methods to estimate the error rates, such as Hold-out, K-fold and Leave-One- Out Cross-Validation will be considered. The obtained results indicate that the method can be a viable alternative to the existing classification techniques. / A classificação é uma etapa muito importante em reconhecimento de padrões, pois ela tem o objetivo de categorizar objetos a partir de um conjunto de características inerentes a ele, atribuindo-lhe um rótulo. Esse processo de classificação pode ser supervisionado, quando existe um conjunto de amostras de treinamento rotuladas que representam satisfatoriamente as classes, semi-supervisionado, quando o conjunto de amostras é limitado ou quase inexistente, ou não-supervisionado, quando não existem amostras rotuladas. Este trabalho propõe explorar caminhos de mínima informação em grafos para problemas de classificação, por meio da criação de um método de classificação supervisionado, não paramétrico, baseado em grafos, seguindo uma abordagem contextual. Esse método propõe a construção de um grafo a partir do conjunto de amostras de treinamento, onde as amostras serão representadas pelos vértices e as arestas serão as ligações entre amostras pertencentes a uma relação de adjacência. A partir da construção do grafo o método faz o calculo da informação de Fisher Local Observada, uma medida baseada no modelo de Potts, para todos os vértices, identificando o grau de informação que cada um possui. Geralmente vértices de classes distintas quando conectados por uma aresta possuem alta informação (bordas). Feito o calculo da informação, é necessário ponderar as arestas por meio de uma função que penaliza a ligação de vértices com alta informação. Enquanto as arestas são ponderadas é possível identificar e selecionar vértices altamente informativos os quais serão escolhidos para serem vértices protótipos, ou seja, os vértices que definem a região de borda. Depois de ponderadas as arestas e definidos os protótipos, o método propõe que cada protótipo conquiste as amostras oferecendo o menor caminho até ele, de modo que quando uma amostra é conquistada ela receba o rótulo do protótipo que a conquistou, ocorrendo a classificação. Para avaliar o método serão utilizados métodos estatísticos para estimar as taxas de acertos, como K-fold, Hold-out e Leave-one-out Cross- Validation. Os resultados obtidos indicam que o método pode ser um uma alternativa viável as técnicas de classificação existentes.