Bobbin lace is a 500-year-old art form in which threads are braided together in an alternating manner to produce a lace fabric. A key component in its construction is a small pattern, called a bobbin lace ground, that can be repeated periodically to fill a region of any size. In this thesis we present a mathematical model for bobbin lace grounds representing the structure as the pair (Δ(G), ζ (v)) where Δ(G) is a topological embedding of a 2-regular digraph, G, on a torus and ζ(v) is a mapping from the vertices of G to a set of braid words. We explore in depth the properties that Δ(G) must possess in order to produce workable lace patterns. Having developed a solid, logical foundation for bobbin lace grounds, we enumerate and exhaustively generate patterns that conform to that model. We start by specifying an equivalence relation and define what makes a pattern prime so that we can identify unique representatives. We then prove that there are an infinite number of prime workable patterns. One of the key properties identified in the model is that it must be possible to partition Δ(G) into a set of osculating circuits such that each circuit has a wrapping index of (1,0); that is, the circuit wraps once around the meridian of the torus and does not wrap around the longitude. We use this property to exhaustively generate workable patterns for increasing numbers of vertices in G by gluing together lattice paths in an osculating manner. Using a backtracking algorithm to process the lattice paths, we identify over 5 million distinct prime patterns. This is well in excess of the roughly 1,000 found in lace ground catalogues. The lattice paths used in our approach are members of a family of partially directed lattice paths that have not been previously reported. We explore these paths in detail, develop a recurrence relation and generating function for their enumeration and present a bijection between these paths and a subset of Motzkin paths. Finally, to draw out of the extremely large number of patterns some of the more aesthetically interesting cases for lacemakers to work on, we look for examples that have a high degree of symmetry. We demonstrate, by computational generation, that there are lace ground representatives from each of the 17 planar periodic symmetry groups. / Graduate / 0389 / 0984 / 0405 / veronikairvine@gmail.com

Orientador: Érika Capelato / Banca: Thiago de Melo / Banca: Camila Fernanda Bassetto / Resumo: Neste trabalho estudamos a Teoria dos Grafos compreendendo suas definições, resultados e algumas aplicações como O Problema das Pontes de Köningsberg, O Problema Chinês do Carteiro, O Problema do Caixeiro Viajante e O Teorema das Quatro e das Cinco Cores. Com o uso da Coleção M3 - Matemática Multimídia, que contém recursos educacionais em formatos digitais, aplicamos as atividades sugeridas aos alunos do segundo ano do Ensino Médio de uma escola particular localizado na cidade de São Pedro - SP. As atividades mostraram que, apesar da Teoria dos Grafos não constar no currículo regular do Ensino Médio, sua aplicação para este grupo de alunos foi positiva, uma vez que os alunos sentiram-se motivados com o conteúdo abordado na forma digital e com sua aplicação ao estudo de Matrizes. Concluímos assim que, nos dias atuais a ligação do processo de ensino aprendizagem com os softwares educacionais podem proporcionar, tanto para os professores quanto para os alunos, uma forma mais prazerosa e eficaz de obter conhecimento em Matemática / Abstract: In this work, we study Graph Theory, meaning its definitions, results e some applications such as the Köningsberg bridge problem, the chinese postman problem, the travelling salesman problem and the four color theorem as well as the five color theorem. By using the M3 - Matemática Multimídia Series, which contains educational resources in digital form, we applied the suggested activities to second year high school students form a private school located at the city of São Pedro - São Paulo State. The activities showed that, although Graph Theory is not part of the high school regular curriculum, its application to this group of students was positive, since the students felt themselves motivated by the digital approach to its contents and its applications to the study of Matrices. We conclude that, nowadays, the connection between the teaching processes and educational softwares can provide, to the teachers as well as to the students, a more pleasurable and efficient way to obtain knowledge in Mathematics / Mestre

The topological entropy of a continuous map quantifies the amount of chaos observed in the map. In this dissertation we present computational methods which enable us to compute topological entropy for given time series data generated from a continuous map with a transitive attractor. A triangulation is constructed in order to approximate the attractor and to construct a multivalued map that approximates the dynamics of the linear interpolant on the triangulation. The methods utilize simplicial homology and in particular the Lefschetz Fixed Point Theorem to establish the existence of periodic orbits for the linear interpolant. A semiconjugacy is formed with a subshift of nite type for which the entropy can be calculated and provides a lower bound for the entropy of the linear interpolant. The dissertation concludes with a discussion of possible applications of this analysis to experimental time series. / by Mark Wess. / Thesis (Ph.D.)--Florida Atlantic University, 2008. / Includes bibliography. / Electronic reproduction. Boca Raton, Fla., 2008. Mode of access: World Wide Web.

