Search

Detec??o de comunidades ? um tipo de an?lise topol?gica amplamente utilizada em an?lise de grafos de diversas ?reas como an?lise de redes sociais, bioinform?tica e sistemas de recomenda??o. O problema compreende detectar componentes que apresentam alta densidade interna e baixa densidade externa. Devido ao r?pido crescimento do volume de dados de diversas aplica??es e ? ampla utiliza??o deste tipo de an?lise, diversas pesquisas em abordagens paralelas e distribu?das para resolver o problema de detec??o de comunidades surgiram. Alguns algoritmos possuem maior popularidade, resultando em uma extensa quantidade de pesquisa dentro de otimiza??es para processamento paralelo. Outros algoritmos, mesmo possuindo bons resultados de acur?cia em testes, n?o apresentam o mesmo n?vel de profundidade de pesquisa em suas vers?es paralelas e distribu?das. Esta pesquisa aborda a acur?cia e escalabilidade de tr?s algoritmos de detec??o de comunidades. A partir dos experimentos realizados s?o propostas diretrizes para a utiliza??o de cada algoritmo de acordo com as necessidades do usu?rio. Al?m disso, ? explorado o comportamento das abordagens paralelas e poss?veis melhorias s?o propostas. Community detection is a type of topological analysis widely used in graph analysis in several fields such as social network analysis, bioinformatics and recommendation systems. The problem involves detecting components that have high internal density and low external density. Due to the rapid growth in the volume of data from a variety of applications and the wide use of this type of analysis, several researches in parallel and distributed approaches to solve the problem of community detection have emerged. Some algorithms are more popular, resulting in an extensive amount of research on optimizations for parallel processing. Other algorithms, which posses better accuracy results in tests, do not present the same level of research depth in their parallel and distributed versions. This research addresses the accuracy and scalability of three community detection algorithms. User guidelines are proposed based on the experiments results. In addition, the behavior of the parallel approaches is explored and possible improvements are proposed. Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior - CAPES

Seja G = (V (G), E (G)) um grafo. Um conjunto I ⊆V (G) é independente quando quaisquer pares de vértices pertencentes a I não são adjacentes em G. Um conjunto independente é dito maximal se não está propriamente contido em nenhum outro conjunto independente de G. Um grafo G é bem-coberto se todo conjunto independente maximal de G é máximo. Determinar se um grafo é bem-coberto é um problema coNP-completo. Nós apresentamos um algoritmo de kernelização para o problema de determinar a BEM-COBERTURA para grafos distância para uma classe Q. Também resultados relacionados a intratabilidade da BEM-COBERTURA parametrizado para distância de grafos livres de Cl com l ≥5. E por fim a inexistência de um kernel polinomial para BEM-COBERTURA parametrizado por distância para cluster Let G = (V (G), E (G)) be a graph. A set I ⊆ V (G) is independent when any pairs of vertices belonging to I are not adjacent in G. An independent set is maximal if it is not properly contained in any other independent set of G. A graph G is well-covered if every maximal independent set of G is maximum. Determining whether a graph is well-covered is a coNP-complete problem. We present a kernelization algorithm for the problem of determining the WELL-COVERAGE for distance graphs for a class Q. Also results related to the intractability of WELL-COVERAGE parameterized for distance of free graphs of Cl with l ≥5. And finally, the inexistence of a polynomial kernel for WELL-COVERAGE parameterized by distance for cluster. Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) Forest fragmentation, as a result of anthropic activities such as urbanization and agriculture, negatively impacts biodiversity and ecosystem services, threatening the connectivity of the landscape, whether structural or functional. Understanding the landscape structure and connectivity by focusing on forest fragments under the influence of relief is the objective of this study. To this end, we combined landscape ecology metrics, the index of Connectivity Probability (through Graph Theory) with the relief, through Digital Terrain Model (DTM), in the sub-basin of the Pirapora River. The characterization of the structure presented a landscape of agricultural matrix with high vegetation cover, predominantly wavy to strongly wavy relief, large fragments in the upstream and mouth of the sub-basin, close together and with complex shapes. When inserting the relief element, there were more significant differences in the metrics when the slope class is undulating and strongly undulating, especially in the metrics related to area and distance from the nearest neighbor. The functional connectivity of the landscape showed a high probability of connectivity, either in the ecological network or in its spatial potential and the relief impacted directly, making it more costly for the flow and maintenance of species in the fragments. In this context, it is necessary to explore the combination of landscape ecology metrics, connectivity indices, and relief at different scales and methods to better understand the landscape and its phenomena. In addition to actions for conservation and preservation of forest fragments mainly in the agricultural matrix, along riparian zones and small fragments (more fragile), that is, in territorial planning with a focus on forest preservation. A fragmentação florestal em decorrência das atividades antrópicas como a urbanização e agricultura, impactam negativamente na biodiversidade e nos serviços ecossistêmicos, ameaçando a conectividade da paisagem, seja ela estrutural ou funcional. O entendimento da estrutura e conectividade da paisagem focando em seus fragmentos florestais sobre a influência do relevo é o objetivo deste estudo. Para tanto, combinou-se métricas de ecologia da paisagem, o índice de Probabilidade de Conectividade (através da Teoria de Grafos) com o relevo, através de Modelo Digital de Terreno (MDT), na sub-bacia do Rio Pirapora. A caracterização da estrutura, apresentou uma paisagem de matriz agrícola com alta cobertura vegetal, relevo predominantemente ondulado a forte ondulado, grandes fragmentos no montante e foz da sub-bacia, próximos entre si e com formas complexas. Ao inserir o elemento relevo, houve maiores diferenças nas métricas quanto a classe de declividade, houve predominante de relevo ondulado e forte ondulado, principalmente nas métricas relativas a área e distância do vizinho mais próximo. A conectividade funcional da paisagem, mostrou-se com grande probabilidade conectiva, seja na rede ecológica, ou em seu potencial espacial e o relevo impactou diretamente tornando mais custoso o fluxo e manutenção das espécies nos fragmentos. Neste contexto, é necessário explorar mais a combinação métricas de ecologia da paisagem, índices de conectividade, e o relevo, em diferenças escalas e métodos, para melhor entendimento da paisagem e seus fenômenos. Além de ações de conservação e preservação dos fragmentos florestais principalmente na matriz agrícola, ao longo de zonas ripárias e pequenos fragmentos (mais frágeis), ou seja, no planejamento territorial com foco na preservação florestal. CAPES/DS (01/03/2020 a 31/12/2021)

The systemic evaluation of public networks is a mechanism for social and democratic control of the quality of education offered by public schools. The general objective of this work is to create a model based on graph theory that relates schools and students' proficiency in large-scale assessment. For this, the database of the Pernambuco State Assessment System (SAEPE) was used, from 2010 to 2019. This model uses schools as vertices of a graph and edges weighted as the proficiency of students. students. And the relationship between the vertices happens as students complete their educational cycles and change educational institutions. This movement of students was initially observed with data from 2010 in the initial years of schooling. And it ends in 2019 with the end of the last cycle of basic education (third year of high school). In addition, we use Dijkstra's algorithm to find the best school trajectory a student should follow within a public education network. Finally, we performed this model computationally using data from a municipality in the State of Pernambuco. And we present the results obtained. Nenhuma A avaliação sistêmica de redes públicas é um mecanismo de controle social e democrático da qualidade da educação oferecida pelas escolas públicas. O objetivo geral deste trabalho é criar um modelo baseado na teoria dos grafos que relaciona escolas e a proficiência dos estudantes na avaliação de larga escala. Para isso, foi utilizada a base de dados do Sistema de Avaliação do Estado de Pernambuco (SAEPE), desde o ano de 2010 até o ano de 2019. Esse modelo utiliza as escolas como vértices de um grafo e as arestas ponderadas como a proficiência dos estudantes. E a relação entre os vértices acontece a medida que os estudantes vão concluindo os ciclos educacionais e mudando de instituições de ensino. Esse movimento dos alunos foi inicialmente observado com os dados de 2010, nos anos iniciais de escolarização. O periodo se encerra em 2019 com o fim do último ciclo da educação básica (terceiro ano do ensino médio). Além disso, utilizamos o algoritmo de Dijkstra para encontrar qual melhor trajetória escolar um estudante deve percorrer dentro de uma rede publica de educação. Por fim, realizamos computacionalmente esse modelo usando dados de um município do Estado de Pernambuco e apresentamos os resultados obtidos.

