Classical mechanics provides a phase space representation of mechanical systems in terms of position and momentum state variables. The Hamiltonian system, a set of partial differential equations, defines a vector field in phase space and uniquely determines the evolutionary process of the system given its initial state.A closed form solution describing system trajectories in phase space is only possible if the system of differential equations defining the Hamiltonian is linear. For nonlinear cases approximate and qualitative methods are required.Generalized phase space methods do not confine state variables to position and momentum, allowing other observables to describe the system. Such a generalization adjusts the description of the system to the required information and provides a method for studying physical systems that are not strictly mechanical.This thesis presents and uses the methods of generalized phase space to compare linear to nonlinear systems.Ball State UniversityMuncie, IN 47306 / Department of Physics and Astronomy

Spectral graph theory is the interplay between linear algebra and combinatorial graph theory. Laplace’s equation and its discrete form, the Laplacian matrix, appear ubiquitously in mathematical physics. Due to the recent discovery of very fast solvers for these equations, they are also becoming increasingly useful in combinatorial optimization, computer vision, computer graphics, and machine learning. In this thesis, we develop highly efficient and parallelizable algorithms for solving linear systems involving graph Laplacian matrices. These solvers can also be extended to symmetric diagonally dominant matrices and M-matrices, both of which are closely related to graph Laplacians. Our algorithms build upon two decades of progress on combinatorial preconditioning, which connects numerical and combinatorial algorithms through spectral graph theory. They in turn rely on tools from numerical analysis, metric embeddings, and random matrix theory. We give two solver algorithms that take diametrically opposite approaches. The first is motivated by combinatorial algorithms, and aims to gradually break the problem into several smaller ones. It represents major simplifications over previous solver constructions, and has theoretical running time comparable to sorting. The second is motivated by numerical analysis, and aims to rapidly improve the algebraic connectivity of the graph. It is the first highly efficient solver for Laplacian linear systems that parallelizes almost completely. Our results improve the performances of applications of fast linear system solvers ranging from scientific computing to algorithmic graph theory. We also show that these solvers can be used to address broad classes of image processing tasks, and give some preliminary experimental results.

GraphCards is a research project devoted to the development of a system for learning graph theory and implementing graph algorithms. It contains an information base for learning and referencing graph theory topics, integrated with an experimentation tool set to create and manipulate graphs. Due to the non-linear relationship of the information, its organization is hypertext based. The hypertext system NoteCards 1 is used to develop the application.The contribution of the current project is to complete and improve an existing system by reclassifying and rewriting the textual information into different chunks called "typed cards". This should serve to enhance the organization and make the traversal by the user easier.This project will also contribute to the development of an interface between the Information Base and the Graph Experimentation Tool Set. / Department of Computer Science

The main focus of this research is to use graph-theoretic formulations to develop an automated algorithm for the generation of sensitivity equations. The idea is to combine the benefits of direct differentiation with that of graph-theoretic formulation. The primary deliverable of this work is the developed software module which can derive the system equations and the sensitivity equations directly from the linear graph of the system. Sensitivity analysis refers to the study of changes in system behaviour brought about by the changes in model parameters. Due to the rapid increase in the sizes and complexities of the models being analyzed, it is important to extend the capabilities of the current tools of sensitivity analysis, and an automated, efficient, and accurate method for the generation of sensitivity equations is highly desirable. In this work, a graph-theoretic algorithm is developed to generate the sensitivity equations. In the current implementation, the proposed algorithm uses direct differentiation to generate sensitivity equations at the component level and graph-theoretic methods to assemble the equation fragments to form the sensitivity equations. This way certain amount of control can be established over the size and complexity of the generated sensitivity equations. The implementation of the algorithm is based on a commercial software package \verb MapleSim[Multibody] and can generate governing and sensitivity equations for multibody models created in MapleSim. In this thesis, the algorithm is tested on various mechanical, hydraulic, electro-chemical, multibody, and multi-domain systems. The generated sensitivity information are used to perform design optimization and parametric importance studies. The sensitivity results are validated using finite difference formulations. The results demonstrate that graph-theoretic sensitivity analysis is an automated, accurate, algorithmic method of generation for sensitivity equations, which enables the user to have some control over the form and complexity of the generated equations. The results show that the graph-theoretic method is more efficient than the finite difference approach. It is also demonstrated that the efficiency of the generated equations are at par or better than the equation obtained by direct differentiation.