This dissertation studies two independent problems, one is about graph labeling and the other problem is related to connectivity condition in a simple graph. Graph labeling is a rapidly developing area of research in graph theory, having connections with a variety of application-oriented areas such as VLSI optimization, data structures and data representation. Furthermore, the connectivity conditions in a simple graphs may help us to study the new aspects of ad hoc networks, social networks and web graphs. In chapter 2, we study path systems, reduced path systems and how to construct a super edge-graceful tree with any number of edges using path systems. First, we give an algorithm to reduce a labeled path system to a smaller labeled path system of a different type. First, we investigate the cases (m, k) = (3; 5) and (m, k) = (4; 7), where m is the number of paths and 2k is the length of each path, and then we give a generalization for any k, m = 3 and m = 4. We also describe a procedure to construct a super-edge-graceful tree with any number of edges. / Includes bibliography. / Dissertation (Ph.D.)--Florida Atlantic University, 2014. / FAU Electronic Theses and Dissertations Collection

Arid regions tend to take careful measures to ensure water supplies are secured to consumers, to help provide the basis for further development. The distribution network is the most expensive part of the water supply infrastructure and it must maintain performance during unexpected incidents. Many aspects of performance have previously been discussed separately, including reliability, vulnerability, flexibility and resilience. This study aimed to develop a framework to bring together these aspects as found in the literature and industry practice, and bridge the gap between them. Semi-structured interviews with water industry experts were used to examine the presence and understanding of robustness factors. Thematic analysis was applied to investigate these and inform a conceptual framework including the component and topological levels. Robustness was described by incorporating network reliability and resiliency. The research focused on resiliency as a network-level concept derived from flexibility and vulnerability. To utilise this new framework, the study explored graph theory to formulate metrics for flexibility and vulnerability that combine network topology and hydraulics. The flexibility metric combines hydraulic edge betweenness centrality, representing hydraulic connectivity, and hydraulic edge load, measuring utilised capacity. Vulnerability captures the impact of failures on the ability of the network to supply consumers, and their sensitivity to disruptions, by utilising node characteristics, such as demand, population and alternative supplies. These measures together cover both edge (pipe) centric and node (demand) centric perspectives. The resiliency assessment was applied to several literature benchmark networks prior to using a real case network. The results show the benefits of combining hydraulics with topology in robustness analysis. The assessment helps to identify components or sections of importance for future expansion plans or maintenance purposes. The study provides a novel viewpoint overarching the gap between literature and practice, incorporating different critical factors for robust performance.