Let s, t natural numbers; the Ramsey number R(s,t) is defined as the least positive integer $r$ with the property that every bicolored graph Kr contains one blue monocramatic subgraph Ks or one red monocramatic subgraph Kr. This theory gave rise to extensive research using, among other subjects, the study of combinatorics, started with Ramsey (1928). As simple as the definition is, calculating Ramsey numbers is very difficult and few are known. Exoo (1989), and Goedgebeur and Radziszowski (2013) showed that 40

Orientador: Lindon Fonseca Matias Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Geociências Resumo: A pesquisa analisou a produção do conhecimento em geografia física por meio dos trabalhos defendidos nos programas stricto sensu brasileiro. O objetivo da investigação foi o de mapear a produção do conhecimento desenvolvido nas pesquisas discentes, na relação orientando-orientador, nos programas de pós-graduação. A metodologia da investigação desenvolveu-se na triangulação entre: a) pesquisa fundamentadas em dados, b) descoberta do conhecimento em banco de dados e c) Análise de redes sociais, operacionalizadas pela Teoria dos grafos. A triangulação descrita foi sustentada pela abordagem quali-quantitativa com vista a possibilitar a compressão das relações desveladas no banco de dados. O banco de dados da pesquisa resulta da integração dos repositórios de teses e dissertações da Universidade de São Paulo (USP) e da Coordenação de Aperfeiçoamento de Pessoal de Ensino Superior (CAPES). O desenvolvimento da pesquisa permitiu observar que: a) Há diferenciação espacial das discussões de áreas específicas das subáreas da geografia física; b) Há centralidade regional e institucional de produção do conhecimento na área de geografia física, respectivamente, destacam-se a região sudeste e a Universidade de São Paulo, c) Há uma proeminência temática das subáreas de geoecologia, geomorfologia e climatologia, enquanto classes das específicas da subárea da geografia física, ao mesmo tempo que se observa a emergência de discussões que não são historicamente associadas a discussão da geografia física como: temas urbanos, educação e população e d) Mapear a produção do conhecimento stricto sensu na geografia, identificando os fluxos de relações entre as temáticas, as regiões e os programas só foi possível por meio do grafo, operacionalizado pela teoria dos grafos e a análise de redes sociais; a estratégia metodológica assumida na pesquisa caracteriza-se elemento fundante para o desenvolvimento de estudos que tenham como objetivo identificar as relações existentes e os fluxos decorrentes. Acredita-se que tanto a teoria dos grafos quanto a análise de redes são operadores potentes para as pesquisas geográficas e, principalmente, àquelas que fazem uso do conceito de redes geográficas Abstract: The research analyzed the production of knowledge in physical geography through works defended in Brazilian stricto sensu programs. The objective of the investigation was to map the production of knowledge developed in student research, in the mentor-advisor relationship, in graduate programs. The investigation methodology was developed in the triangulation between: a) research based on data, b) discovery of knowledge in database and c) Analysis of social networks, operationalized by the theory of graphs. The described triangulation was supported by the quali-quantitative approach in order to enable the compression of the relationships revealed in the database. The research database results from the integration of the theses and dissertations repositories of the University of São Paulo (USP) and the Coordination for the Improvement of Higher Education Personnel (CAPES). The development of the research allowed us to observe that: a) There is a spatial differentiation of the discussions of specific areas of the subareas of physical geography; b) There is regional and institutional centrality of knowledge production in the area of physical geography, respectively, the Southeast region and the University of São Paulo stand out, c) There is a thematic prominence of the sub-areas of geoecology, geomorphology and climatology, while classes of the specific to the sub-area of physical geography, while the emergence of discussions that are not historically associated with the discussion of physical geography, such as: urban themes, education and population, and d) Mapping the production of knowledge stricto sensu in geography, identifying the flows of relationships between themes, regions and programs was only possible through the graph, operationalized by graph theory and the analysis of social networks; the methodological strategy adopted in the research is a fundamental element for the development of studies that aim to identify the existing relationships and the resulting flows. It is believed that both graph theory and network analysis are powerful operators for geographic research and, especially, for those that make use of the concept of geographic networks Doutorado Análise Ambiental e Dinâmica Territorial Doutora em Geografia CAPES 001

Orientador: Prof. Dr. Roldão da Rocha Junior Coorientadora: Profa. Dra. Paula Andrea Cadavid Salazar Tese (doutorado) - Universidade Federal do ABC, Programa de Pós-Graduação em Matemática, Santo André, 2022. As álgebras de evolução são álgebras não associativas inspiradas em fenômenos biológicos com aplicações e conexões com vários campos da matemática. Propõe-se o estudo das álgebras de evolução de dimensão finita usando como principal ferramenta a teoria de grafos. Mostra-se como o radical de absorção deste tipo de álgebra pode ser obtido a partir das propriedades do seu grafo associado. Define-se o conceito de laço de uma álgebra de evolução e apresentam-se condições suficientes e necessárias para que a quantidade de laços seja preservada pela troca de base natural. Estuda-se o espaço de derivações de álgebras de evolução não degeneradas e, em especial, das álgebras de evolução de Volterra. Além disso, apresenta-se uma caracterização completa do espaço de derivações das álgebras de evolução associadas a grafos não orientados quando consideradas álgebras sobre corpos de característica positiva. Evolution algebras are non-associative algebras inspired by biological phenomena with applications and connections to several fields of mathematics. We propose to study finite-dimensional evolution algebras using graph theory as the main tool. We show how the absorption radical of these algebras can be obtained from the properties of its associated graph. The concept of loop of an evolution algebra is defined and sufficient and necessary conditions are presented so that the number of loops is preserved by changing the natural base. The space of derivations of non-degenerate evolution algebras and, in particular, of Volterra evolution algebras are studied. Furthermore, a complete characterization of the space of derivations of evolution algebras associated with undirected graphs is presented when considering algebras over fields with non-zero characteristics.