If R is a list of positive integers with greatest common denominator equal to 1, calculating the Frobenius number of R is in general NP-hard. Dino Lorenzini defines the arithmetical graph, which naturally arises in arithmetic geometry, and a notion of genus, the g-number, that in specific cases coincides with the Frobenius number of R. A result of Dino Lorenzini's gives a method for quickly calculating upper bounds for the g-number of arithmetical graphs. We discuss the arithmetic geometry related to arithmetical graphs and present an example of an arithmetical graph that arises in this context. We also discuss the construction for Lorenzini's Riemann-Roch structure and how it relates to the Riemann-Roch theorem for finite graphs shown by Matthew Baker and Serguei Norine. We then focus on the connection between the Frobenius number and arithmetical graphs. Using the Laplacian of an arithmetical graph and a formulation of chip-firing on the vertices of an arithmetical graph, we show results that can be used to find arithmetical graphs whose g-numbers correspond to the Frobenius number of R. We describe how this can be used to quickly calculate upper bounds for the Frobenius number of R.

In discrete mathematics, a convex space is an ordered pair (V,M) where M is a family of subsets of a finite set V , such that: ∅ ∈M, V ∈M, andMis closed under intersection. The elements of M are called convex sets. For a set S ⊆ V , the convex hull of S is the smallest convex set that contains S. A point x of a convex set X is an extreme point of X if X\{x} is also convex. A convex space (V,M) with the property that every convex set is the convex hull of its extreme points is called a convex geometry. A graph G has a P-elimination ordering if an ordering v1, v2, ..., vn of the vertices exists such that vi has property P in the graph induced by vertices vi, vi+1, ..., vn for all i = 1, 2, ...,n. Farber and Jamison [18] showed that for a convex geometry (V,M), X ∈Mif and only if there is an ordering v1, v2, ..., vk of the points of V − X such that vi is an extreme point of {vi, vi+1, ..., vk}∪ X for each i = 1, 2, ...,k. With these concepts in mind, this thesis surveys the literature and summarizes results regarding graph convexities and elimination orderings. These results include classifying graphs for which different types of convexities give convex geometries, and classifying graphs for which different vertex ordering algorithms result in a P-elimination ordering, for P the characteristic property of the extreme points of the convexity. We consider the geodesic, monophonic, m3, 3-Steiner and 3-monophonic convexities, and the vertex ordering algorithms LexBFS, MCS, MEC and MCC. By considering LexDFS, a recently introduced vertex ordering algorithm of Corneil and Krueger [11], we obtain new results: these are characterizations of graphs for which all LexDFS orderings of all induced subgraphs are P-elimination orderings, for every characteristic property P of the extreme vertices for the convexities studied in this thesis. / Graduate / 0405 / rachela@uvic.ca

Spectral graph theory widely increases the interests in not only discovering new properties of well known graphs but also proving the well known properties for the new type of graphs. In fact all spectral properties of proverbial graphs are not acknowledged to us and in other hand due to the structure of nature, new classes of graphs are required to explain the phenomena around us and the spectral properties of these graphs can tell us more about the structure of them. These both themes are the body of our work here. We introduce here three models of random graphs and show that the eigenvalue counting function of Laplacians on these graphs has exponential decay bound. Since our methods heavily depend on the first nonzero eigenvalue of Laplacian, we study also this eigenvalue for the graph in both random and nonrandom cases.

