Literatura científica selecionada sobre o tema "Graphe ordonné"

On introduit une nouvelle structure algébrique qui formalise bien les problèmes de reconstruction, assortie d'une conjecture qui permettrait de traiter directement des symétries. Le cadre fournit par cette étude permet de plus d'engendrer des relations qui ont lieu entre les nombres de sous-structures, et d'une certaine façon, la conjecture formulée affirme qu'on les obtient toutes. De plus, la généralisation des résultats précédemment obtenus pour la reconstruction permet de chercher 'a en apprécier les limites en recherchant des cas où ces relations sont optimales. Ainsi, on montre que les théorèmes de V.Müller et de L.Lovasz sont les meilleurs possibles en exhibant des cas limites. Cette généralisation aux algèbres d'invariants, déjà effectuée par P.J.Cameron et V.B.Mnukhin, permet de placer les problèmes de reconstruction en tenaille entre d'une part des relations (fournies) que l'on veut exploiter, et des exemples qui établissent l'optimalité du résultat. Ainsi, sans aucune donnée sur le groupe, le résultat de L.Lovasz est le meilleur possible, et si l'on considère l'ordre du groupe, le résultat de V.Müller est le meilleur possible.

Dans ce travail, nous donnons un cadre général de surfaces riemanniennes qui dégénèrent sur des graphes métriques que nous appelons surfaces décomposables en cylindres et en jonctions. Les surfaces décomposables en cylindres et en jonctions dépendent d’un paramètre t qui traduit le mécanisme d’écrasement sur le graphe. Quand le paramètre t tend vers 0, les circonférences des cylindres tendent vers 0 et leurs longueurs restent fixes. On obtient ainsi les arêtes du graphe limite. Les jonctions, elles, sont écrasées dans toutes les directions et donc dégénèrent sur les sommets du graphe limite. Nous étudions alors le comportement asymptotique du spectre de ces variétés lors de cette déformation. Nous adoptons les points de vue de la convergence des valeurs propres ordonnées et de celle des branches analytiques. Ces deux approches sont fondamentalement différentes. Le cas des valeurs propres ordonnées est assez classique et nous retrouvons la convergence vers le spectre du graphe limite. L’étude des branches analytiques est plus original. Nous montrons la convergence et donnons une caractérisation des limites possibles. Ces résultats s’appliquent dans le cas des surfaces de translations qui possèdent une direction complètement périodique<br>In this work, we give a general framework of Riemannian surfaces that can degenerate on metric graphs and that we call surfaces made from cylinders and connecting pieces. The latter depend on a parameter t that describes the degeneration. When t goes to 0, the waists of the cylinders go to 0 but their lengths stay fixed. We thus obtain the edges of the limiting graph. The connecting pieces are squeezed in all directions and degenerate on the vertices of the limiting graph. We then study the asymptotic behaviour of the spectrum of these surfaces when t varies from two different points of view, considering the spectrum either as a sequence of ordered eigenvalues or as a collection of analytic eigenbranches. In the case of ordered eigenvalues, we recover a rather classical statement, and prove that the spectrum converges to the spectrum of the limiting object. The study of the analytic eigenbranches is more original. We prove that any such eigenbranch converges and we give a characterisation of the possible limits. These results apply to translation surfaces on which there is a completely periodic direction