A mobilidade urbana em grandes cidades tem enfrentado desafios crescentes com a introdução de novas opções de transporte privado e diminuição progressiva dos usuários do transporte público. Neste contexto, o transporte público se reinventa e incorpora novas tecnologias de informação e comunicação para aumentar a atratividade dos usuários. Todavia, a manipulação do grande volume de dados provenientes da operação, em particular de sensores de localização instalados nos veículos, é um dos grandes desafios da área de gerência, planejamento e operação do transporte. Este trabalho tem por objetivo o desenvolvimento de um modelo da operação do transporte de ônibus a partir de um grafo variante no tempo. Uma base de dados de grafos é gerada a partir de um repositório de dados abertos com informações da operação diária do transporte de Curitiba. Com a base gerada, métricas de redes complexas são aplicadas para a avaliação da topologia da rede do sistema de transporte, destacando a importância dos diversos pontos de ônibus. Também foi criada uma metodologia para identificação de possíveis áreas para definição de uma integração temporal. Ou seja, para a criação de “terminais virtuais” integrados com a finalidade de permitir que um passageiro troque de ônibus sem pagar nova tarifa. A partir da metodologia desenvolvida, foi proposta a integração temporal de quatro áreas de pontos de ônibus e apresentado o impacto dessa integração temporal nas métricas da rede estática. Por fim, foi avaliada a qualidade da integração temporal através da correlação das paradas de ônibus entre os pontos de uma mesma área, com a finalidade de identificar os horários nos quais a conexão de passageiros pode ser feita em tempo reduzido. Embora os resultados dessa análise tenham sido realizados para o sistema de transporte de Curitiba, o modelo pode ser adaptado para o transporte de ônibus de outras cidades. Urban mobility in large cities has faced growing challenges with the introduction of new private transport options and progressive decrease in the number of users of public transport. In this context, public transport is updated for including new information and communication technologies to increase the attractiveness of users. However, handling the large volume of data provided by the operation, particularly from location sensors installed in vehicles, is one of the greatest challenges in the area of transport management, planning and operation. This work aims to develop a time-varying graph model for the operation of bus transport. A graph database is generated from open data of daily operation of the Curitiba public transportation. By using this database, complex network metrics are then applied to evaluate the transport network topology, highlighting the importance of different bus stops. A methodology was proposed to identify possible areas for temporal integration, i.e., for creating integrated “virtual terminals” in order to allow passengers to change buses without paying a new fare. Based on this methodology, the temporal integration of bus stops in four areas was proposed. The impact of the temporal integration on metrics of the static network was presented. Finally, the quality of temporal integration was evaluated through the correlation of stopping times of buses at the same area. It allows to identify the times at which the connection of passengers can be made in a reduced time. Although the results were carried out for the transport system of Curitiba, the model can be adapted for bus transport of other cities.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) Uma coloração de arestas própria de um grafo é uma atribuição de cores para as suas arestas tal que arestas incidentes em um mesmo vértice têm cores distintas. O Problema da Coloração de Arestas é responder, dado um grafo, qual o menor número de cores para uma coloração de arestas própria. Esse número é chamado de índice cromático e, para um grafo , é denotado por ′(). Por definição, o índice cromático é pelo menos ∆(), onde ∆() é o maior número de arestas incidentes em um mesmo vértice do grafo . Em 1964, Vizing provou que ′() ≤ ∆() + 1 para qualquer grafo simples . Portanto, quando é simples, ∆() ≤ ′() ≤ ∆() + 1. Um grafo é Classe 1 se o seu índice cromático é igual ao seu grau máximo, e é Classe 2 caso contrário. O Problema da Classificação é decidir se um grafo simples é Classe 1. A despeito de haver apenas dois possíveis valores para o índice cromático de um grafo simples, o Problema da Classificação é NP-completo. Em 1985, em sua famosa coluna "The NP-Completeness Column: an Ongoing Guide”, David Johnson classificou alguns problemas da Teoria dos Grafos em relação à sua complexidade computacional. Em alguns casos, esta complexidade ainda era desconhecida e Johnson identificou classes de grafos para as quais considerou que seria fácil determiná-la. Nas classes de grafos split, de comparabilidade e de intervalos, por exemplo, Johnson considerou que determinar a complexidade computacional do Problema da Classificação era possivelmente fácil. Entretanto, após 35 anos, apenas a complexidade computacional do Problema da Classificação para os grafos de comparabilidade foi determinada, sendo este um problema NP-completo. Esta dissertação apresenta uma solução de tempo polinomial para o Problema da Classificação para grafos split-intervalos, além de identificar e corrigir um problema na prova que determina o índice cromático dos grafos split-comparabilidade. A proper edge coloring of a graph is an assignment of colors to its edges such that edges incident with the same vertex have distinct colors. The Edge Coloring Problem is answering, given a graph, which is the least number of colors for a proper edge coloring. That number is called the chromatic index and, for a graph , it is denoted ′ (). By definition, the chromatic index is at least ∆(), wherein ∆() is the largest number of edges incident with the same vertex of the graph . In 1964, Vizing proved that ′() ≤ ∆() + 1 for every simple graph . Therefore, when is a simple graph, ∆() ≤ ′() ≤ ∆()+1. A graph is Class 1 if its chromatic index equals its maximum degree, and it is Class 2 otherwise. The Graph Classification Problem is deciding if a simple graph is Class 1. Even considering that there are only two possible values for the chromatic index, the Graph Classification Problem is still NP-complete. In 1985, in his famous column "The NP-Completeness Column: an Ongoing Guide”, David Johnson classified some problems in Graph Theory concerning their computational complexity. In some cases, that complexity was still unknown and Johnson identified graph classes for which he considered it would be easier to determine it. On the classes of split, comparability, and intervals graphs, for instance, Johnson considered that determining the computational complexity of the Classification Problem was possibly easy. However, after 35 years, only the computational complexity of the Classification Problem for comparability graphs was determined, being it an NP-complete problem. This thesis presents a polynomial-time solution for the Classification Problem for splitinterval graphs, besides identifying and correcting an issue in the previous proof that determined the chromatic index of split-comparablility graphs.

Orientador: Ricardo Dahab Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Um grafo G admite um 3-fluxo se existe uma orientação de G e uma atribuição de pesos em {1, 2} às arestas de G tal que, para todo vértice v do grafo, a soma dos pesos das arestas entrando em v é igual à soma dos pesos das arestas saindo de v. A conjetura dos 3-fluxos de Tutte afirma que todo grafo 4-aresta-conexo admite um 3-fluxo. Uma versão equivalente dessa conjetura é perguntar se todo grafo 2-aresta-conexo com no máximo três cortes de aresta de tamanho três admite um 3-fluxo. Nosso objetivo é caracterizar quais grafos com até quatro cortes de aresta de tamanho três admitem um 3-fluxo, para algumas classes restritas de grafos. Nós focamos em grafos com até seis vértices de grau ímpar. Nós provamos uma caracterização completa para grafos com até quatro vértices de grau ímpar e uma caracterização parcial para grafos com seis vértices de grau ímpar Abstract: A graph G admits a 3-flow if there exists an orientation of G and an assignment of weights in {1, 2} to the edges of G such that, for every vertex v of G, the sum of the weights of the edges entering v is equal to the sum of the weights of the edges leaving v. Tutte's 3-flow conjecture states that every 4-edge-connected graph admits a 3-flow. An equivalent formulation of this conjecture states that every 2-edge-connected graph with at most three edge cuts of size three admits a 3-flow. Our objective is to characterize which graphs with up to four edge cuts of size three admit a 3-flow, for some classes of graphs. We focus on graphs with at most six vertices of odd degree. We prove a characterization for graphs with up to four vertices of odd degree and a partial characterization for graphs with up to six vertices of odd degree Mestrado Ciência da Computação Mestre em Ciência da Computação CAPES 329145/2019-01