Relações min-max são objetos centrais em otimização combinatória. Elas basicamente afirmam que, numa dada estrutura, o valor ótimo de um certo problema de minimização é igual ao valor ótimo de um outro problema de maximização. Relações desse tipo fornecem boas caracterizações e descrições poliédricas para diversos problemas importantes, além de geralmente virem acompanhadas de algoritmos eficientes para os problemas em questão. Muitas vezes, tais algoritmos eficientes são obtidos naturalmente das provas construtivas dessas relações; mesmo quando isso não ocorre, essas relações revelam o suficiente sobre a estrutura combinatória dos problemas, levando ao desenvolvimento de algoritmos eficientes. O foco principal desta dissertação é o estudo dessas relações em grafos. Nossa ênfase é sobre grafos orientados. Apresentamos o poderoso arcabouço poliédrico de Edmonds e Giles envolvendo fluxos submodulares, bem como o algoritmo de Frank para um caso especial desse arcabouço: o teorema de Lucchesi-Younger. Derivamos também diversas relações min-max sobre o empacotamento de conectores, desde o teorema de ramificações disjuntas de Edmonds até o teorema de junções disjuntas de Feofiloff-Younger e Schrijver. Apresentamos também uma resenha completa sobre as conjecturas de Woodall e sua versão capacitada, conhecida como conjectura de Edmonds-Giles. Derivamos ainda algumas relações min-max clássicas sobre emparelhamentos, T-junções e S-caminhos. Para tanto, usamos um teorema de Frank, Tardos e Sebö e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour. Ao longo do texto, ilustramos vários aspectos recorrentes, como o uso de ferramentas da combinatória poliédrica, a técnica do descruzamento, o uso de funções submodulares, matróides e propriedades de troca, bem como alguns resultados envolvendo subestruturas proibidas. / Min-max relations are central objects in combinatorial optimization. They basically state that, in a given structure, the optimum value of a certain minimization problem equals the optimum value of a different, maximization problem. Relations of this kind provide good characterizations and polyhedral descriptions to several important problems and, moreover, they often come with efficient algorithms for the corresponding problems. Usually, such efficient algorithms are obtained naturally from the constructive proofs involved; even when that is not the case, these relations reveal enough of the combinatorial structure of the problem, leading to the development of efficient algorithms. The main focus of this dissertation is the study of these relations in graphs. Our emphasis is on directed graphs. We present Edmonds and Giles\' powerful polyhedral framework concerning submodular flows, as well as Frank\'s algorithm for a special case of this framework: the Lucchesi-Younger Theorem. We also derive several min-max relations about packing connectors, starting with Edmonds\' Disjoint Branchings Theorem and ending with Feofiloff-Younger and Schrijver\'s Disjoint Dijoins Theorem. We further derive some classical min-max relations on matchings, T-joins and S-paths. To this end, we use a theorem due to Frank, Tardos, and Sebö and a general framework due to Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour. Throughout the text, we illustrate several recurrent themes, such as the use of tools from polyhedral combinatorics, the uncrossing technique, the use of submodular functions, matroids and exchange properties, as well as some results involving forbidden substructures.

Besides finding changing areas based on the number of node and edge evolutions, a more interesting problem is to analyze the impact of these evolutions to graphs and find the regions that exhibit significant changes when these evolutions happen. The more different the relationship between nodes in a certain region is, the more significant this region is. This problem is challenging since it is hard to define the range of changing regions that is closely related to actual evolutions. We formalize the problem by using a similarity measure based on neighborhood random walks, and design an efficient algorithm which is able to identify the significant changing regions without recomputing all similarities. Meaningful examples in experiments demonstrate the effectiveness of our algorithms. / Graph patterns are able to represent the complex structural relations among objects in many applications in various domains. Managing and mining graph data, on which we study in this thesis, are no doubt among the most important tasks. We focus on two challenging problems, namely, graph summarization and graph change detection. / In the area of summarizing a collection of graphs, we study the problem of summarizing frequent subgraphs, since it is not much necessary to summarize a collection of random graphs. The bottleneck for exploring and understanding frequent subgraphs is that they are numerous. A summary can be a solution to this issue, so the goal of frequent subgraph summarization is to minimize the restoration errors of the structure and the frequency information. The unique challenge in frequent subgraph summarization comes from the fact that a subgraph can have multiple embeddings in a summarization template graph. We handle this issue by introducing a partial order between edges to allow accurate structure and frequency estimation based on an independence probabilistic model. The proposed algorithm discovers k summarization templates in a top-down fashion to control the restoration error of frequencies within sigma. There is no restoration error of structures. Experiments on both real and synthetic graph datasets show that our framework can control the frequency restoration error within 10% by a compact summarization model. / The objective of graph change detection is to discover the changing areas on graphs when they evolves at a high speed. The most changing areas are those areas having the highest number of evolutions (additions/deletions) of nodes and edges, which is called burst areas. We study on finding the most burst areas in a stream of fast graph evolutions. We propose to use Haar wavelet tree to monitor the upper bound of the number of evolutions. Our approach monitors all potential changing areas of different sizes and computes incrementally the number of evolutions in those areas. The top-k burst areas are returned as soon as they are detected. Our solution is capable of handling a large amount of evolutions in a short time, which is consistent to the experimental results. / The objective of graph summarization is to obtain a concise representation of a single large graph or a collection of graphs, which is interpretable and suitable for analysis. A good summary can reveal the hidden relationships between nodes in a graph. The key issue of summarizing a single graph is how to construct a high-quality and representative summary, which is in the form of a super-graph. We propose an entropy-based unified model for measuring the homogeneity of the super-graph. The best summary in terms of homogeneity could be too large to explore. By using the unified model, we relax three summarization criteria to obtain an approximate homogeneous summary of appropriate size. We propose both agglomerative and divisive algorithms for approximate summarization, as well as pruning techniques and heuristics for both algorithms to save computation cost. Experimental results confirm that our approaches can efficiently generate high-quality summaries. / Liu, Zheng. / Advisers: Wai Lam; Jeffrey Xu Yu. / Source: Dissertation Abstracts International, Volume: 73-06, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 133-141). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