Dans cette thèse, nous étudions les régularités dans les graphes et les représentations succinctes des graphes. Une régularité, ou structure, est un terme générique qui désigne un ensemble de sommets du graphe ayant certaines propriétés. Parmi les régularités les plus connues, nous pouvons citer les cliques, les sous-graphes denses, les communautés, les modules et les splits. Une représentation succincte d'un graphe est une façon de le décrire qui est plus efficace que de simplement lister les différentes arêtes du graphe. Chercher des régularités permet d'obtenir des représentations succinctes. Ainsi, dans un premier temps, nous avons développé un algorithme de compression de graphe qui cherche différentes régularités du graphe, en sélectionne une partie et partitionne le graphe en fonction des structures sélectionnées. Cet algorithme donne une description succincte du graphe qui est meilleure que certains algorithmes de référence.Dans un deuxième temps, nous avons créé nos propres structures, de sorte qu'elles soient adaptées à la compression et qu'elles soient assez facile à chercher. Pour ce faire, nous sommes partis d'une structure connue, le split, et nous l'avons généralisée en créant le r-split, où r est un paramètre entier fixé. Nous avons alors montré que l'ensemble des r-splits d'un graphe a une cohérence globale, dans le sens où seul un nombre polynomial d'entre eux suffit à décrire l'intégralité des r-splits du graphe. Cela généralise une propriété bien connue des splits, pour lesquels seul un nombre linéaire d'entre eux suffit à retrouver tous les autres. Nous avons également montré que les r-splits peuvent se calculer en temps polynomial en utilisant des algorithmes d'optimisation de fonctions sous-modulaires.Dans un troisième temps, nous nous sommes intéressés à la recherche de structures particulières : les motifs dans les graphes ordonnés. Un graphe ordonné est un graphe dans lequel les sommets sont ordonnés de 1 à n. Un motif est un sous-graphe ordonné partiel, dans le sens où chaque paire de sommets peut être reliée soit par une arête, soit par une non-arête, soit par ni l'une ni l'autre. Le but est de fixer un motif P et de construire un algorithme capable de détecter si P est dans n'importe quel graphe ordonné donné en paramètre. Ce problème est polynomial en la taille du graphe via une recherche exhaustive. Cependant, est-il possible de faire mieux ? Nous avons montré que oui : la plupart des motifs à trois sommets peuvent être détectés en temps linéaire là où une recherche exhaustive nécessite un temps cubique. Concernant les motifs plus grands, nous avons exhibé des classes de motifs qui peuvent être détectés en temps sous-cubique : les motifs planaires extérieurs. En ajoutant des contraintes supplémentaires, nous avons exhibé une classe de motifs qui peuvent être détectée en temps linéaire : il s'agit des motifs planaires extérieurs sans cycle et sans non-arête<br>In this thesis, we investigate regularities in graphs and succinct representations of graphs.A regularity, or structure, is a generic term that refers to a set of vertices in a graph with certain properties.Among the most well-known regularities, we can mention cliques, dense subgraphs, communities, modules, and splits.A succinct representation of a graph is a way of describing it that is more efficient than simply listing the different edges of the graph.Searching for regularities enables obtaining succinct representations.Thus, in a first step, we developed a graph compression algorithm that searches for different graph regularities, selects a portion of them, and partitions the graph based on the selected structures.This algorithm provides a succinct description of the graph that is better than some benchmark algorithms.In a second step, we created our own structures, so they are suitable for compression and are easy enough to search for.To do this, we started from a known structure, the split, and generalized it to create the r-split, where r is a fixed integer parameter.We then showed that the set of r-splits of a graph has a global coherence, in the sense that only a polynomial number of them is sufficient to describe all r-splits of the graph.This generalizes a well-known property of splits, for which only a linear number of them is sufficient to recover all the others.We also demonstrated that r-splits can be computed in polynomial time using submodular function optimization algorithms.In a third step, we focused on searching for particular regularities: patterns in ordered graphs.An ordered graph is a graph in which the vertices are ordered from 1 to n.A pattern is a partial ordered subgraph, in the sense that each pair of vertices can be connected either by an edge, a non-edge, or neither.The goal is to fix a pattern P and build an algorithm capable of detecting if P is in any ordered graph given as an input.This problem is polynomial in the size of the graph via exhaustive search.However, is it possible to do better?We were able to show that yes: most three-vertex patterns can be detected in linear time while exhaustive search requires cubic time.Regarding larger patterns, we exhibited classes of patterns that can be detected in subcubic time: outerplanar patterns.By adding additional constraints, we exhibited a class of patterns that can be detected in linear time: these are outerplanar patterns without cycles and non-edges