Orientador: Ricardo Miranda Martins Dissertação (mestrado profissional) - Universidade Estadual de Campinas Instituto de Matemática, Estatística e Computação Científica Resumo: Este trabalho tem como principal objetivo apresentar a fórmula de Euler e suas aplicações aos poliedros de Platão. A versão da fórmula de Euler para grafos é demonstrada, e também apresentada uma demonstração do teorema para poliedros usando ângulos esféricos. É demonstrada também a existência de apenas cinco poliedros com as características de Platão, usando teoria dos grafos. Em sequência são apresentadas sequências didáticas abordando os sólidos e suas características. Também é mostrado como fazer a construção dos poliedros de Platão com o auxílio do software Geogebra e as relações de Euler aplicadas a estes Abstract: The main aim of this work is to introduce Euler's formula and its applications to Plato's polyhedra. We present the proof of the Euler's formula for graphs and we also give the proof of the Euler's formula for polyedra using spherical angles. We prove the existence of only five polyhedra with Plato's characteristics, using graph theory. In sequence, is presented didactic sequences addressing solids and their characteristics. We also show how to make the constructions of Plato's polyhedra with the aid of the Geogebra software and the Euler relations applied to them Mestrado Matemática em Rede Nacional Mestra CAPES 001

Este trabalho propõe um novo modelo matemático para dinâmicas evolucionárias em redes finitas. Esse modelo estende a equação de replicação em redes finitas para jogadores hiper-racionais, que são capazes de considerar o benefício ou prejuízo dos demais jogadores na escolha de sua estratégia. Este processo é feito através da introdução de um novo parâmetro chamado matriz de preferências, que traz informações sobre a importância que um jogador dá para o benefício ou prejuízo de um outro jogador. A rede é modelada através de um grafo onde cada vértice do grafo representa uma subpopulação de replicadores hiper-racionais com mesma preferência que, a cada instante, interage com uma subpopulação vizinha e recebe um pagamento de acordo com suas preferências por si e por seus vizinhos. A equação obtida não depende de hipóteses sobre as matrizes de pagamento, topologia do grafo ou preferências dos jogadores. Os equilíbrios de Nash e o comportamento dos agentes hiper-racionais em diferentes jogos e grafos são discutidos. Também é feita uma comparação entre jogadores racionais e hiper-racionais para alguns jogos e grafos. This work proposes a new mathematical model for evolutionary dynamics in finite networks. This model extends the replicator equation on networks to hyper-rational players, which considers the profit or the loss of others when choosing their strategy. This is made by adding a new parameter called matrix of preferences, which holds information on how much a player values the profit or the loss of another player. The network is represented by a graph where each vertex is interpreted as a subpopulation of hyper-rational replicators with the same preferences engaged at each time instant in 2-player games with a neighboring subpopulation, receiving a payoff according to their preferences. The obtained equation does not depends on any hypothesis over the game payoff matrices, graph topology or player preferences. Nash equilibria and the behavior of hyper-rational players are discussed. A comparison between rational and hyper-rational players in some games and graphs is also made.

Mestrado em Métodos Quantitativos para a Decisão Económica e Empresarial O uso de dados de séries temporais na modelação de redes financeiras e económicas desafiam algumas suposições estatísticas tradicionais, como a aplicação do Teorema de Limite Central (TLC). No entanto, o recurso aos pressupostos provenientes da Física foi possível resolver algumas das limitações abordadas ao longo do documento. O trabalho desenvolvido baseia-se na aplicação de algoritmos de separação de observadores desenvolvidos pela Closer, cujo problema tem sido abordado desde há alguns anos, permitindo assim resolver os problemas associados à aplicação do TLC. Estes algoritmos baseiam-se na geometria diferencial e relatividade, que foram aplicados em séries de ações das empresas do mercado americano retiradas em escalas de tempo diversas, reportando no final os resultados obtidos em termos de transformação das distribuições vistas por cada um dos observadores. The handling of time-series data in modeling financial and economic networks challenges some traditional statistical assumptions, such as application of the Central Limit Theorem. However, using the assumptions of Physics it was possible to understand some of the limitations of the model. The work developed is set up on the application of observer separation algorithms developed by Closer Consulting, whose problem has addressed for some years, which solves the infinite variation limitation. These algorithms based on differential geometry and relativity, which was applied to series of shares of companies in the American market taken at different time scales, reporting, in the end, the results obtained in terms of transforming the distributions seen by each of the observers. info:eu-repo/semantics/publishedVersion

Estudos sugerem que o envelhecimento saud?vel (ES) e doen?as neurodegenerativas, como a doen?a de Alzheimer ou AD (do ingl?s Alzheimer disease) e o comprometimento cognitivo leve ou MCI (do ingl?s Mild Cognitive Impairment), afetam a conectividade cerebral. M?tricas de teoria de grafos vem sendo utilizadas para avaliar rupturas de conectividade funcional do c?rebro. Por?m, pesquisadores vem explorando preferencialmente estudos transversais. O objetivo principal deste trabalho foi investigar a evolu??o da conectividade cerebral em indiv?duos no envelhecimento saud?vel e no decl?nio cognitivo, a partir dos dados longitudinais de resson?ncia magn?tica funcional no estado de repouso ou rs-fMRI (do ingl?s Resting-State Functional Magnetic Resonance Imaging), utilizando m?tricas de grafos. A amostra utilizada foi dividida em dois grupos, um est?vel (EES-EES e EMCI-EMCI) e um conversor (ES-MCI e MCI-AD). Foram realizadas an?lises longitudinais e transversais dos grupos. O processamento foi implementado no SPM 12-MATLAB e a an?lise foi realizada na ferramenta CONN Toolbox. As m?tricas de grafos escolhidas para descrever as caracter?sticas da topologia das redes foram: efici?ncia global, efici?ncia local, comprimento do caminho caracter?stico, coeficiente de agrupamento de grau. Foram analisadas as redes fronto parietal, sens?rio motora, visual, linguagem, default mode network, aten??o dorsal e sali?ncia. Os resultados indicaram que h? uma diminui??o de for?a de conectividade funcional nos indiv?duos com MCI e AD, quando comparados aos indiv?duos saud?veis. Nos indiv?duos com envelhecimento saud?vel, foi identificado que a efici?ncia local pode ser utilizada como um poss?vel biomarcador entre os indiv?duos que permanecem est?veis e os que convertem. Nos indiv?duos com MCI, n?o foi identificada uma m?trica e sim um conjunto de m?tricas que variam entre os grupos conversores e est?veis. A an?lise de todas as redes no estado de repouso permitiu uma melhor caracteriza??o dos grupos, possibilitando a diferencia??o entre indiv?duos saud?veis est?veis e aqueles que convertem para o decl?nio cognitivo, ao longo do tempo. Studies suggests that healthy aging (ES) and certain neurological diseases, such as Alzheimer's disease (AD) and mild cognitive impairment (MCI), affects brain functional connectivity. Graph Theory (GT) metrics allows us to analyze ruptures in the brain functional connectivity. However, researchers has been preferentially exploring transversal studies. The general objective of this work was to investigate the evolution of brain connectivity in individuals with healthy aging and cognitive decline, based on resting state functional magnetic resonance imaging (rs-fMRI) and using graph metrics. The data was divided into two groups, stable (EES-EES and EMCI-EMCI) and converter (ES-MCI and MCI-AD). The longitudinal analysis was carried out between each evolution over time, then crosswise compared healthy individuals between the stable and converting group, and the same process was performed for individuals with MCI.The processing was implemented in SPM12-MATLAB performed in the CONN Toolbox. The networks analyzed were parietal, sensory motor, visual, language, default mode network, dorsal attention and salience. The GT metrics chosen to describe the main topological characteristics of the networks were: characteristic path length, global efficiency, local efficiency, clustering coefficient and degree. The results indicateds a decrease in the strength of functional connectivity in individuals with MCI and AD compared with healthy aging. In healthy aging individuals, was identified that local efficiency metric can be used as a possible biomarker between those who remain stable and those who convert. In MCI individuals, a metric was not identified, but a set of metrics that vary between converting and stable groups. The analysis of all networks in the resting state allowed for a better characterization of the groups, enabling the differentiation between stable healthy individuals and those who convert to cognitive decline over time.

