In this thesis, we will study several domination parameters of a family of graphs known as complementary prisms. We will first present the basic terminology and definitions necessary to understand the topic. Then, we will examine the known results addressing the domination number and the total domination number of complementary prisms. After this, we will present our main results, namely, results on the restrained domination number of complementary prisms. Subsequently results on the distance - k domination number, 2-step domination number and stratification of complementary prisms will be presented. Then, we will characterize when a complementary prism is Eulerian or bipartite, and we will obtain bounds on the chromatic number of a complementary prism. We will finish the thesis with a section on possible future problems.

Spectral clustering is often used to partition a data set into a specified number of clusters. Both the unweighted and the vertex-weighted approaches use eigenvectors of the Laplacian matrix of a graph. Our focus is on using vertex-weighted methods to refine clustering of observations. An eigenvector corresponding with the second smallest eigenvalue of the Laplacian matrix of a graph is called a Fiedler vector. Coefficients of a Fiedler vector are used to partition vertices of a given graph into two clusters. A vertex of a graph is classified as unassociated if the Fiedler coefficient of the vertex is close to zero compared to the largest Fiedler coefficient of the graph. We propose a vertex-weighted spectral clustering algorithm which incorporates a vector of weights for each vertex of a given graph to form a vertex-weighted graph. The proposed algorithm predicts association of equidistant or nearly equidistant data points from both clusters while the unweighted clustering does not provide association. Finally, we implemented both the unweighted and the vertex-weighted spectral clustering algorithms on several data sets to show that the proposed algorithm works in general.

This thesis aims to investigate the controllability and observability of the discrete fractional linear time-invariant state-space model. First, we will establish key concepts and properties which are the tools necessary for our task. In the third chapter, we will discuss the discrete state-space model and set up the criteria for these two properties. Then, in the fourth chapter, we will attempt to apply these criteria to the discrete fractional model. The general flow of our objectives is as follows: we start with the first-order linear difference equation, move on to the discrete system, then the fractional difference equation, and finally the discrete fractional system. Throughout this process, we will develop the solutions to the (fractional) difference equations, which are the basis of our criteria.

We study single-pursuer, line-of-sight Pursuit and Evasion games in polytopes in $\mathbb{R}^n$. We develop winning Pursuer strategies for simple classes of polytopes (monotone prisms) in Rn, using proven algorithms for polygons as inspiration and as subroutines. More generally, we show that any Pursuer-win polytope can be extended to a new Pursuer-win polytope in more dimensions. We also show that some more general classes of polytopes (monotone products) do not admit a deterministic winning Pursuer strategy. Though we provide bounds on which polytopes are Pursuer-win, these bounds are not tight. Closing the gap between those polytopes known to be Pursuer-win and those known not to be remains an problem for future researchers.

Ce mémoire résume une quinzaine d'années de recherche dans le monde industriel et universitaire. Il est divisé en trois parties, traitant respectivement de la théorie de la morphologie mathématique, des systèmes dynamiques et enfin des applications au traitement des images. En morphologie mathématique, nos travaux ont porté principalement sur le filtrage et la segmentation d'images. En ce qui concerne le filtrage, nous avons proposé un algorithme quasi-linéaire pour calculer l'arbre des composantes, une des structures d'organisation naturelles des ensembles de niveaux d'une image. En segmentation, nous nous sommes principalement intéressé à la ligne de partage des eaux. Nous en avons proposé une définition continue. En nous servant du formalisme récemment introduit par Gilles Bertrand, nous avons comparé les propriétés de plusieurs définitions discrètes et nous avons proposé un algorithme quasi-linéaire permettant de calculer la ligne de partage des eaux topologique. Notre algorithme repose en partie sur celui de l'arbre des composantes. Enfin, nous avons proposé des schémas hiérarchiques pour utiliser la ligne de partage des eaux, et en particulier, nous avons proposé de valuer les contours produits par un critère de saillance donnant l'importance du contour dans la hiérarchie. Ces études nous ont conduit à proposer des classes de graphes adaptés pour la fusion de région, mettant en particulier en évidence l'équivalence existant entre une de ces classes de graphes et la classe des graphes pour lesquels toute ligne de partage des eaux binaire est mince. En ce qui concerne les systèmes dynamiques, nous avons utilisé les outils issus du cadre de l'analyse multivoque et de la théorie de la viabilité pour proposer un algorithme (dit des "Montagnes Russes") qui permet de converger vers le minimum global d'une fonction dont on connaît l'infimum. L'association du cadre algébrique des treillis complets, de l'algèbre et de la théorie des inclusions différentielles nous a permis de donner des propriétés algébriques et de continuité d'applications agissant sur des ensembles fermés, comme l'ensemble atteignable ou le noyau de viabilité. Nous avons utilisé le cadre des équations mutationnelles, permettant de dériver des tubes de déformations de formes dans des espaces métriques, pour prouver de manière rigoureuse et sans hypothèse de régularité sur la forme, l'intuition selon laquelle la dilatation transforme la forme dans la direction des normales à celle-ci en chacun de ses points. Nous avons adapté au cadre des équations mutationnelles le théorème d'Euler, qui permet d'approcher une solution à une équation mutationnelle par une s'equence de points dans un espace métrique. Enfin, nous avons proposé une approche générique de simulation, fondée sur les systèmes de particules, qui a prouvé son efficacité par sa mise en œuvre en milieu industriel, en particulier, pour la simulation de foules, pour la synthèse d'images, ou encore pour la simulation du déploiement d'airbags. Nous pensons que de bonnes études théoriques aident à réaliser des applications de qualité. Inversement, de bons problèmes théoriques peuvent trouver une source dans de bons problèmes applicatifs. On trouvera dans ce mémoire le résumé d'un certain nombre de travaux dont l'intérêt industriel a été prouvé par des brevets ou des logiciels. Citons par exemple un outil de segmentation 4D (3D+temps) en imagerie cardiaque utilisé par des médecins dans le cadre de leur pratique. Nous avons travaillé pendant plusieurs années dans le domaine du traitement d'images de documents. Nous avons proposé un outil basé sur la morphologie mathématique permettant d'estimer l'angle d'inclinaison d'un document scanné. Plus particulièrement, nous avons étudié des problèmes liés à l'indexation et à la reconnaissance de dessins techniques.