by Tang Chi Nang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1995. / Includes bibliographical references (leaves 104-[109]). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Gaussian elimination --- p.2 / Chapter 1.1.1 --- Numerical stability --- p.2 / Chapter 1.2 --- Block Gaussian elimination --- p.3 / Chapter 1.2.1 --- Numerical stability --- p.4 / Chapter 1.3 --- Elimination graph --- p.4 / Chapter 1.4 --- Elimination ordering --- p.5 / Chapter 1.5 --- Computation and storage requirement --- p.6 / Chapter 1.6 --- Outline of the thesis --- p.7 / Chapter 2 --- Weighted graph elimination --- p.8 / Chapter 2.1 --- Weighted elimination graph --- p.8 / Chapter 2.2 --- Sparse Gaussian elimination --- p.9 / Chapter 2.3 --- Computation and storage requirement --- p.12 / Chapter 2.3.1 --- Computation requirement --- p.12 / Chapter 2.3.2 --- Storage requirement --- p.14 / Chapter 2.4 --- Elimination ordering --- p.15 / Chapter 2.5 --- Repeated structure --- p.18 / Chapter 3 --- Main theory --- p.21 / Chapter 3.1 --- Motivation --- p.21 / Chapter 3.2 --- Notations --- p.22 / Chapter 3.2.1 --- Connectivity --- p.23 / Chapter 3.2.2 --- Separator --- p.23 / Chapter 3.2.3 --- Equivalence --- p.24 / Chapter 3.3 --- Repetition separator --- p.25 / Chapter 3.4 --- Repetition elimination process --- p.30 / Chapter 3.5 --- Multiple Separators --- p.32 / Chapter 3.6 --- Feasibility --- p.33 / Chapter 3.6.1 --- Two-separator case --- p.34 / Chapter 3.6.2 --- General case --- p.39 / Chapter 3.6.3 --- Successive repetition elimination process (SREP) --- p.41 / Chapter 3.7 --- Generalized repetition elimination process --- p.42 / Chapter 3.7.1 --- Extra edges --- p.42 / Chapter 3.7.2 --- Acyclic edges --- p.43 / Chapter 3.7.3 --- Generalized repetition separator --- p.45 / Chapter 4 --- Application in queueing analysis --- p.52 / Chapter 4.1 --- Markov Chain Reduction Principle --- p.54 / Chapter 4.1.1 --- Numerical stability --- p.57 / Chapter 4.2 --- Multi-class MMPP/M/1/L queue --- p.57 / Chapter 4.2.1 --- Single-class case (QBD case) --- p.58 / Chapter 4.2.2 --- Preemptive LCFS case --- p.63 / Chapter 4.2.3 --- Non-preemptive LCFS case --- p.70 / Chapter 4.2.4 --- FCFS case --- p.72 / Chapter 4.2.5 --- Extension to phase type service time --- p.77 / Chapter 4.3 --- 2-class priority system --- p.77 / Chapter 5 --- Choosing the right algorithm --- p.85 / Chapter 5.1 --- MMPP/M/1/L system with bursty arrival --- p.86 / Chapter 5.1.1 --- Algorithm Comparison --- p.89 / Chapter 5.1.2 --- Numerical Examples --- p.90 / Chapter 5.2 2 --- -class priority system --- p.90 / Chapter 5.2.1 --- Algorithm Comparison --- p.95 / Chapter 5.2.2 --- Numerical Examples --- p.95 / Chapter 5.3 --- Conclusion --- p.95 / Chapter 6 --- Conclusion --- p.98 / Chapter 6.1 --- Further research --- p.99 / Chapter A --- List of frequently-used notations --- p.101 / Chapter A.l --- System of equations and Digraph --- p.101 / Chapter A.2 --- General-purpose functions --- p.102 / Chapter A.3 --- Single repetition separator --- p.102 / Chapter A.4 --- Sequence of repetition separators --- p.103 / Chapter A.5 --- Compatibility --- p.103 / Bibliography --- p.104