Um grafo se caracteriza por um conjunto de vértices e um conjunto arestas, cada uma dela conectando dois vértices. Os momentos espectrais de um grafo são utilizados para caracterizar a topologia do grafo. Os algoritmos para calcular os momentos espectrais, em geral, caracterizam-se por ter complexidade de ordem cubica, o que inviabiliza o cálculo para grafos grandes na escala de milhões de nós, por demandar um tempo de processamento computacional muito grande. Este trabalho apresenta uma adaptação do algoritmo, descrito por Cohein-Steiner, para grafos não dirigidos com pesos. O algoritmo devolve um resultado baseado em uma aproximação com diferença na quarta casa decimal, mas que ainda possa ser utilizado para caracterizar o grafo. O mesmo calculou os momentos para um grafo com mais de 800 mil nos em menos de 2,5 segundos. Esta implementação consiste em apresentar uma solução para calcular os momentos espectrais de grandes grafos em um tempo de processamento computacional viável. Dessa forma, a solução proposta e viável para aplicações em problemas que se possa utilizar este algoritmo em problemas de reconhecimento de padrões. Na implementação, foram feitas adaptações no algoritmo, melhorando para um consumo de tempo próximo à complexidade constante O(1). A graph is a collection of vertexes and edges, each one connecting two vertexes. We can use the spectral moments to characterize the topology of the graph. The algorithms that calculate the spectral moments have a cubic-order complexity, a fact that makes it unfeasible for large graphs with millions of nodes because it demands a considerable computational processing time. This work presents an adaption of the algorithm, described by Cohein-Steiner, for undirected weighted graphs. The algorithm returns a result based on an approximation with difference on the forth demail place, that can still be used to characterize the graph. This one calculated the moments for a graph with more than 800 thousands of nodes in less than 2.5 seconds. This implementation consists in presenting a solution for calculating the spectral moments of large graphs in feasible computational processing time, that makes able to use this algorithm in pattern recognizing problems. On the implementation, some adaptions were made on the algorithm, improving for a runtime close to O(1).

This study aims to apply the theory of graphs through the measure of eigenvector centrality in macro projects activities (WBS) of construction of electrical plants of renewable sources such as wind, solar, hydro and biomass. The subprojects that make up the main project, also called by PMI methodology as level 1 activities, are based on the five main scopesfor the construction project: (1) Civil Project, (2) Substation Electrical Project, (3) Medium Voltage Electrical Project, (4) High Voltage Electrical Project, (5) Project of Acquisition of Specific Machinery. The final timing impact relation set by delay in one of the subprojects considering other subproject delays is analyzed as the link between the vertices of theplotted graph for study. The final result obtained through the application of the method are analyzed and evidence the applicability of the theory of graphs in several market segments since it is possible to establish concepts of vertices and connection relation between them Este estudo visa aplicar a teoria de grafos através da medida de centralidade de autovetor em atividades macro (EAP) de projetos de construção de usinas geradoras de energia elétrica de fonte renovável como eólica, solar, hídrica e biomassa. Os subprojetos que compõem o projeto principal, também chamados na metodologia do PMI como atividades de nível 1, são baseados nos cinco escopos principais para a construção de uma usina elétrica: (1) Projeto Civil, (2) Projeto Elétrico de Subestação, (3) Projeto Elétrico de Linha de Rede de Média Tensão, (4) Projeto Elétrico de Linha de Alta Tensão/ Transmissão, (5) Projeto de Aquisição de Maquinário Específico. A relação de impacto em cronograma final configurada por atraso em um dos subprojetos analisados par a par é analisada como a ligação entre os vértices do grafo traçado para estudo. Os resultados finais obtidos através da aplicação do método são analisados e evidenciam a aplicabilidade da teoria de grafos em diversos segmentos de mercado desde que se possa estabelecer conceitos de vértices e relação entre os mesmos.

The systematic review is an essential method for collecting data on a particular object of study. It is a type of research that requires a strict protocol for searching, collecting, analyzing and presenting data, with or without the use of statistical methods. In this sense, Graph Theory is one of the branches of mathematics that offers important resources for the analysis and representation of the relationships between variables of any nature, being also very useful in research such as systematic reviews in the field of psychology. This article is an innovative methodological proposal that aims to describe: the basic process of construction, interpretation and the use of graphs in systematic reviews applied to the area of psychology. The results indicate that with the use of search techniques with graphs it is possible to view and identify rules of association between keywords, for example, in addition to assisting in the investigation of the relationships between the variables under study. It is concluded that the techniques of analysis and visualization by means of graphs, as well as the application of a centrality measure, proved to be adequate and effective, being able to contribute to systematic review studies. La revisión sistemática es un método esencial para recopilar datos sobre un objeto particular de estudio. Es un tipo de investigación que requiere un protocolo estricto para buscar, recopilar, analizar y presentar datos, con o sin el uso de métodos estadísticos. En este sentido, Teoría de Grafos es una de las ramas de las matemáticas que ofrece recursos importantes para el análisis y la representación de las relaciones entre variables de cualquier naturaleza, siendo también muy útil en investigaciones como las revisiones sistemáticas en el campo de la psicología. Este artículo es una propuesta metodológica innovadora que tiene como objetivo describir: el proceso básico de construcción, interpretación y uso de gráficos en revisiones sistemáticas aplicadas al área de la psicología. Los resultados indican que con el uso de técnicas de búsqueda con gráficos es posible ver e identificar reglas de asociación entre palabras clave, por ejemplo, además de ayudar en la investigación de las relaciones entre las variables en estudio. Se concluye que las técnicas de análisis y visualización mediante gráficos, así como la aplicación de una medida de centralidad, demostraron ser adecuadas y efectivas, pudiendo contribuir a estudios de revisión sistemática. A revisão sistemática consiste em método essencial para o levantamento de dados sobre determinado objeto de estudo. É um tipo de pesquisa que requer um protocolo rígido de busca, coleta, análise e apresentação dos dados, podendo ou não utilizar métodos estatísticos. Nesse sentido, a Teoria dos Grafos é um dos ramos da matemática que oferece importantes recursos para a análise e representação das relações entre variáveis de qualquer natureza, sendo muito útil também em pesquisas como as revisões sistemáticas na área da psicologia. O presente artigo constitui-se em uma proposta metodológica inovadora que visa descrever: o processo básico de construção, interpretação e a utilização de grafos em revisões sistemáticas aplicadas à área da psicologia. Os resultados indicam que com utilização das técnicas de pesquisa com grafos é possível visualizar e identificar regras de associação entre palavras-chave, por exemplo, além de auxiliar na investigação das relações entre as variáveis em estudo. Conclui-se que as técnicas de análise e visualização por meio de grafos, bem como a aplicação de medida de centralidade, demonstraram-se adequadas e eficazes, podendo contribuir com estudos de revisão sistemática.