Cette thèse présente l'ensemble des concepts mathématiques et de Génie Logiciel ayant servi à la réalisation d'un cahier de brouillon interactif pour la théorie des graphes : Cabri-graphes.

Nous nous intéressons dans cette thèse à différents types de réseaux (optiques, sans-fil, pair-à-pair) ayant chacun leurs spécificités mais partageant des problématiques communes : assurer la meilleure qualité de services possible, garantir la stabilité du système, minimiser les ressources et donc le coût de fonctionnement. Tout d'abord, nous étudions le problème de la reconfiguration du routage dans les réseaux optiques consistant à rerouter les requêtes de connexion en minimisant les perturbations pour les utilisateurs. Puis, nous nous intéressons au problème de la détermination de routages efficaces en énergie dans les réseaux coeur. Pour ce faire, nous étudions le problème de trouver des routages minimisant le nombre d'équipements utilisés. Ensuite, nous nous intéressons aux algorithmes d'ordonnancement des liens dans les réseaux sans-fil en présence d'interférence. Enfin, nous considérons le problème de stockage de données dans les réseaux pair-à-pair. Nous étudions l'impact de différentes politiques de placement sur la durée de vie des données et nous déterminons un choix de placement optimal. Pour résoudre ces problèmes, nous utilisons les outils théoriques des mathématiques discrètes (graphes, configurations, optimisation combinatoire), d'algorithmique (complexité, algorithmique distribuée) et de probabilités.