A \emph{simple} $n$-\emph{Venn diagram} is a collection of $n$ simple intersecting closed curves in the plane where exactly two curves meet at any intersection point; the curves divide the plane into $2^n$ distinct open regions, each defined by its intersection of the interior or exterior of each of the curves. A Venn diagram is \emph{reducible} if there is a curve that, when removed, leaves a Venn diagram with one less curve and \emph{irreducible} if no such curve exists. A Venn diagram is \emph{extendible} if another curve can be added, producing a Venn diagram with one more curve. Currently it is not known whether every simple Venn diagram is extendible by the addition of another curve. We show that all simple Venn diagrams with $5$ curves or less are extendible to another simple Venn diagram. We also show that for certain Venn diagrams, a new extending curve is relatively easy to produce. We define a new type of diagram of simple closed curves where each curve divides the plane into an equal number of regions; we call such a diagram a \emph{face-balanced} diagram. We generate and exhibit all face-balanced diagrams up to and including those with $32$ regions; these include all the Venn diagrams. Venn diagrams exist where the curves are the perimeters of polyominoes drawn on the integer lattice. When each of the $2^n$ intersection regions is a single unit square, we call these \emph{minimum area polyomino Venn diagrams}, or \emph{polyVenns}. We show that polyVenns can be constructed and confined in bounding rectangles of size $2^r \times 2^c$ whenever $r, c \ge 2$ and $n=r+c$. We show this using two constructive proofs that extend existing diagrams. Finally, for even $n$, we construct polyVenns with $n$ polyominoes in $(2^{n/2} - 1) \times (2^{n/2} + 1)$ bounding rectangles in which the empty set is not represented as a unit square. / Graduate / 0405 / 0984 / bbultena@uvic.ca

In discrete mathematics, a convex space is an ordered pair (V,M) where M is a family of subsets of a finite set V , such that: ∅ ∈M, V ∈M, andMis closed under intersection. The elements of M are called convex sets. For a set S ⊆ V , the convex hull of S is the smallest convex set that contains S. A point x of a convex set X is an extreme point of X if X\{x} is also convex. A convex space (V,M) with the property that every convex set is the convex hull of its extreme points is called a convex geometry. A graph G has a P-elimination ordering if an ordering v1, v2, ..., vn of the vertices exists such that vi has property P in the graph induced by vertices vi, vi+1, ..., vn for all i = 1, 2, ...,n. Farber and Jamison [18] showed that for a convex geometry (V,M), X ∈Mif and only if there is an ordering v1, v2, ..., vk of the points of V − X such that vi is an extreme point of {vi, vi+1, ..., vk}∪ X for each i = 1, 2, ...,k. With these concepts in mind, this thesis surveys the literature and summarizes results regarding graph convexities and elimination orderings. These results include classifying graphs for which different types of convexities give convex geometries, and classifying graphs for which different vertex ordering algorithms result in a P-elimination ordering, for P the characteristic property of the extreme points of the convexity. We consider the geodesic, monophonic, m3, 3-Steiner and 3-monophonic convexities, and the vertex ordering algorithms LexBFS, MCS, MEC and MCC. By considering LexDFS, a recently introduced vertex ordering algorithm of Corneil and Krueger [11], we obtain new results: these are characterizations of graphs for which all LexDFS orderings of all induced subgraphs are P-elimination orderings, for every characteristic property P of the extreme vertices for the convexities studied in this thesis. / Graduate / 0405 / rachela@uvic.ca

The objective of this thesis is to develop decentralized methods for building robust multi-agent networks through self-organization. Multi-agent networks appear in a large number of natural and engineered systems, including but not limited to, biological networks, social networks, communication systems, transportation systems, power grids, and robotic swarms. Networked systems typically consist of numerous components that interact with each other to achieve some collaborative tasks such as flocking, coverage optimization, load balancing, or distributed estimation, to name a few. Multi-agent networks are often modeled via interaction graphs, where the nodes represent the agents and the edges denote direct interactions between the corresponding agents. Interaction graphs play a significant role in the overall behavior and performance of multi-agent networks. There- fore, graph theoretic analysis of networked systems has received a considerable amount of attention within the last decade. In many applications, network components are likely to face various functional or structural disturbances including, but not limited to, component failures, noise, or malicious attacks. Hence, a desirable network property is robustness, which is the ability to perform reasonably well even when the network is subjected to such perturbations. In this thesis, robustness in multi-agent networks is pursued in two parts. The first part presents a decentralized graph reconfiguration scheme for formation of robust interaction graphs. Particularly, the proposed scheme transforms any interaction graph into a random regular graph, which is robust to the perturbations of their nodes/links. The second part presents a decentralized coverage control scheme for optimal protection of networks by some mobile security resources. As such, the proposed scheme drives a group of arbitrarily deployed resources to optimal locations on a network in a decentralized fashion.