Universidade Tecnológica Federal do Paraná (UTFPR) Problemas de coloração arco-íris, com notáveis aplicações em segurança de informação, têm recebido bastante atenção nos últimos anos na área de Combinatória. Em particular, o número de conexão arco-íris de um grafo conexo , denotado por (), é o menor inteiro para o qual admite uma -coloração de arestas (não necessariamente própria) tal que, entre qualquer par de vértices, existe um caminho arco-íris, ou seja, um caminho em que as cores das arestas são todas distintas. Dada uma coloração de arestas para um grafo , se entre cada par de vértices existe um caminho mínimo que é arco-íris, então é uma coloração arco-íris forte. O menor número de cores que permite uma coloração arco-íris forte de um dado grafo é o número de conexão arco-íris forte de . Um grafo é arco-íris crítico se a remoção de uma aresta qualquer aumenta o número de conexão arco-íris de . Neste trabalho, são determinados o número de conexão arco-íris e o número de conexão arco-íris forte dos grafos sombras de caminhos, cobras triangulares triplas, circulantes 1, 2 e junção + quando tem () ≤ 2. Também foram determinados os números de conexão arco-íris dos grafos junção de sunlet () com quando | ()| ≥ − 1 e de cografos com três vértices pendentes. Foram encontrados novos limitantes superiores para o número de conexão arco-íris dos grafos cobras, de junção de dois grafos com vértice universal e de junção + quando ≤ −2. Também são apresentadas condições necessárias e suficientes para a criticalidade dos grafos leque, dos produtos cartesianos de × quando () = () ≥ 2 ou quando é uma panela, × quando () = () ≥ 1 e de × , quando e são pares. Rainbow coloring problems, of noteworthy applications in Information Security, have been receiving much attention in the last years in Combinatorics. In particular, the rainbow connection number of a connected graph , denoted (), is the least for which admits a (not necessarily proper) -edge-coloring such that between any pair of vertices there is a rainbow path, i. e., a path whose edge colors are all distinct. Given an edge coloring for a graph , if between any pair of vertices there is a minimum path which is rainbow, then is a strong rainbow coloring. The minimum number of colors for which a given graph has a strong rainbow coloring is the strong rainbow connection number of . A graph is rainbow critical if the deletion of any edge of increases (). In this work, we determine the rainbow connection number and the strong rainbow connection number of shadow graphs of paths, triple triangular snake graphs, circulant graphs 1, 2 and join graphs + when has () ≤ 2. We also determine the rainbow connection number of join graphs of sunlet () with when | ()| ≥ − 1 and of cographs with three pendent vertices. We found new upper bounds for the rainbow connection number of snake graphs, join graphs of two graphs with universal vertices, and join graphs + when ≤ − 2. We also present necessary and sufficient conditions for the criticality of fan graphs, Cartesian products × when () = () ≥ 2 or when is a pan graph, × when () = () ≥ 1, and × when and are even.