In this thesis we present and solve selected problems arising from digital geometry and combinatorics on words. We consider digital straight lines and, equivalently, upper mechanical words with positive irrational slopes a<1 and intercept 0. We formulate a continued fraction (CF) based description of their run-hierarchical structure. Paper I gives a theoretical basis for the CF-description of digital lines. We define for each irrational positive slope less than 1 a sequence of digitization parameters which fully specifies the run-hierarchical construction. In Paper II we use the digitization parameters in order to get a description of runs using only integers. We show that the CF-elements of the slopes contain the complete information about the run-hierarchical structure of the line. The index jump function introduced by the author indicates for each positive integer k the index of the CF-element which determines the shape of the digitization runs on level k. In Paper III we present the results for upper mechanical words and compare our CF-based formula with two well-known methods, one of which was formulated by Johann III Bernoulli and proven by Markov, while the second one is known as the standard sequences method. Due to the special treatment of some CF-elements equal to 1 (essential 1's in Paper IV), our method is currently the only one which reflects the run-hierarchical structure of upper mechanical words by analogy to digital lines. In Paper IV we define two equivalence relations on the set of all digital lines with positive irrational slopes a<1. One of them groups into classes all the lines with the same run length on all digitization levels, the second one groups the lines according to the run construction in terms of long and short runs on all levels. We analyse the equivalence classes with respect to minimal and maximal elements. In Paper V we take another look at the equivalence relation defined by run construction, this time independently of the context, which makes the results more general. In Paper VI we define a run-construction encoding operator, by analogy with the well-known run-length encoding operator. We formulate and present a proof of a fixed-point theorem for Sturmian words. We show that in each equivalence class under the relation based on run length on all digitization levels (as defined in Paper IV), there exists exactly one fixed point of the run-construction encoding operator.

HTML clipboard Statistical physics seeks to explain macroscopic properties of matter in terms of microscopic interactions. Of particular interest is the phenomenon of phase transition: the sudden changes in macroscopic properties as external conditions are varied. Two models in particular are of great interest to mathematicians, namely the Ising model of a magnet and the percolation model of a porous solid. These models in turn are part of the unifying framework of the random-cluster representation, a model for random graphs which was first studied by Fortuin and Kasteleyn in the 1970’s. The random-cluster representation has proved extremely useful in proving important facts about the Ising model and similar models. In this work we study the corresponding graphical framework for two related models. The first model is the transverse field quantum Ising model, an extension of the original Ising model which was introduced by Lieb, Schultz and Mattis in the 1960’s. The second model is the space–time percolation process, which is closely related to the contact model for the spread of disease. In Chapter 2 we define the appropriate space–time random-cluster model and explore a range of useful probabilistic techniques for studying it. The space– time Potts model emerges as a natural generalization of the quantum Ising model. The basic properties of the phase transitions in these models are treated in this chapter, such as the fact that there is at most one unbounded fk-cluster, and the resulting lower bound on the critical value in <img src="http://upload.wikimedia.org/math/a/b/8/ab820da891078a8245d7f4f3252aee4f.png" />. In Chapter 3 we develop an alternative graphical representation of the quantum Ising model, called the random-parity representation. This representation is based on the random-current representation of the classical Ising model, and allows us to study in much greater detail the phase transition and critical behaviour. A major aim of this chapter is to prove sharpness of the phase transition in the quantum Ising model—a central issue in the theory— and to establish bounds on some critical exponents. We address these issues by using the random-parity representation to establish certain differential inequalities, integration of which gives the results. In Chapter 4 we explore some consequences and possible extensions of the results established in Chapters 2 and 3. For example, we determine the critical point for the quantum Ising model in <img src="http://upload.wikimedia.org/math/a/b/8/ab820da891078a8245d7f4f3252aee4f.png" /> and in ‘star-like’ geometries. / HTML clipboard Statistisk fysik syftar till att förklara ett materials makroskopiska egenskaper i termer av dess mikroskopiska struktur. En särskilt intressant egenskap är är fenomenet fasövergång, det vill säga en plötslig förändring i de makroskopiska egenskaperna när externa förutsättningar varieras. Två modeller är särskilt intressanta för en matematiker, nämligen Ising-modellen av en magnet och perkolationsmodellen av ett poröst material. Dessa två modeller sammanförs av den så-kallade fk-modellen, en slumpgrafsmodell som först studerades av Fortuin och Kasteleyn på 1970-talet. fk-modellen har sedermera visat sig vara extremt användbar för att bevisa viktiga resultat om Ising-modellen och liknande modeller. I den här avhandlingen studeras den motsvarande grafiska strukturen hos två näraliggande modeller. Den första av dessa är den kvantteoretiska Isingmodellen med transverst fält, vilken är en utveckling av den klassiska Isingmodellen och först studerades av Lieb, Schultz och Mattis på 1960-talet. Den andra modellen är rumtid-perkolation, som är nära besläktad med kontaktmodellen av infektionsspridning. I Kapitel 2 definieras rumtid-fk-modellen, och flera probabilistiska verktyg utforskas för att studera dess grundläggande egenskaper. Vi möter rumtid-Potts-modellen, som uppenbarar sig som en naturlig generalisering av den kvantteoretiska Ising-modellen. De viktigaste egenskaperna hos fasövergången i dessa modeller behandlas i detta kapitel, exempelvis det faktum att det i fk-modellen finns högst en obegränsad komponent, samt den undre gräns för det kritiska värdet som detta innebär. I Kapitel 3 utvecklas en alternativ grafisk framställning av den kvantteoretiska Ising-modellen, den så-kallade slumpparitetsframställningen. Denna är baserad på slumpflödesframställningen av den klassiska Ising-modellen, och är ett verktyg som låter oss studera fasövergången och gränsbeteendet mycket närmare. Huvudsyftet med detta kapitel är att bevisa att fasövergången är skarp—en central egenskap—samt att fastslå olikheter för vissa kritiska exponenter. Metoden består i att använda slumpparitetsframställningen för att härleda vissa differentialolikheter, vilka sedan kan integreras för att lägga fast att gränsen är skarp. I Kapitel 4 utforskas några konsekvenser, samt möjliga vidareutvecklingar, av resultaten i de tidigare kapitlen. Exempelvis bestäms det kritiska värdet hos den kvantteoretiska Ising-modellen på <img src="http://upload.wikimedia.org/math/a/b/8/ab820da891078a8245d7f4f3252aee4f.png" /> , samt i ‘stjärnliknankde’ geometrier. / QC 20100705

Nous étudions les fonctions sommatoires des suites digitales. Ces suites sont obtenues en "promenant une fenêtre" sur le développement des entiers en base q, et sont une sous- classe des suites q-régulières. Le comportement asymptotique des fonctions sommatoires est précisé, avec la mise en évidence d'une oscillation "fractale", qui fait intervenir une fonction continue nulle part dérivable. Dans la dernière partie nous nous intéressons à des suites d'entiers à la Cantor, qui s'écrivent dans une base donnée en évitant certains chiffres.