The thesis focuses on two open problems on finite partially ordered sets: the structure of order polytopes and the approximation of the number of linear extensions of a poset by mean of graph entropy. The polytopes considered here are the linear ordering polytope, the semiorder polytope, the interval order polytope, the partial order polytope and also a generalisation of the linear ordering polytope: the linear extension polytope of a fixed poset P. Various results on the structure of theses polytopes are proved in the first part of the thesis. In the second part of the thesis, we improve the existing bounds linking the entropy of the incomparability graph of the poset P and its number of linear extension.<br>Le but de la thèse est d'étudier deux problèmes ouverts sur les ensembles ordonnés finis: la structure des polytopes d'ordre et l'approximation du nombre d'extensions linéaires d'un ordre partiel au moyen de la notion d'entropie de graphe. Les polytopes considérés sont le polytope des ordres totaux, le polytope des semiordres, le polytope des ordres d'intervalles, le polytope des ordres partiels, ainsi qu'une généralisation du polytope des ordres totaux: le polytope des extensions linéaires d'un ensemble ordonné fixé P. Des résultats sur la structure de ces polytopes sont présentés dans la première partie de la thèse. Dans la deuxième partie de la thèse, nous améliorons les bornes existantes liant l'entropie du graphe d'incomparabilité d'un ordre partiel et son nombre d'extensions linéaires.<br>Doctorat en Sciences<br>info:eu-repo/semantics/nonPublished

Cette thèse présente un calcul des séquents pour la logique linéaire enrichie d'un connecteur non commutatif et autodual "précède" situé entre le "par" et le "tenseur". Il est défini pour des séquents dont les formules sont orientées par un ordre partiel. Un calcul de réseaux de démonstration quotientant ce calcul des séquents est défini en termes de graphes orientés. Ce calcul est doté d'une sémantique dénotationnelle dans les espaces cohérents, préservée par élimination des coupures, un processus convergent et confluent. Des résultats combinatoires nécessaires sur les ordres partiels et sur la structure des graphes de démonstrations sont établies ainsi que quelques propriétés du calcul commutatif avec la règle MIX.

Cette thèse porte sur l'utilisation des outils théoriques de l'informatique pour améliorer les algorithmes dans la pratique, en particulier ceux qui traitent des données sous forme de graphes. Un graphe représente des éléments (nœuds) et leurs interactions (arêtes). L'informatique théorique a conçu des algorithmes pour des graphes arbitraires, tels que la recherche des chemins les plus courts ou l'identification des nœuds interconnectés. Cependant, les réseaux réels ont des propriétés spécifiques qui sont inconnues à l'avance en raison des situations du monde réel dont ils sont issus. Ils peuvent être très volumineux, ce qui pose un problème pour les traiter en un temps raisonnable. Pour aider à concevoir des algorithmes qui passent à l'échelle sur de gros graphes, nous nous concentrons sur la technique qui consiste à réordonner les nœuds selon un ordre spécifique qui dépend des propriétés locales ou globales du graphe. Nous classifions les différents mécanismes et méthodes qui ont été utilisés pour concevoir des ordres dans divers domaines d'application. Ensuite, nous présentons trois contributions qui utilisent l'ordre des nœuds pour rendre les algorithmes plus efficaces. Tout d'abord, nous reproduisons un article qui conçoit un ordre pour rendre les systèmes de cache plus efficaces, ce qui accélère différents algorithmes de graphes. Deuxièmement, nous créons de nouveaux ordres qui réduisent le nombre d'opérations dans un algorithme existant pour lister les triangles. Troisièmement, nous utilisons des algorithmes simples avec des ordres appropriés pour limiter la taille d'une couverture minimale par les sommets sur une instance spécifique de graphe, ce qui nous permet de certifier la qualité des résultats obtenus par des valeurs approchées. Ces résultats insistent sur les questions de passage à l'échelle, les mesures de temps, les fondements mathématiques et la validation par l'expérience. Enfin, nous présentons une collaboration sur l'analyse des réseaux qui consiste à décrire la mobilité des chercheurs et chercheuses dans l'espace de la connaissance<br>This thesis focuses on using theoretical tools of computer science to improve algorithms in practice, specifically algorithms that process data in the form of graphs. A graph represents elements (nodes) and their interactions (edges). Computer scientists have designed theoretical algorithms for arbitrary graphs, such as finding shortest paths or identifying inter-connected nodes. However, real-world networks have specific properties that are unknown in advance due to the situations from which they arise. They can be very large, which presents a challenge for processing them in reasonable time. To help design scalable algorithms for real-world networks, we focus on the technique of node ordering, which consists in processing the nodes in a specific order that depends on local or global properties of the network. We provide a review on the different mechanisms and methods that have been used to design orderings across various application domains. Then, we present three contributions that use node orderings to make algorithms more efficient. First, we replicate a paper that designs an ordering to make cache systems more effective, which accelerates different graph algorithms. Second, we create new orderings that diminish the number of operations in an existing algorithm for triangle listing. Third, we use greedy algorithms with certain orderings to bound the size of a minimum vertex cover on a specific instance, which allows us to certify the quality of approximate values. These findings insist on scalability issues, time measurements, mathematical grounding and validation by experiments. Finally, we present a collaboration on network analysis that consists in describing the mobility of researchers within the space of knowledge