Orientador: Gabriela Castellano Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Física Gleb Wataghin Resumo: Redes cerebrais têm sido amplamente utilizadas para estudar as relações entre diferentes regiões cerebrais com base em sua dinâmica, medida por meio de várias técnicas (por exemplo, imagem de ressonância magnética funcional e eletroencefalografia). Redes que caracterizam as conexões físicas reais entre as regiões do cérebro, obtidas por meio de imagens de tensor de difusão, também foram amplamente investigadas. No entanto, existem poucos estudos com o objetivo de investigar redes cerebrais derivadas de propriedades estruturais, os quais se basearam na espessura cortical ou no volume da substância cinzenta. O principal objetivo deste trabalho foi investigar a viabilidade de obtenção de informação útil a partir de redes cerebrais derivadas de imagens de ressonância magnética estrutural, utilizando uma propriedade estrutural ainda não explorada em redes cerebrais, nomeadamente, a textura baseada no método da matriz de co-ocorrência. Como objetivos secundários, pretendeu-se: 1) avaliar as conexões estruturais entre regiões da Default Mode Network (DMN); 2) comparar redes cerebrais baseadas em textura para homens e mulheres; 3) investigar a dependência da rede de parâmetros de textura em relação à idade; e 4) caracterizar indivíduos saudáveis com base em redes de textura. No que diz respeito a DMN, o principal resultado foi que as áreas homólogas desta rede estavam fortemente conectadas, conforme o esperado. Também descobrimos que as mulheres apresentavam "hubs de textura" no lóbulo paracentral (parte da área motora primária) e no giro frontal inferior (parte da área de Broca, associada ao processamento de linguagem e produção da fala), enquanto os homens apresentavam "hubs de textura" no giro parietal superior (relacionado à integração sensório-motora e orientação espacial) e no giro frontal superior dorsolateral (relacionado às funções executivas). Além disso, várias regiões apresentaram dependência linear com a idade para a strength, local efficiency, clustering coefficient e eigenvector centrality, indicando alterações na textura dessas regiões com o passar do tempo. Em particular, a ínsula e o giro parahipocampal aumentaram a força de conexão com a idade. Finalmente, o tálamo e o putâmen pareceram ter uma estrutura bastante única (em termos de textura) em comparação com outras regiões analisadas, o que parece apropriado devido aos seus respectivos papéis neurofisiológicos. O principal desafio deste trabalho foi a dificuldade inerente de interpretar as redes de textura. Por outro lado, este trabalho tem potencial para ser estendido a pacientes neurológicos para extrair biomarcadores que possam ajudar a acompanhar a evolução de doenças ou a eficácia de um tratamento Abstract: Brain networks have been widely used to study the relationships between different brain regions based on their dynamics, measured by various techniques (for example, functional magnetic resonance imaging and electroencephalography). Networks that characterize the real physical connections between brain regions, obtained through diffusion tensor images, have also been extensively investigated. However, there are few studies aimed at investigating brain networks derived from structural properties, which were based on cortical thickness or gray matter volume. The main objective of this work was to investigate the feasibility of obtaining useful information from brain networks derived from structural magnetic resonance images, using a structural property not yet explored in brain networks, namely, the texture based on the co-occurrence matrix method. As secondary objectives, it was intended: 1) to evaluate the structural connections between regions of the Default Mode Network (DMN); 2) compare texture-based brain networks for men and women; 3) investigate the dependence of the texture parameters network in relation to age; and 4) to characterize healthy individuals based on texture networks. With regard to the DMN, the main result was that the homologous areas of this network were strongly connected, as expected. We also found that women had "texture hubs" in the paracentral lobe (part of the primary motor area) and in the lower frontal gyrus (part of Broca's area, associated with language processing and speech production), while men had "texture hubs" in the upper parietal gyrus (related to sensorimotor integration and spatial orientation) and in the upper dorsolateral frontal gyrus (related to executive functions). In addition, several regions showed linear dependence with age for strength, local efficiency, clustering coefficient, and eigenvector centrality, indicating changes in the texture of these regions over time. In particular, the insula and the parahippocampal gyrus have increased the strength of connection with age. Finally, the thalamus and putamen appeared to have a very unique structure (in terms of texture) compared to other regions analyzed, which seems appropriate due to their respective neurophysiological roles. The main challenge of this work was the inherent difficulty in interpreting the texture networks. On the other hand, this work has the potential to be extended to neurological patients to extract biomarkers that can help to monitor the evolution of diseases or the effectiveness of a treatment Mestrado Física Aplicada Mestre em Física CAPES 1801218/2018 FAPESP 2013-07559-3

Orientador: Christiane Neme Campos Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: O resumo poderá ser visualizado no texto completo da tese digital Abstract: The abstract is available with the full electronic document Mestrado Ciência da Computação Mestra em Ciência da Computação CNPQ 134580/2018-4

Orientador: Prof. Dr. Edmarcio Antonio Belati Tese (doutorado) - Universidade Federal do ABC, Programa de Pós-Graduação em Energia, Santo André, 2020. Devido ao esgotamento irreversível das fontes energéticas não renováveis, como combustíveis fósseis e nucleares, bem como aos danos que causam ao meio ambiente, deve-se aproveitar com maior eficiência as fontes renováveis. O consumo de energia elétrica é ininterrupto e mesmo uma pequena redução nas perdas promove um montante significativo de economia. Nos sistemas elétricos de distribuição, a reconfiguração é uma técnica de otimização que visa, entre outros objetivos, à minimização de perdas de potência ativa. Com a expansão das redes elétricas inteligentes e crescente introdução de equipamentos telecomandados, é desejável realizar a reconfiguração em tempo real. Dentre as técni-cas de otimização disponíveis, a reconfiguração é a mais econômica porque não demanda gastos com novos equipamentos. Porém ao tentar reconfigurar surge um fenômeno in-conveniente de explosão combinatória devido às características do problema. Diversas metaheurísticas para redução do espaço de busca não têm capacidade de fornecer uma resposta em tempo real, sendo mais adequadas para planejamento. Além disso, a incerteza inerente aos métodos probabilísticos impede que se tenha garantia de obtenção da melhor solução. Neste trabalho, expõe-se um método de reconfiguração em tempo real baseado em Teoria dos Grafos. Devido à característica determinística com resul-tados conservativos, mas sem empregar busca exaustiva, eliminou-se a desvantagem das flutuações estatísticas aleatórias, inerentes aos métodos probabilísticos. Adicionalmente, além de minimizar perdas de potência ativa, pode-se restaurar o funcionamento no caso de ocorrência de faltas. Um pré-processamento computacional proveniente de um fluxo de potência ótimo adaptado direciona a análise da árvore geradora do grafo de topologia para a solução otimizada. O algoritmo foi testado em sistemas contendo 7, 21, 37, 74, 96, 114 e 156 chaves, obtendo a melhor solução disponível na literatura científica, com tempos computacionais da ordem de dezenas de milissegundos. Due to the irreversible depletion of non-renewable energy sources, such as fossil and nu-clear fuels, as well as the damage they cause to the environment, renewable sources should be more efficiently used. Electricity consumption is uninterrupted and even a small reduc-tion in losses promotes a significant amount of savings. In electrical distribution systems, reconfiguration is an optimization technique that aims, among other objectives, to min-imize active power losses. With the expansion of intelligent electrical networks (smart grids) and the increasing introduction of remote-controlled equipment, it is desirable to perform the reconfiguration in real time. Among the optimization techniques available, reconfiguration is the most economical because it does not require expenses with new equipment. However, when trying to reconfigure arises an inconvenient phenomenon of combinatorial explosion due to the characteristics of the problem. Several metaheuristics to reduce the search space do not have the capacity to provide a real-time response, being more suitable for planning. Moreover, the uncertainty inherent in probabilistic methods prevents the guarantee of obtaining the best solution. In this work, a real-time reconfigu-ration method based on Graph Theory is exposed. Due to the deterministic characteristic with conservative results, but without exhaustive search, the disadvantage of random sta-tistical fluctuations inherent to probabilistic methods was eliminated. Additionally, in addition to minimizing active power losses, it is possible to restore operation in the event of faults. Computational preprocessing from an adapted optimal power flow directs the analysis of the topology graph generating tree to the optimized solution. The algorithm was tested in systems containing 7, 21, 37, 74, 96, 114 and 156 switches, obtaining the best solution available in the scientific literature, with computational times of tens of milliseconds.

Orientador: Prof. Dr. Diogo Coutinho Soriano Coorientador: Prof. Dr. André Kazuo Takahata Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Engenharia Biomédica, São Bernardo do Campo, 2020. A teoria dos grafos vem sendo extensivamente utilizada para descrever a relação entre objetos ou elementos em diferentes contextos. Recentemente, estratégias que transformam séries temporais em grafos atraíram atenção de pesquisadores, principalmente pela possibilidade de caracterizar processos (e.g. estados fisiológicos) por meio de suas medidas clássicas (grau, centralidade de autovetor, etc). A neurociência destaca-se entre os principais nichos de aplicação, dado que as interações das regiões corticais na distribuição espaço-temporal das atividades cerebrais pode ser representada por um grafo, sendo o estudo do conectoma a chave para funcionalmente tentar compreender diversas patologias cerebrais. Entre os tipos de conectividade cerebral, a conectividade funcional dinâmica destaca-se por fornecer informações relevantes sobre o curso temporal das medidas de grafos obtidas da similaridade estatística observada entre diferentes regiões, ganhando particular importância no desenvolvimento de sistemas BCI (interface cérebro-máquina, do inglês, brain-computer interface ), onde aspectos dinâmicos da atividade cerebral são utilizados para controlar dispositivos externos em tempo de execução. Tendo isso por motivação, o objetivo deste trabalho é representar graficamente a conectividade funcional dinâmica em tempo de execução através de grafos variantes no tempo visando analisar padrões de EEG coletados no contexto de sistemas BCI durante a execução motora. Para atingir esses objetivos foi desenvolvido um serviço web na tecnologia Node.js, que captura os sinais de EEG vindos do headset do OpenBCI, uma plataforma de baixo custo para amplificação de biopotenciais, e os disponibiliza em uma rede de computadores. Também foi criada uma interface na linguagem Java utilizando a ferramenta GraphStream, a qual transforma os sinais de EEG advindos do OpenBCI em grafos, de acordo com diversos parâmetros de construção, que podem ser atualizados em tempo de execução. Graph theory has been used extensively to describe the objects or elements relationship in different contexts. Recently, strategies that transform time series into graphs have attracted the researchers attention, mainly due to the possibility of characterizing processes (e.g. physiological states) through their classic measures (degree, centrality of eigenvector, etc.). Neuroscience stands out among the main application niches, given that the cortical regions interactions in the brain activities spatio-temporal distribution can be represented by a graph, with the connectome study the key to functionally try to understand different brain pathologies. Among the brain connectivity types, dynamic functional connectivity stands out for providing relevant information on the time course of graph measures obtained from the statistical similarity observed between different regions, gaining particular importance in the development of BCI systems (brain-computer interface), where brain activity dynamic aspects are used to control external devices at run time. Bearing this in mind, the work's objective is graphically represent dynamic functional connectivity at runtime through time-varying graphs in order to analyze EEG patterns collected in the context of BCI systems during motor execution. To achieve these objectives, a web service was developed using Node.js technology, which captures EEG signals from the OpenBCI headset, a low-cost platform for amplifying biopotentials, and making them available on a computer network. Na interface was also created in the Java language using the GraphStream tool, which transforms the EEG signals from OpenBCI into graphs, according to several construction parameters, which can be updated at run time.

Orientadora: Profa. Dra. Dahisy Valadão de Souza Lima Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional - PROFMAT, Santo André, 2020. Esse trabalho apresenta uma breve introdução a teoria dos grafos. Apresentamos os grafos eulerianos e o problema das pontes de Königsberg, resolvido por Euler, que é tido como o marco zero da teoria dos grafos. Demonstramos a validade da fórmula de Euler para grafos planares conexos e apresentamos a característica de Euler como um invariante topológico. Estabelecemos condições suficientes para garantir a planaridade de um grafo. Abordamos o conceito de grafo dual, que nos permite demonstrar de forma alternativa a validade da fórmula de Euler. Finalmente, apresentamos uma proposta de exercícios de fixação, problemas e situações cotidianas em que podemos identificar a aplicação de grafos. This work presents a brief introduction to graph theory. We present the Eulerian graphs and the problem of Königsberg bridges, solved by Euler, considered to be the ground zero of graph theory. We prove the validity of Euler¿s formula for connected planar graphs and present the Euler characteristic as a topological invariant. We establish sufficient conditions to guarantee that a graph is planar. We present the concept of dual graph that allows us to give an alternative proof for the Euler¿s formula. Finally, we present a proposal of exercises, problems and everyday situations where we can identify the application of graphs.

A utilização de grafos nas ciências sociais tem sido cada vez mais representativa, tendo em vista que este tipo de técnica possibilita o estudo das relações entre vários objetos ou categorias. O uso combinado dos grafos com as redes sociais proporciona um avanço na compreensão de fenômenos sociais. O presente artigo objetiva apresentar e analisar as relações encontradas entre as variáveis presentes em 45 artigos científicos que tratam do adoecimento docente, selecionados a partir da técnica da revisão da literatura além da rede de colaboração entre os autores e co-autores dos artigos. Após a aplicação da técnica da Análise de Conteúdo, construiu-se os grafos, com auxílio da ferramenta NodeXL, utilizando-se as categorias encontradas nos artigos. As variáveis “Adoecimento” “Docente” e “Saúde Docente”’ foram as que alcançaram maior grau de centralidade nos grafos apresentados, mantendo conexões com outras variáveis tais como Qualidade de Vida, Subjetividade, Depressão, denotando sua importância nas discussões que estão sendo empreendidas acerca do tema ora investigado, na literatura pertinente. The use of graphs in the social sciences has been increasingly representative, considering that this type of technique makes it possible to study the relationships between various objects or categories. The combined use of graphs with social networks provides an advance in the understanding of social phenomena. The present article aims to present and analyze the relationships found among 45 scientific articles dealing with the illness of the teacher, selected from the literature review technique, as well as the collaboration network between the authors and co - authors of the articles. After the application of the Content Analysis technique, the graphs were constructed with the help of the NodeXL tool, using the categories found in the articles. The variables Teaching Illness and Teaching Health were those that reached a greater degree of centrality in the presented graphs, maintaining connections with other variables such as Quality of Life, Subjectivity, Depression, denoting their importance in the discussions that are being undertaken about the subject investigated, in the relevant literature.

Os atendimentos hospitalares são fundamentais para a população de uma região. As unidades básicas de saúde (US) analisadas nesta dissertação pertencem à rede pública e visam atender a população de menor renda que utiliza deslocamentos a pé ou por transporte público. Este trabalho tem por objetivo avaliar a acessibilidade das US da cidade de Curitiba considerando como origem os bairros de Curitiba e as US como destino. O método proposto baseia-se em indicadores para avaliar a acessibilidade da população considerando: (i) ofertas de pontos próximos às US, (ii) frequência dos ônibus e (iii) tempo de deslocamento até a US. Com o indicador distância identificam-se os pontos de ônibus localizados até 500m de uma US. O indicador frequência avalia o tempo de espera pela passagem de um ônibus nas paradas próximas às US. Os resultados mostram que 97% das US têm boa acessibilidade. O tempo médio de espera por ônibus nas paradas é regular, enquanto que apenas 8% das linhas foram classificadas como boas (com intervalo de tempo inferior a 15 minutos). Finalmente a partir da relação entre renda da população e tempo de viagem dos bairros até uma US dentro da regional, foi proposto um modelo de detecção de “outliers” para identificar os bairros com maior vulnerabilidade, que devem ser priorizados em termos de investimentos públicos ou ajustes na rede de transporte. Hospital services are essential for the population of a region. The basic healthcare units (HU) considered in this work are part of public healthcare services. They aim to assist the lower income population which usually reaches these units by walking or by means of public transport. This work aims to evaluate the accessibility of Curitiba healthcare units considering neighborhoods as origins and HU as destinations. The proposed method is based on indicators to assess the accessibility of population considering: (i) offers of points close to HU, (ii) Frequency of buses and (iii) time of displacement to HU. With the distance indicator is evaluated if the health facilities are located within 500m of a bus stop. The frequency indicator measures the waiting time for a bus at stops near the US. Results show that 97% of the HU have good accessibility. The average bus waiting time at the stops is regular, but 8% of lines were rated as good (with time interval lower than 15 minutes). Finally, from the relationship between population income and neighborhood travel time to a HU within the regional area, an outlier detection model was proposed to identify the most vulnerable neighborhoods, that should be prioritized for public investment or adjustment in the transport network.

Planejamento de rotas é um desafio para a computação urbana que, de maneira geral, envolve o processamento de uma grande quantidade de dados, além do feedback dos usuários. Tradicionalmente, os serviços de planejamento de rota são baseados em ruas, isto é, mesmo um caminho para um pedestre ´e fornecido utilizando ruas. Entretanto, tais modelos não são adequados para usuários com certas deficiências. A fim de resolver tal problema, essa dissertação apresenta um modelo baseado em calcadas visando suprir as necessidades de um cadeirante por meio de um serviço de planejamento de rotas. O modelo ´e matematicamente definido como um grafo, em que os vértices são as esquinas e as arestas são as calcadas ou cruzamentos. Os custos de cada aresta são obtidos de diversos fatores como distância, inclinação e a condição/manutenção das rampas, cruzamentos e calçadas. O modelo foi pensado de maneira que o feedback do usuário fosse considerado durante a atualização de suas informações com dados de cadeirantes sobre problemas de acessibilidade e de problemas resolvidos pelo departamento de planejamento urbano da cidade. E apresentado ainda um algoritmo de planejamento de rotas que fornece um conjunto de rotas alternativas baseadas em condições de acessibilidade e um algoritmo de recomendação de atalhos para auxiliar a tomada de decisões pelo departamento de planejamento urbano da cidade. Além disso, foi desenvolvida uma API para o fornecimento dos serviços de caminho mínimo em calçadas. Experimentos, usando pgRouting e o PostGIS com dados abertos foram realizados em um bairro de uma cidade brasileira a fim de validar o modelo e o serviço de planejamento de rotas. Route planning is a challenging problem for urban computing that usually involves the processing of a huge amount of data and collaborative user feedback. Traditionally, route planning services are street-based, that is, even paths for a pedestrian are suggested in terms of streets. However such models are not suitable for users with certain disabilities. To address this problem, we describe in this dissertation a sidewalk-based model to accommodate the needs for a wheelchair route planning service. The model is mathematically defined as a graph, where the vertices are the city block corners and the edges are the sidewalks or crosswalks. The edge costs are derived from important accessibility features, such as distance, path inclination, and existence and maintenance conditions of curb ramps, crosswalks and sidewalks. The model has been organized such as the user feedback is considered to help updating the model when accessibility issues are detected, by wheelchair users and companions, or solved, by the department of city planning. We also present a route planning algorithm that provides a set of alternative routes based on accessibility conditions, and a shortcut recommender algorithm to support accessibility related decision making by the department of city planning. Besides, it was developed an API to provide shortest-path using sidewalks. Experiments, by using PgRouting and PostGIS with open data, are reported for a Brazilian city neighborhood in order to validate the model and the route planning service.