La conjecture de partitionnement des chemins

Soit G = (V, E) un graphe simple fini. Soit (a, b) un couple d’entiers positifs. On note par τ(G) le nombre de sommets d’un chemin d’ordre maximum dans G. Une partition (A,B) de V(G) est une (a,b)−partition si τ(⟨A⟩) ≤ a et τ(⟨B⟩) ≤ b. Si G possède une (a, b)−partition pour tout couple d’entiers positifs satisfaisant τ(G) = a+b, on dit que G est τ−partitionnable. La conjecture de partitionnement des chemins, connue sous le nom anglais de Path Partition Conjecture, cherche à établir que tout graphe est τ−partitionnable. Elle a été énoncée par Lovász et Mihók en 1981 et depuis, de nombreux chercheurs ont tenté de démontrer cette conjecture et plusieurs y sont parvenus pour certaines classes de graphes. Le présent mémoire rend compte du statut de la conjecture, en ce qui concerne les graphes non-orientés et ceux orientés.

Réseaux, homophilie et discours de collaboration scientifique au Québec : étude comparée sur le capital social des chercheurs junior et senior (1990-2009)

Notre étude porte sur la manière dont les chercheurs universitaires junior et senior en sciences sociales au Québec établissent leurs réseaux de cosignataires et donnent une interprétation discursive à leurs activités de collaboration face à l'impact du changement institutionnel universitaire pendant la période 1990-2009. Plus spécifiquement, notre recherche s'intéresse à montrer que la création des réseaux et la collaboration scientifique par cosignature peuvent être identifiées comme des « ajustements professionnels » et se présenter aussi comme une ressource du capital social qui peut être mobilisé et qui peut produire des avantages aux chercheurs en accord avec leur statut junior ou senior. Il s’agit donc d’une recherche qui relève de la sociologie des sciences. Notre approche a été opérationnalisée à partir de l'étude de 15 membres d'un centre de recherche universitaire au Québec, et leur réseau de 447 cosignataires (y compris les chercheurs de l'étude), et à travers l'application de 7 entretiens auprès de chercheurs junior et senior du même centre. Dans le même plan opérationnel, depuis une perspective qualitative, la thèse permet d'identifier le sens discursif que les chercheurs fournissent à la collaboration et à la participation en réseaux de cosignatures. Ensuite, depuis l'analyse structurelle des réseaux, notre étude montre les connexions individuelles et leurs formes d'interprétation — spécialement la théorie des graphes et ses mesures de centralité (la centralité de degré, la centralité d’intermédiarité et la centralité de vecteur propre) — de même que l'homophilie par statut entre chercheurs. Enfin, depuis l'analyse statistique, elle montre la corrélation des périodes de l'étude et des attributs socioprofessionnels des chercheurs étudiés (sexe, statut universitaire, affiliation institutionnelle, discipline d’appartenance, pays, région du Canada et ville de travail). Notamment, les résultats de notre thèse montrent que chaque catégorie de chercheurs possède ses propres particularités structurelles et discursives en ce qui a trait à ses pratiques de collaboration en réseau, et vont confirmer que les chercheurs senior, plus que les chercheurs junior, grâce à leur capital social mobilisé, ont conservé et obtenu plus d'avantages de leur réseau de cosignataires afin de s'adapter au changement institutionnel et mieux gérer leur travail de collaboration destiné à l’espace international, mais surtout à l'espace local.

Évaluation de l’effet de faux souvenirs en vieillissement normal : validation de scores composites des fonctions temporale médiane et frontale et contribution aux hypothèses théoriques

L’avancement en âge est associé à plusieurs modifications cognitives, dont un déclin des capacités à mémoriser et/ou à rappeler les événements vécus personnellement. Il amène parallèlement une augmentation des faux souvenirs, c.-à-d. le rappel d’événements qui ne se sont pas réellement déroulés. Les faux souvenirs peuvent avoir d’importantes répercussions dans la vie quotidienne des personnes âgées et il importe donc de mieux comprendre ce phénomène en vieillissement normal. Des études ont démontré l’importance de la fonction des lobes temporaux médians (FTM)/mémoire et de la fonction des lobes frontaux (FF)/fonctions exécutives dans l’effet de faux souvenirs. Ainsi, la première étude de la thèse visait à valider en français une version adaptée d’une méthode proposée par Glisky, Polster, & Routhieaux (1995), permettant de mesurer ces fonctions cognitives (Chapitre 2). L’analyse factorielle de cette étude démontre que les scores neuropsychologiques associés à la mémoire se regroupent en un facteur, le facteur FTM/mémoire, alors que ceux associés aux fonctions exécutives se regroupent en un deuxième facteur, le facteur FF/fonctions exécutives. Des analyses « bootstrap » effectuées avec 1 000 ré-échantillons démontrent la stabilité des résultats pour la majorité des scores. La deuxième étude de cette thèse visait à éclairer les mécanismes cognitifs (FTM/mémoire et FF/fonctions exécutives) ainsi que théoriques de l’effet de faux souvenirs accru en vieillissement normal (Chapitre 3). La Théorie des Traces Floues (TTF; Brainerd & Reyna, 1990) propose des explications de l’effet de faux souvenirs pour lesquelles la FTM/mémoire semble davantage importante, alors que celles proposées par la Théorie de l’Activation et du Monitorage (TAM; Roediger, Balota, & Watson, 2001) sont davantage reliées à la FF/fonctions exécutives. Les tests neuropsychologiques mesurant la FTM/mémoire ainsi que ceux mesurant la FF/fonctions exécutives ont été administrés à 52 participants âgés (moyenne de 67,81 ans). Basé sur l’étude de validation précédente, un score composite de la FTM/mémoire et un score composite de la FF/fonctions exécutives ont été calculés pour chaque participant. Ces derniers ont d’abord été séparés en deux sous-groupes, un premier au score FTM/mémoire élevé (n = 29, âge moyen de 67,45 ans) et un deuxième au score FTM/mémoire faible (n = 23, âge moyen de 68,26 ans) en s’assurant de contrôler statistiquement plusieurs variables, dont le score de la FF/fonctions exécutives. Enfin, ces participants ont été séparés en deux sous-groupes, un premier au score FF/fonctions exécutives élevé (n = 26, âge moyen 68,08 ans) et un deuxième au score FF/fonctions exécutives faible (n = 25, âge moyen de 67,36 ans), en contrôlant les variables confondantes, dont le score de la FTM/mémoire. Les proportions de vraie et de fausse mémoire (cibles et leurres associatifs) ont été mesurées à l’aide d’un paradigme Deese-Roediger et McDermott (DRM; Deese, 1959; Roediger & McDermott, 1995), avec rappel et reconnaissance jumelée à une procédure « Je me souviens / Je sais » (Tulving, 1985) chez les 52 participants âgés ainsi que chez 22 jeunes (âge moyen de 24,59 ans), apparié pour les années de scolarité. D’abord, afin de tester l’hypothèse de la TTF (Brainerd & Reyna, 1990), ces proportions ont été comparées entre les jeunes adultes et les deux sous-groupes de personnes âgées catégorisées selon le score de la FTM/mémoire. Ensuite, afin de tester l’hypothèse de la TAM (Roediger et al., 2001), ces proportions ont été comparées entre les jeunes adultes et les deux sous-groupes de personnes âgées catégorisées selon le score de la FF/fonctions exécutives. Il s’agit de la première étude qui compare directement ces hypothèses à travers de nombreuses mesures de vraie et de fausse mémoire. Les résultats démontrent que seule la FTM/mémoire modulait l’effet d’âge en vraie mémoire, et de manière quelque peu indirecte, en fausse mémoire et dans la relation entre la vraie et la fausse remémoration. Ensuite, les résultats démontrent que seule la FF/fonctions exécutives jouerait un rôle dans la fausse reconnaissance des leurres associatifs. Par ailleurs, en des effets d’âge sont présents en faux rappel et fausse remémorations de leurres associatifs, entre les jeunes adultes et les personnes âgées au fonctionnement cognitif élevé, peu importe la fonction cognitive étudiée. Ces résultats suggèrent que des facteurs autres que la FTM/mémoire et la FF/fonctions exécutives doivent être identifiés afin d’expliquer la vulnérabilité des personnes âgées aux faux souvenirs. Les résultats de cette thèse sont discutés à la lumière des hypothèses théoriques et cognitives en faux souvenirs (Chapitre 4).

Antimedian graphs

Antimedian graphs are introduced as the graphs in which for every triple of vertices there exists a unique vertex x that maximizes the sum of the distances from x to the vertices of the triple. The Cartesian product of graphs is antimedian if and only if its factors are antimedian. It is proved that multiplying a non-antimedian vertex in an antimedian graph yields a larger antimedian graph. Thin even belts are introduced and proved to be antimedian. A characterization of antimedian trees is given that leads to a linear recognition algorithm.

Studies on the Spectrum and the Energy of Graphs

Department of Mathematics, Cochin University of Science and Technology

CoObRA: Eine Plattform zur Verteilung und Replikation komplexer Objektstrukturen mit optimistischen Sperrkonzepten

In der vorliegenden Arbeit wird die Konzeption und Realisierung der Persistenz-, Verteilungs- und Versionierungsbibliothek CoObRA 2 vorgestellt. Es werden zunächst die Anforderungen an ein solches Rahmenwerk aufgenommen und vorhandene Technologien für dieses Anwendungsgebiet vorgestellt. Das in der neuen Bibliothek eingesetzte Verfahren setzt Änderungsprotokolle beziehungsweise -listen ein, um Persistenzdaten für Dokumente und Versionen zu definieren. Dieses Konzept wird dabei durch eine Abbildung auf Kontrukte aus der Graphentheorie gestützt, um die Semantik von Modell, Änderungen und deren Anwendung zu definieren. Bei der Umsetzung werden insbesondere das Design der Bibliothek und die Entscheidungen, die zu der gewählten Softwarearchitektur führten, eingehend erläutert. Dies ist zentraler Aspekt der Arbeit, da die Flexibilität des Rahmenwerks eine wichtige Anforderung darstellt. Abschließend werden die Einsatzmöglichkeiten an konkreten Beispielanwendungen erläutert und bereits gemachte Erfahrungen beim Einsatz in CASE-Tools, Forschungsanwendungen und Echtzeit-Simulationsumgebungen präsentiert.

Theoretical study of magnetism, structure and chemical order in transition-metal alloy clusters

Research on transition-metal nanoalloy clusters composed of a few atoms is fascinating by their unusual properties due to the interplay among the structure, chemical order and magnetism. Such nanoalloy clusters, can be used to construct nanometer devices for technological applications by manipulating their remarkable magnetic, chemical and optical properties. Determining the nanoscopic features exhibited by the magnetic alloy clusters signifies the need for a systematic global and local exploration of their potential-energy surface in order to identify all the relevant energetically low-lying magnetic isomers. In this thesis the sampling of the potential-energy surface has been performed by employing the state-of-the-art spin-polarized density-functional theory in combination with graph theory and the basin-hopping global optimization techniques. This combination is vital for a quantitative analysis of the quantum mechanical energetics. The first approach, i.e., spin-polarized density-functional theory together with the graph theory method, is applied to study the Fe$_m$Rh$_n$ and Co$_m$Pd$_n$ clusters having $N = m+n \leq 8$ atoms. We carried out a thorough and systematic sampling of the potential-energy surface by taking into account all possible initial cluster topologies, all different distributions of the two kinds of atoms within the cluster, the entire concentration range between the pure limits, and different initial magnetic configurations such as ferro- and anti-ferromagnetic coupling. The remarkable magnetic properties shown by FeRh and CoPd nanoclusters are attributed to the extremely reduced coordination number together with the charge transfer from 3$d$ to 4$d$ elements. The second approach, i.e., spin-polarized density-functional theory together with the basin-hopping method is applied to study the small Fe$_6$, Fe$_3$Rh$_3$ and Rh$_6$ and the larger Fe$_{13}$, Fe$_6$Rh$_7$ and Rh$_{13}$ clusters as illustrative benchmark systems. This method is able to identify the true ground-state structures of Fe$_6$ and Fe$_3$Rh$_3$ which were not obtained by using the first approach. However, both approaches predict a similar cluster for the ground-state of Rh$_6$. Moreover, the computational time taken by this approach is found to be significantly lower than the first approach. The ground-state structure of Fe$_{13}$ cluster is found to be an icosahedral structure, whereas Rh$_{13}$ and Fe$_6$Rh$_7$ isomers relax into cage-like and layered-like structures, respectively. All the clusters display a remarkable variety of structural and magnetic behaviors. It is observed that the isomers having similar shape with small distortion with respect to each other can exhibit quite different magnetic moments. This has been interpreted as a probable artifact of spin-rotational symmetry breaking introduced by the spin-polarized GGA. The possibility of combining the spin-polarized density-functional theory with some other global optimization techniques such as minima-hopping method could be the next step in this direction. This combination is expected to be an ideal sampling approach having the advantage of avoiding efficiently the search over irrelevant regions of the potential energy surface.

Meshing highly regular structures: The case of super carbon nanotubes of arbitrary order

Mesh generation is an important step inmany numerical methods.We present the “HierarchicalGraphMeshing” (HGM)method as a novel approach to mesh generation, based on algebraic graph theory.The HGM method can be used to systematically construct configurations exhibiting multiple hierarchies and complex symmetry characteristics. The hierarchical description of structures provided by the HGM method can be exploited to increase the efficiency of multiscale and multigrid methods. In this paper, the HGMmethod is employed for the systematic construction of super carbon nanotubes of arbitrary order, which present a pertinent example of structurally and geometrically complex, yet highly regular, structures. The HGMalgorithm is computationally efficient and exhibits good scaling characteristics. In particular, it scales linearly for super carbon nanotube structures and is working much faster than geometry-based methods employing neighborhood search algorithms. Its modular character makes it conducive to automatization. For the generation of a mesh, the information about the geometry of the structure in a given configuration is added in a way that relates geometric symmetries to structural symmetries. The intrinsically hierarchic description of the resulting mesh greatly reduces the effort of determining mesh hierarchies for multigrid and multiscale applications and helps to exploit symmetry-related methods in the mechanical analysis of complex structures.

An improved method for discovering link criticality in transport networks

Quantitatively assessing the importance or criticality of each link in a network is of practical value to operators, as that can help them to increase the network's resilience, provide more efficient services, or improve some other aspect of the service. Betweenness is a graph-theoretical measure of centrality that can be applied to communication networks to evaluate link importance. However, as we illustrate in this paper, the basic definition of betweenness centrality produces inaccurate estimations as it does not take into account some aspects relevant to networking, such as the heterogeneity in link capacity or the difference between node-pairs in their contribution to the total traffic. A new algorithm for discovering link centrality in transport networks is proposed in this paper. It requires only static or semi-static network and topology attributes, and yet produces estimations of good accuracy, as verified through extensive simulations. Its potential value is demonstrated by an example application. In the example, the simple shortest-path routing algorithm is improved in such a way that it outperforms other more advanced algorithms in terms of blocking ratio

On optimal computation of MPLS label binding for multipoint-to-point connections

Most network operators have considered reducing Label Switched Routers (LSR) label spaces (i.e. the number of labels that can be used) as a means of simplifying management of underlaying Virtual Private Networks (VPNs) and, hence, reducing operational expenditure (OPEX). This letter discusses the problem of reducing the label spaces in Multiprotocol Label Switched (MPLS) networks using label merging - better known as MultiPoint-to-Point (MP2P) connections. Because of its origins in IP, MP2P connections have been considered to have tree- shapes with Label Switched Paths (LSP) as branches. Due to this fact, previous works by many authors affirm that the problem of minimizing the label space using MP2P in MPLS - the Merging Problem - cannot be solved optimally with a polynomial algorithm (NP-complete), since it involves a hard- decision problem. However, in this letter, the Merging Problem is analyzed, from the perspective of MPLS, and it is deduced that tree-shapes in MP2P connections are irrelevant. By overriding this tree-shape consideration, it is possible to perform label merging in polynomial time. Based on how MPLS signaling works, this letter proposes an algorithm to compute the minimum number of labels using label merging: the Full Label Merging algorithm. As conclusion, we reclassify the Merging Problem as Polynomial-solvable, instead of NP-complete. In addition, simulation experiments confirm that without the tree-branch selection problem, more labels can be reduced

Application for fault location in electrical power distribution systems

Fault location has been studied deeply for transmission lines due to its importance in power systems. Nowadays the problem of fault location on distribution systems is receiving special attention mainly because of the power quality regulations. In this context, this paper presents an application software developed in Matlabtrade that automatically calculates the location of a fault in a distribution power system, starting from voltages and currents measured at the line terminal and the model of the distribution power system data. The application is based on a N-ary tree structure, which is suitable to be used in this application due to the highly branched and the non- homogeneity nature of the distribution systems, and has been developed for single-phase, two-phase, two-phase-to-ground, and three-phase faults. The implemented application is tested by using fault data in a real electrical distribution power system

Introduction to Network Mathematics

Introduction to Network Mathematics provides college students with basic graph theory to better understand the Internet

WAIS seminar:Mathematics for Web Science Part3-1

ABSTRACT In the first two seminars we looked at the evolution of Ontologies from the current OWL level towards more powerful/expressive models and the corresponding hierarchy of Logics that underpin every stage of this evolution. We examined this in the more general context of the general evolution of the Web as a mathematical (directed and weighed) graph and the archetypical “living network” In the third seminar we will analyze further some of the startling properties that the Web has as a graph/network and which it shares with an array of “real-life” networks as well as some key elements of the mathematics (probability, statistics and graph theory) that underpin all this. No mathematical prerequisites are assumed or required. We will outline some directions that current (2005-now) research is taking and conclude with some illustrations/examples from ongoing research and applications that show great promise.

WAIS seminar:Mathematics for Web Science Part 3-2

ABSTRACT In the first two seminars we looked at the evolution of Ontologies from the current OWL level towards more powerful/expressive models and the corresponding hierarchy of Logics that underpin every stage of this evolution. We examined this in the more general context of the general evolution of the Web as a mathematical (directed and weighed) graph and the archetypical “living network” In the third seminar we will analyze further some of the startling properties that the Web has as a graph/network and which it shares with an array of “real-life” networks as well as some key elements of the mathematics (probability, statistics and graph theory) that underpin all this. No mathematical prerequisites are assumed or required. We will outline some directions that current (2005-now) research is taking and conclude with some illustrations/examples from ongoing research and applications that show great promise.

WAIS seminar: Mathematics for Web Science: Part 3-3

ABSTRACT In the first two seminars we looked at the evolution of Ontologies from the current OWL level towards more powerful/expressive models and the corresponding hierarchy of Logics that underpin every stage of this evolution. We examined this in the more general context of the general evolution of the Web as a mathematical (directed and weighed) graph and the archetypical “living network” In the third seminar we will analyze further some of the startling properties that the Web has as a graph/network and which it shares with an array of “real-life” networks as well as some key elements of the mathematics (probability, statistics and graph theory) that underpin all this. No mathematical prerequisites are assumed or required. We will outline some directions that current (2005-now) research is taking and conclude with some illustrations/examples from ongoing research and applications that show great promise.