Human structural and functional brain architecture is increasingly studied by applying the mathematical framework of complex networks to data from magnetic resonance imaging. Connections (edges) in such brain networks are commonly constructed using correlations of features between pairs of brain regions, such as regional morphology (across participants) or neurophysiological time series (within participants). Subsequent analyses frequently focus on summary network statistics calculated using the strongest correlations, but often neglect potential underlying shifts within the correlation distribution. This thesis presents methods for the construction and analysis of correlation-derived structural and functional brain networks, focusing on the implications of changes within the correlation distribution. First, schizophrenia is considered as an example disease which is known to present a reduction in mean correlation between regional neurophysiological time series. Previous studies reported increased network randomisation in schizophrenia, but these results may have been driven by inclusion of a greater number of noisy edges in patients’ networks, based on retention of a fixed proportion of the strongest edges during network thresholding. Here, a novel probabilistic thresholding procedure is applied, based on the realisation that the strongest edges are not necessarily most likely to be true following adjustment of edge probabilities for effects of participant in-scanner motion. Probabilistically thresholded functional networks show decreased randomness, and increased consistency across participants. Further, applying probabilistic thresholding eliminates increased network randomisation in schizophrenia, supporting the hypothesis that previously reported group differences originated in the application of standard thresholding approaches to patient networks with decreased functional correlations. Subsequently, healthy adolescent development is studied, to help understand the frequent emergence of psychiatric disorders in this period. Importantly, both structural and functional brain networks undergo maturational shifts in correlation distribution over adolescence. Due to reliance of structural correlation networks on a group of subjects, previous studies of adolescent structural network development divided groups into discrete age-bins. Here, a novel sliding-window method is used to describe adolescent development of structural correlation networks in a continuous manner. Moreover, networks are probabilistically thresholded by retaining edges that are most consistent across bootstrapped samples of participants, leading to clearer maturational trajectories. These structural networks show non-linear trajectories of adolescent development driven by changes in association cortical areas, compatible with a developmental process of pruning combined with consolidation of surviving connections. Robustness of the results is demonstrated using extensive sensitivity analyses. Finally, adolescent developmental changes in functional network architecture are described, focusing on the characterisation of unthresholded (fully weighted) networks. The distribution of functional correlations presents a non-uniform shift over adolescence. Initially strong cortical connections to primary sensorimotor areas further strengthen into adulthood, whereas association cortical and subcortical edges undergo a subtler reorganisation of functional connectivity. Furthermore, individual subcortical regions show distinct maturational profiles. Patterning of maturation according to known functional systems is affirmed by partitioning regions developing at similar rates into maturational modules. Taken together, this thesis comprises novel methods for the characterisation of disease-related and normative developmental changes in structural and functional correlation brain networks. These methods are generalizable to a wide range of scenarios, beyond the specific disease and developmental age-ranges presented herein.

In today's Internet, with the advent of cloud computing, there is a natural desire for enterprises, organizations, and end users to outsource increasingly large amounts of data to a cloud provider. Therefore, ensuring security and privacy is becoming a significant challenge for cloud computing, especially for users with sensitive and valuable data. Recently, many efficient and scalable query processing methods over encrypted data have been proposed. Despite that, numerous challenges remain to be addressed due to the high complexity of many important queries on encrypted large-scale datasets. This thesis studies the problem of privacy-preserving database query processing on structured data (e.g., relational and graph databases). In particular, this thesis proposes several practical and provable secure structured encryption schemes that allow the data owner to encrypt data without losing the ability to query and retrieve it efficiently for authorized clients. This thesis includes two parts. The first part investigates graph encryption schemes. This thesis proposes a graph encryption scheme for approximate shortest distance queries. Such scheme allows the client to query the shortest distance between two nodes in an encrypted graph securely and efficiently. Moreover, this thesis also explores how the techniques can be applied to other graph queries. The second part of this thesis proposes secure top-k query processing schemes on encrypted relational databases. Furthermore, the thesis develops a scheme for the top-k join queries over multiple encrypted relations. Finally, this thesis demonstrates the practicality of the proposed encryption schemes by prototyping the encryption systems to perform queries on real-world encrypted datasets.