Nous definissons les ordres de contiguite comme possedant une extension lineaire pour laquelle chaque ensemble de successeurs directs apparait comme un intervalle. Nous etudions cette nouvelle classe d'ordres dont la reconnaissance est lineaire, ainsi que certaines restrictions. Cette classe contient en particulier les ordres d'intervalles et les ordres sans n, ce qui entraine la np-completude de la dimension et du nombre de sauts. Nous montrons que le calcul du nombre d'extensions lineaires de contiguite est p-complet. Concernant les ordres de contiguite de hauteur un, nous prouvons que la dimension est un probleme polynomial. Nous etablissons egalement l'invariance de comparabilite de l'appartenance a la classe des ordres de double contiguite ainsi que la np-completude de la dimension pour les ordres de forte contiguite

Les structures arborescentes (arbres) sont largement étudiées en informatique. Les données semi-structurées en sont un récent champ d'application : il est admis que les arbres ordonnés d'arité non bornée sont un bon modèle pour ces données. Dans certains cas il est intéressant de considérer des arbres non ordonnés. Des formalismes logiques (logiques) sont utilisés pour décrire des requêtes ou vérifier des propriétés sur des données semi-structurées. Il est important d'identifier des logiques représentant un compromis entre expressivité et praticabilité des algorithmes. Des critères pertinents sont la satisfiabilité et la complexité du model checking de la logique. Nous étudions une logique spatiale, LS, qui est à la base d'un langage de requètes pour données semi-structurées modélisées par des arbres non ordonnés. La logique LS est très expressive, incluant des opérateurs spatiaux pour décrire localement la structure d'un arbre, un opérateur de point fixe et permettant de quantifier sur des étiquettes et sur des arbres. Nous établissons des résultats sur la satisfiabilité et la complexité du model checking pour différents fragments de LS. Nous identifions deux fragments syntaxiques de LS à satisfiabilité décidable, montrons que ces fragments sont équivalents aux logiques MSO et PMSO respectivement, et introduisons des classes d'automates d'arbres qui capturent ces deux fragments. Nous montrons que la complexité du mode! checking de LS est dans PSPACE-complet. Si seule la taille de l'arbre est prise en compte, la complexité du model checking va de linéaire à PSP ACE-complet pour les différents fragments de la logique.

La notion d'intervalle dans un graphe, traduit de façon naturelle la notion du segment dans les espaces euclidiens. Par analogie, un ensemble C de sommets est convexe si pour tout couple x, y de sommets de C, l'intervalle entre x et y est inclu dans C. En utilisant la convexité géodésique, Djokovic a caractérisé les graphes isométriquement plongeable dans l'hypercube. Une vingtaine d'années plus tard, Mulder a caractérisé les graphes médians comme des graphes isométriquement plongeable dans l'hypercube et qui sont fermés pour l'opération médian. La comprehension du lien apparent entre ces deux résultats, nous a permis de trouver une nouvelle caractérisation, d'inspiration géométrique, des graphes médians. Cette caractérisation nous a permis à reconnaître les graphes médians qui sont des produits d'arbres ou de chemins. Nous avons donné une caractérisation de ces produits par mineurs convexes exclus. Un autre groupe de résultats concerne des graphes définis naturellement à partir des polyminos. En cherchant le nombre minimum de sommets qui engendrent convexement un tel graphe G, nous avons trouvé que ce nombre est égal au nombre maximum de sommets de degré un d'un arbre obtenu à partir de G par la contraction d'arêtes bien choisies