Thèses : « Graphes planaires »

1

Lapoire, Denis. « Structuration des graphes planaires ». Bordeaux 1, 1996. http://www.theses.fr/1996BOR10684.

Résumé :

Cette these etend la theorie des grammaires algebriques aux cartes (c'est a dire des representations de graphes sur des surfaces). Nous definissons des algebres de cartes possedant de bonnes proprietes vis a vis des notions de dualite, de graphe induit et de planarite. Ceci nous permet d'etudier les liens existant entre d'une part les grammaires de graphes et les grammaires de cartes et d'autre part les grammaires de graphes et les grammaires algebriques de mots

Styles APA, Harvard, Vancouver, ISO, etc.

2

Tishchenko, Serge. « Diamètre des graphes planaires ». Paris 6, 2009. http://www.theses.fr/2009PA066566.

Texte intégral

Résumé :

Nous étudions les N-séparateurs dans les graphes planaires pondérés (un N-séparateur d'un graphe connecté G est un sous-graphe S dont la suppression décompose G en N composantes connexes). Un grand nombre de travaux a été inspiré par l'article fondateur de Lipton et Tarjan sur les 2-séparateurs dans les graphes planaires pondérés. La construction de leur séparateur est un outil majeur dans de nombreux cas d'application de la théorie des graphes tels que VLSI modélisation, réseaux de communication, calcul parallèle. La plupart des publications considère les séparateurs qui divisent le graphe en deux parties, pourtant la division des graphes en un nombre de parties plus grand est nécessaire dans beaucoup d'applications. Notons que l'application récursive du 2-séparateur de Lipton-Tarjan donne une séparation qui est loin d'être optimale. Si cet algorithme est utilisé afin d'obtenir un 4-séparateur, dans ce cas, la plus petite des composantes sera d'au moins 1/9 de la taille du graphe quand l'application de notre méthode nous permet de dire que la plus petite des composantes va être d'au moins 1/7 de la taille du graphe. On optimise la construction du séparateur dans le cas des graphes planaires pondérés. Cette généralisation est importante pour les applications pratiques. Nous étudions les conditions d'existence d'un N-séparateur dans un graphe planaire et obtenons la limite optimale de la taille de la plus petite composante. Nous proposons la solution exacte au problème de degré-diamètre pour les graphes planaires dans le cas de diamètre pair 2d et de degré Delta > 6(12d + 1). De nouveaux exemples de graphes améliorant la borne inférieure sont construits pour Delta >=5.

Styles APA, Harvard, Vancouver, ISO, etc.

3

Zighem, Ismail. « Etude d'invariants de graphes planaires ». Université Joseph Fourier (Grenoble), 1998. http://www.theses.fr/1998GRE10211.

Texte intégral

Résumé :

Dans la première partie, nous construisons, à partir de relations linéaires de récurrence, des invariants de graphes planaires 4-réguliers prenant leurs valeurs dans un anneau commutatif. Ces relations représentent des règles récursives bien définies sur cette catégories de graphes, ramenant le calcul des valeurs de l'invariant en ces graphes à une combinaison linéaire d'autres graphes plus réduits. Après avoir dégagé quelques conditions nécessaires pour que ces règles soient mutuellement compatibles, nous montrons en utilisant un résultat de la théorie des systèmes de réécriture qu'elles sont aussi suffisantes. Nous terminons cette partie en évoquant la relation avec le polynôme de Kauffman et en montrant que, pour une évaluation particulière de ses variables, ce polynôme peut être défini à partir de notre invariant. Ce qui constitue une nouvelle preuve d'existence de ce polynôme. La seconde partie aborde le problème de la détermination du nombre d'absorption des graphes de type grille. Dans un premier temps, nous déterminons ce nombre pour les petites grilles croisées (graphes produit croisé de deux chaînes de longueurs k et n, avec k ≤ 33 et n ≤ 40). En utilisant la programmation dynamique, nous présentons pour k fixé un algorithme linéaire en n pour calculer ce nombre. On en déduit alors que ce nombre vérifie des formules simples en fonction de k et n. Ensuite, nous montrons par récurrence, en prenant ces valeurs comme base de récurrence, que ces formules sont vérifiées par ce nombre, pour tous k = 12 ou k ≥ 14 et n ≥ k. Finalement, nous donnons quelques bornes du nombre d'absorption de la grille carrée (graphe produit carré de deux chaînes) qui améliorent les résultats déjà connus

Styles APA, Harvard, Vancouver, ISO, etc.

4

Isenmann, Lucas. « Des graphes planaires vers des dimensions supérieures ». Thesis, Montpellier, 2019. http://www.theses.fr/2019MONTS142.

Texte intégral

Résumé :

Dans cette thèse on cherche à généraliser certaines propriétés des graphes planaires aux dimensions supérieures en remplaçant les graphes par des complexes simpliciaux. En particulier on étudie la dimension de Dushnik-Miller qui mesure à quel point un ordre partiel ressemble à un ordre total. Appliquée aux complexes simpliciaux, cette dimension semble capturer des propriétés géométriques. Concernant ce sujet, on infirme une conjecture assurant que n'importe quel complexe simplicial de dimension de Dushnik-Miller au plus d+1 peut être représenté par un complexe de TD-Delaunay dans RR d, qui est une variante des graphes de Delaunay dans le plan. On montre que toute section supremum, qui est un complexe simplicial particulier relié à la dimension de Dushnik-Miller, est ``collapsible'', c'est-à-dire que l'on peut atteindre un point unique en retirant dans le bon ordre les faces du complexe. On introduit la notion d'empilements d'escaliers et on démontre que la dimension de Dushnik-Miller est reliée aux complexes de contacts de tels empilements. On démontre aussi de nouveaux résultats sur les graphes planaires.Les deux résultats suivants sur la représentabilité des graphes planaires sont démontrés : tout graphe planaire est le graphe d'intersection de llcorner et tout graphe planaire sans triangle est le graphe de contact de {llcorner, | , -}. On introduit et étudie une nouvelle notion sur les graphes planaires que l'on appelle ``Möbius stanchion systems'' qui sont reliés à des questions sur les plongements unicellulaires des graphes planaires
In this thesis we look for generalizations of some properties of planar graphs to higher dimensions by replacing graphs by simplicial complexes.In particular we study the Dushnik-Miller dimension which measures how a partial order is far from being a linear order.When applied to simplicial complexes, this dimension seems to capture some geometric properties.In this idea, we disprove a conjecture asserting that any simplicial complex of Dushnik-Miller dimension at most d+1 can be represented as a TD-Delaunay complex in RR d, which is a variant of the well known Delaunay graphs in the plane.We show that any supremum section, particular simplicial complexes related to the Dushnik-Miller dimension, is collapsible, which means that it is possible to reach the single point by removing in a certain order the faces of the complex.We introduce the notion of stair packings and we prove that the Dushnik-Miller dimension is connected to contact complexes of such packings.We also prove new results on planar graphs.The two following theorems about representations of planar graphs are proved: any planar graph is an llcorner-intersection graph and any triangle-free planar graph is an {llcorner, | , -}-contact graph.We introduce and study a new notion on planar graphs called Möbius stanchion systems which is related to questions about unicellular embeddings of planar graphs

Styles APA, Harvard, Vancouver, ISO, etc.

5

Chaboud, Thomas. « Pavages et graphes de Cayley planaires ». Lyon, École normale supérieure (sciences), 1995. http://www.theses.fr/1995ENSL0004.

Texte intégral

Résumé :

Les deux premiers chapitres introduisent les thèmes abordés et les définitions afférentes. Le chapitre 3 établit une généralisation d'un algorithme de Thurston de pavage par dominos dans la grille carrée et le réseau triangulaire. Nous montrons que les mêmes techniques permettent d'obtenir des pavages par dominos (deux faces partageant une arête) de parties finies simplement connexes de graphes planaires dont le dual est régulier et biparti, en temps linéaire sur la surface. Même dans les cas ou le graphe sous-jacent est régulier, nous remarquons qu'il n'admet pas en général d'étiquetage par un groupe ; les groupes de pavage de Conway ne suffisent donc pas à expliquer cette combinatoire. Le chapitre 4 établit une caractérisation des graphes planaires euclidiens ou hyperboliques gk, d réguliers (degré d), de dual régulier (degré k) admettant un étiquetage de graphe de Cayley. G admet un tel étiquetage ssi k a un facteur inférieur a d. La preuve est effective: On construit au moins un étiquetage pour tous les cas positifs. Le chapitre 5 prouve et expose un algorithme permettant d'obtenir toutes les présentations étiquetant un graphe planaire donné, s'il admet un plongement localement fini sur le plan euclidien ou hyperbolique ; nous montrons qu'un tel graphe induit toujours un pavage du plan par des polygones reguliers. Nous décrivons des graphes de Cayley planaires hors de cette classe. Enfin, le chapitre 6 montre une caractérisation linéaire des polyominos horizontalement et verticalement convexes admettant un pavage optimal par des dominos

Styles APA, Harvard, Vancouver, ISO, etc.

6

Dieng, Youssou. « Décomposition arborescente des graphes planaires et routage compact ». Thesis, Bordeaux 1, 2009. http://www.theses.fr/2009BOR13855/document.

Texte intégral

Résumé :

Savoir comment transmettre une information est fondamental dans un réseau. Il est essentiel que chaque entité du réseau soit capable de décider localement, avec sa vue du réseau, du chemin par lequel l'information doit passer. Ainsi, il est souvent utile d'étudier la topologie du réseau, modélisée par un graphe, pour répondre à ces exigences. Nous nous intéressons dans un premier temps, à la décomposition arborescente des graphes planaires. En effet, comme dans beaucoup de problèmes de graphes, l'étude de la topologie des graphes nous conduit à procéder à une décomposition du graphe afin d'exploiter les propriétés structurelles qui en découlent. En suite, nous nous sommes aussi intéressés à la structure des graphes qui excluent un mineur H, en particulier le graphe K_{2,r}. Ces travaux nous ont permis d'améliorer les bornes actuelles connues sur la largeur arborescente de ces graphes. Dans la dernière partie, nous abordons le problème du routage compact. Nous nous sommes intéressés aux schémas de routage de plus courts chemins utilisant des adresses, des tables de routage de tailles optimales de O(log n) bits, où n est le nombre de sommets du graphe. Nous proposons un tel schéma de routage pour une famille de graphes valués contenant les arbres et les graphes planaire-extérieurs
In a network, it is crucial to know how to construct an efficent routing scheme. It is fundamental for each entity with its local knowledge of the network, to be able to decide on which link to forward messages. Thus, it is important to sutdy the underlying network topology in order to design routing schemes. In the first part of this thesis, we construct a new tree-decomposition for planar graphs. In fact, as in many graph problems, the study of the graph structure leads to do a tree-decomposition for exploiting structural propertys of the graphs. In second part, we studied the structure of H-minor free graphs, in particular whenever H = K_{2,r}. Our results improve upon previous known bounds about the tree-width of K_{2,r}-minor free graphs. At last, we treat the problème of compact routing scheme. More precisely, we are interested in shortest-path routing schemes that use O(\log n) bits for addresses, headers and routing tables, where n is the number of vertices in the graph. We propose such a routing scheme for a large family of weighted graphs including outerplanar graphs

Styles APA, Harvard, Vancouver, ISO, etc.

7

Gonçalves, Daniel. « Etudes de différents problèmes de partition de graphes ». Bordeaux 1, 2006. http://www.theses.fr/2006BOR13256.

Texte intégral

Résumé :

Dans ce mémoire, on s'intéresse à différentes notions de partition de graphes telles que l'arboricité ou la planarité externe. On se concentre sur la famille des graphes planaires. On montre notamment que tout graphe planaire est l'union de : - deux graphes planaires externes. - quatres forêts de chenilles. - trois forêts dont une est de degré maximum au plus quatre. On donne également quelques résultats de compléxité concernant des problèmes de décision liés à différents types d'arboricité. On définit enfin de nouvelles notions d'arboricité telles que l'arboricité mixte ou l'arboricité circulaire.

Styles APA, Harvard, Vancouver, ISO, etc.

8

Fusy, Eric. « Combinatoire des cartes planaires et applications algorithmiques ». Palaiseau, Ecole polytechnique, 2007. http://www.theses.fr/2007EPXX0034.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

9

Esperet, Louis. « Distance-two colorings of graphs ». Bordeaux 1, 2008. http://www.theses.fr/2008BOR13591.

Texte intégral

Résumé :

Dans cette thèse, on s'intéresse en particulier à la coloration du carré des graphes planaires (deux sommets à distance au plus deux ont des couleurs distinctes) et à la coloration cyclique des graphes planaires (deux sommets incidents à la même face ont des couleurs distinctes). On montre un résultat général qui implique que deux conjectures importantes sur ces colorations (Wegner 1977 et Borodin 1984) sont vraies asymptotiquement. On s'intéresse également à d'autres colorations à distance deux, qui ont des liens (plus ou moins vagues) avec l'allocation de fréquences dans les réseaux radios, la théorie des jeux, la sociologie, et l'écologie.

Styles APA, Harvard, Vancouver, ISO, etc.

10

Renault, David. « Etude des graphes planaires cofinis selon leurs groupes de symétries ». Bordeaux 1, 2004. http://www.theses.fr/2004BOR12922.

Texte intégral

Résumé :

Les graphes cofinis constituent une famille de graphes possédant un groupe de symétries non trivial, comme les graphes de Cayley ou les graphes sommet-transitifs. Lorsque ces graphes sont en plus planaires, ces symétries peuvent se traduire de manière simple grâce à des symétries du plan dans lequel les graphes sont dessinés. L'ensemble de ces symétries ou automorphismes permet alors de décrire globalement le graphe à l'aide de données géométriques locales, par des structures appelées schémas d'étiquetage. Dans cette thèse, nous étudions les groupes de symétries et décrivons les schémas d'étiquetage des graphes planaires cofinis possédant une représentation topologique simple : les graphes planaires localement finis. Nous montrons comment ces schémas permettent de caractériser le graphe et ses plongements. Cette analyse permet d'énu\-mérer cette famille des graphes planaires cofinis, en particulier lorsqu'ils sont de Cayley ou sommet-transitifs. A partir de ces résultats, nous nous intéressons à la structure des groupes d'automorphismes de cette famille de graphes. Des problèmes de la théorie combinatoire des groupes usuellement indécidables se trouvent devenir décidables dans notre cadre : c'est le cas en particulier des problèmes du mot, simple et généralisé. Les problèmes de décidabilité de la logique permettent de classifier ces graphes en deux grandes familles, selon leur largeur arborescente et la géométrie de leur plongement. Enfin, la question de l'extension de cette description à une famille de graphes plus généraux est étudiée. La classification de ces graphes en terme de bouts et de points d'accumulation dans les plongements permet d'obtenir des informations sur la forme que peuvent prendre les plongements des graphes planaires cofinis non localement finis. Nous discutons alors des difficultés d'extension de la méthode ``localement finie'' au cas général.

Styles APA, Harvard, Vancouver, ISO, etc.

11

Dervieux, Clément. « Énumération de cartes planaires orientées ». Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC056/document.

Texte intégral

Résumé :

Après une présentation générale des cartes planaires, nous définissons les polyèdres en coin, étudiés par Eppstein et Mumford. Nous en venons rapidement à introduire les triangulations en coin, qui sont les cartes duales des squelettes des polyèdres en coin, et en donnons quelques propriétés. Nous proposons un algorithme de réalisation de polyèdres en coin de complexité linéaire. Pour cela, l'étude des triangulations en coin conduit à des problèmes d'énumération. Une méthode classique, connue depuis Tutte, donne le résultat voulu en faisant intervenir la série des nombres de Catalan. La recherche d'une explication combinatoire à la présence des nombres de Catalan a rendu souhaitable l'utilisation d'autres méthodes, fondées sur des découpages et des recollements de morceaux de triangulations en coin. Ainsi apparaît la famille des triangulations en amande, qui est une nouvelle représentation des nombres de Catalan, qui est en bijection directe avec la famille des arbres binaires, et qui complète notre algorithme de réalisation de polyèdres en coin. Nous apportons enfin une conclusion à ces travaux en tentant de généraliser nos méthodes à des cartes dont les faces sont de degré fixé, mais quelconque
After a general presentation of planar maps, we define corner polyhedra, studied by Eppstein and Mumford. We soon introduce corner triangulations, that are dual maps of the skeletons of corner polyhedra, and we give some properties of them.We offer a linear time algorithm to realize corner polyhedra. For that, the study of corner triangulations leads to enumeration problems. A classic method, known from Tutte, gives the wanted result, making the series of Catalan numbers appearing. The research for a combinatorial explanation of the presence of Catalan numbers induces the use of other methods, based on cuttings and gluings of some parts of corner triangulations. Thus appears the family of almond triangulations, that is a new representation of Catalan numbers, in bijection with the binary trees family, and that completes our corner polyhedra realization algorithm. We eventually give a conclusion to these works, trying to generalize our methods to maps whose faces have an any fixed degree

Styles APA, Harvard, Vancouver, ISO, etc.

12

Roussel, Nicolas. « Circular coloring and acyclic choosability of graphs ». Thesis, Bordeaux 1, 2009. http://www.theses.fr/2009BOR13889/document.

Texte intégral

Résumé :

Dans cette thèse, nous nous intéressons à la coloration circulaire des graphes planaires. Des bornes supérieures ont été données pour des graphes avec degré maximum borné, avec girth, la longueur de son plus petit cycle, bornée, avec des cycles manquants, etc. Ici nous donnerons de nouvelles bornes pour les graphes avec degré moyen maximum borné. Nous étudions également la coloration totale et la coloration (d,1)-totale de plusieurs familles infinies de graphes. Nous décrivons le nouveau concept de coloration (d,1)-totale circulaire. Enfin, nous discutons les conditions nécessaires pour qu'un graphe planaire admette une coloration acyclique par listes de taille 4
In this thesis, we study the circular coloring of planar graphs. Upper bounds have been given for graphs with bounded maximum degree, with bounded girth, that is the length of its smallest cycle, with missing cycles, and so on. It has also been studied for graphs with bounded maximum average degree. Here we give new upper bounds for that latter case. We also study the total coloring and ($d,1$)-total labeling of a few infinite families of graphs and describe the new concept of circular ($d,1$)-total labeling of graphs. In the last part, we will discuss conditions for a planar graph to be acyclically $4$-choosable

Styles APA, Harvard, Vancouver, ISO, etc.

13

Courtat, Thomas. « Promenade dans les cartes de villes, phénoménologie mathématique et physique des villes : une approche géométrique ». Paris 7, 2012. http://www.theses.fr/2012PA077160.

Texte intégral

Résumé :

Nous nous intéressons à la phénoménologie des villes en nous limitant à la géométrie induite par le squelette de leur réseau des rues. C'est une étude à volonté synthétique, fonctionnelle et interdisciplinaire qui vient s'ajouter aux travaux qui ont été menés à grande cadence depuis le début du XXème siècle par les urbanistes, sociologues, géographes, statiticiens, physiciens. Nous cherchons à montrer que la rue, en tant qu'alignement cohérent de segments de rues peut être considérée comme structure élémentaire de la ville. Quelle quantité d'information est donnée par la géométrie du réseau routier ? Dans quelle mesure contraint-il nos échanges ? Comment le paysage urbain actuel est-il déterminé par son évolution le long d'axes de circulation et d'éléments structurants ? Nous présentons un cadre mathématique permettant de considérer la carte d'une ville comme un continuum géométrique défini par la topologie d'un graphe planaire. Nous superposons à ce graphe une structure d'hypergraphe pour manipuler aisément la notion d'axes ainsi qu'une représentation multi-échelles de la ville. En dépit d'une grande diversité apparente de formes, nous montrons que le réseau de rues d'une ville se soumet à un certain nombre de lois générales qui laissent des traces sur le plan de la ville. Nous proposons des modèles de croissance et de morphogénèse de la ville, implémentant l'idée que l'évolution de la ville suit une logique d'extension / division structurée de l'espace et reproduisant les signatures observées sur les plans de villes réelles. La compréhension des mécanismes régulateurs de la ville nous permet de proposer des algorithmes fonctionnels dont le temps de calcul est très intéressant. Ainsi nous présentons un algorithme reconstituant les rues à partir de segments de rues ; la notion de centralité simple dont le calcul sur une carte permet une analyse hiérarchique de celle-ci, met en valeur les axes de transport principaux et en évidence les zones mal desservies ; un algorithme permettant d'approximer rapidement le plus court chemin entre deux points aléatoires ; un alogorithme prenant appui sur le Spectral Clustering pour produire des segmentations morphologiques de cartes et retravaillons l'identification de modèles de mosaïques aléatoires pour les substituer à un réseau urbain particulier dans la résolution par équivalents statistiques de grands problèmes d'optimisation
We are interested in the phenomenology of cities by restricting them to the geometry of their street network. This study aims at being synthetic, functional and interdisciplinary. It follows the large work that has been performed from the early XXth century by town-planners, social scientists, geographers, statisticians, physicists. We try to demonstrate that the street - as a coherent alignment of street segments - can be considered as an essential elementary structure of the city. How much information is encoded in the street network ? To what extent does it constraint the city use ? How are the current urban layout and its evolution determined jointly by traffic axis and structuring elements ? We present a mathematical and computational framework allowing to consider the map of a city as a geometric continuum associated to the topology of a planar graph. To this graph we juxtapose a hypergraph structure using the street geometry to obtain easily the notion of axis and a multi-scale representation of the city. In spite of an apparent shape diversity, we show that the street network of a city is subjected to general laws that leave hallmarks on a city map. We propose several morphogenesis models of the city, implementing the idea that the city's growth follows a strucured extension / division of space logic and able to reproduce hallmarks observed on actual maps. The understanding of regulation mechanism of the city allows us to propose functional algorithms whose computational efficiencies are very interesting. We present an algorithm recovering steets from a collection of street segments ; the notion of simplest centrality whose calculus on a map allows a hierarchical analysis of it, revealing for instance main trafic axis and ill-deserved area ; a fast approximative algorithm to find the shortest path between two random points ; and a Spectral Clustering based algorithm to produce morphological segmentations of maps. We also work on the identification of random tessellation models to be subtituted to an actual road network and to solve large optimization problems using statistical equivalence

Styles APA, Harvard, Vancouver, ISO, etc.

14

Rossetti, Bastien. « Sur la détermination des fractions rationnelles postcritiquement finies par des graphes planaires finis ». Thesis, Toulouse 3, 2015. http://www.theses.fr/2015TOU30156/document.

Texte intégral

Résumé :

On réfléchit à une façon de déterminer une fraction rationnelle postcritiquement finie à conjugaison par une transformation de Möbius près, à l'aide de graphes planaires finis munis de la dynamique de l'application. Étant donné une telle fraction rationnelle f, on définit un ensemble G(f) de classes d'équivalences de graphes admissibles (des graphes planaires finis invariants, connexes, qui contiennent l'ensemble postcritique de f). On montre que si G(f) est non vide, alors f et g sont conjuguées par une transformation de Möbius si et seulement si l'intersection entre G(f) et G(g) est non vide. Cela nous amène à réfléchir à la construction de graphes admissibles pour une fraction rationnelle postcritiquement finie. On montre qu'une intersection non vide entre les bords de deux composantes de Fatou périodiques contient au moins un point périodique. On construit des graphes admissibles pour certains éléments de la famille des fractions rationnelles quadratiques dont l'un des deux points critiques est l'image de l'autre, avec des techniques utilisables dans de nombreuses autres familles
We think of a way to determine a postcritically finite rational map up to Möbius conjugacy, using planar finite graphs fitted with the dynamics of themap. Givensuch a rational map f, we define a set G(f)of equivalence classes of admissible graphs (invariant, connected planar finite graphs containing the postcritical set). We show that if G(f) is non-empty, then f and g are Möbius conjugate if and only if G(f)nG(g) unequal Ø. This leads us to think about the construction of admissible graphs for a postcritically finite rational map. We show that a non-empty intersection between the boundaries of two periodic Fatou components contains at least one periodic point. We construct admissible graphs for some elements of the family of quadratic rational maps whose one of the two critical points is the image of the other, with technics usable in a lot of other families

Styles APA, Harvard, Vancouver, ISO, etc.

15

Moreau, Jean-Michel. « Hiérarchisation et facétisation de la représentation par segments d'un graphe planaire dans le cadre d'une arithmetique mixte ». Saint-Etienne, EMSE, 1990. http://tel.archives-ouvertes.fr/docs/00/83/15/81/PDF/1990_Moreau_Jean_Michel.pdf.

Texte intégral

Résumé :

L'organisation structurée (graphe avec hiérarchies et propriétés sémantiques) d'objets du plan implique plusieurs opérations complexes qui doivent être effectuées en toute sécurite de cohérence topologique. La précision inhérente d'une machine étant nécessairement limitée, il faut souvent recourir à une arithmétique exacte couteuse. Cette thèse présente, à partir de travaux liés à la réalisation du module de facétisation d'un simulateur de vol industriel, une solution permettant l'utilisation d'une arithmétique mixte, de précision arbitraire et de coût trés inferieur statistiquement à la solution exacte. On y trouve aussi l'unification des méthodes de construction d'un diagramme de Voronoi, d'une triangulation de Delaunay pour un nuage de points dans le plan et de la triangulation contrainte de Delaunay de la représentation par segments d'un graphe planaire, autour d'une technique incrémentale optimale, fondamentalement plus simple que la méthode" diviser-pour-résoudre" classique. La technique incrémentale permet, par ailleurs, de donner un algorithme linéaire et très simple de construction du diagramme de Voronoi et de la triangulation de Delaunay d'un nuage de points situés sur la frontière d'un polygone monotone ou convexe.

Styles APA, Harvard, Vancouver, ISO, etc.

16

Bedu, Mélanie. « Développement de guides d'ondes planaires de TiO2 optiquement actifs pour biopuces à ondes évanescentes ». Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2009. http://tel.archives-ouvertes.fr/tel-00462382.

Texte intégral

Résumé :

Les biopuces sont utilisées en biologie moléculaire et pour le diagnostic. La lecture est généralement réalisée en «end-point» mais le suivi en temps réel donne accès à des données complémentaires. Avec les biopuces à fluorescence, ces expériences sont limitées par 1fluorescence de la solution d'hybridation contenant les cibles marquées. Pour atténuer ce signal parasite, il est possible d'exciter sélectivement la surface avec une onde guidée dans le substrat. L'utilisation de guides d'ondes minces permet de diminuer le signal parasite d'un facteur 103 et d'augmenter l'éclairement d'un facteur 104 par effet de confinement. La principale difficulté concerne le couplage de l'onde guidée. Dans ce travail, nous proposons un système de couplage innovant, simple et efficace basé sur l'incorporation de fluorophores dans les guides. Tout d'abord, un procédé sol-gel de synthèse à basse température de guide d'ondes à haut indice avec de faibles pertes optiques a été développé. Un chélate d'europium est ensuite incorporé à la matrice pour le couplage. Les couches dopées ont de bonnes propriétés optiques et des taux d'absorption élevés. La fluorescence guidée des sources permet l'excitation de spots biologiques ce qui valide l'architecture proposée. L'éclairement est homogène avec une sensibilité équivalente à celle d'un système conventionnel. Enfin, la fonctionnalisation de la surface a été étudiée pour permettre l'accrochage de biomolécules en surface. Le système développé a permis la réalisation d'expériences biologiques complètes en présence d'une solution d'hybridation. Une diminution significative de la fluorescence parasite a été mesurée par rapport au système conventionnel.

Styles APA, Harvard, Vancouver, ISO, etc.

17

Silva, Ana. « Le nombre b-chromatique de quelques classes de graphes généralisant les arbres ». Grenoble, 2010. http://www.theses.fr/2010GRENM078.

Texte intégral

Résumé :

Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. Ces notions ont été introduites par Irving et Manlove en 1999. Elles permettent d'évaluer les performances de certains algorithmes de coloration. Irving et Manlove ont montré que le calcul du nombre b-chromatique d'un graphe est un problème NP-difficile et qu'il peut être résolu en temps polynomial pour les arbres. Une question qui se pose naturellement est donc d'enquêter sur les graphes qui ont une structure proche des arbres : cactus, graphes triangulés, graphes série-parallèles, "block" graphes, etc. Dans cette thèse, nous généralisons le résultat d'Irving et Manlove pour les cactus dont le "m-degré" est au moins 7 et pour les graphes planaires extérieurs dont la maille est au moins 8. (Le m-degré m(G) est le plus grand entier d tel que G a au moins d sommets de degré au moins d −1. ) Nous démontrons un résultat semblable pour le produit cartésien d'un arbre par une chaîne, un cycle ou une étoile. Pour ce qui concerne les graphes dont les blocs sont des cliques, nous montrons que le problème avec un nombre de couleurs fixé peut être résolu en temps polynomial et nous présentons des cas où le problème de décision peut être résolu. Toutefois, nous avons constaté que la différence m(G)−b(G) peut être arbitrairement grande pour les graphes blocs, ce qui montre qu'avoir une structure arborescence n'est pas suffisant pour que le graphe satisfasse b(G)>= m(G) − 1
Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. Ces notions ont été introduites par Irving et Manlove en 1999. Elles permettent d'évaluer les performances de certains algorithmes de coloration. Irving et Manlove ont montré que le calcul du nombre b-chromatique d'un graphe est un problème NP-difficile et qu'il peut être résolu en temps polynomial pour les arbres. Une question qui se pose naturellement est donc d'enquêter sur les graphes qui ont une structure proche des arbres : cactus, graphes triangulés, graphes série-parallèles, "block" graphes, etc. Dans cette thèse, nous généralisons le résultat d'Irving et Manlove pour les cactus dont le "m-degré" est au moins 7 et pour les graphes planaires extérieurs dont la maille est au moins 8. (Le m-degré m(G) est le plus grand entier d tel que G a au moins d sommets de degré au moins d −1. ) Nous démontrons un résultat semblable pour le produit cartésien d'un arbre par une chaîne, un cycle ou une étoile. Pour ce qui concerne les graphes dont les blocs sont des cliques, nous montrons que le problème avec un nombre de couleurs fixé peut être résolu en temps polynomial et nous présentons des cas où le problème de décision peut être résolu. Toutefois, nous avons constaté que la différence m(G)−b(G) peut être arbitrairement grande pour les graphes blocs, ce qui montre qu'avoir une structure arborescence n'est pas suffisant pour que le graphe satisfasse b(G)>= m(G) − 1

Styles APA, Harvard, Vancouver, ISO, etc.

18

Beaudou, Laurent. « Autour de problèmes de plongements de graphes ». Phd thesis, Université Joseph Fourier (Grenoble), 2009. http://tel.archives-ouvertes.fr/tel-00401226.

Texte intégral

Résumé :

Cette thèse s'articule autour de la notion de plongement de graphe. Un plongement de graphe consiste à envoyer les sommets d'un graphe dans une autre structure par une application qui conserve certaines propriétés à déterminer. Nous pouvons distinguer deux grandes familles de plongements. D'une part les plongements purement combinatoires qui envoient les éléments d'un graphe G dans un autre graphe H. La propriété la plus naturelle à conserver est la notion d'adjacence entre les sommets. Nous nous intéressons à la conservation d'une propriété supplémentaire : la distance entre les sommets. Nous caractérisons plusieurs familles de graphes se plongeant de cette façon dans les hypercubes ou les graphes de Hamming. Les plongements topologiques visent à représenter un graphe G sur une surface quelconque. Les sommets sont envoyés vers des points d'une surface et les arêtes vers des courbes continues entre ces points. Comment représenter un graphe afin de minimiser le nombre de croisements d'arêtes ? Nous nous posons ces questions à travers l'étude de la planarité et des nombres de croisements de certains graphes.

Styles APA, Harvard, Vancouver, ISO, etc.

19

Beaudou, Laurent. « Autour de problèmes de plongements de graphes ». Phd thesis, Grenoble 1, 2009. http://www.theses.fr/2009GRE10089.

Texte intégral

Résumé :

Cette thèse s'articule autour de la notion de plongement de graphe. Un plongement de graphe consiste à envoyer les sommets d'un graphe dans une autre structure par une application qui conserve certaines propriétés à déterminer. Nous pouvons distinguer deux grandes familles de plongements. D'une part les plongements purement combinatoires qui envoient les éléments d'un graphe G dans un autre graphe H. La propriété la plus naturelle à conserver est la notion d'adjacence entre les sommets. Nous nous intéressons à la conservation d'une propriété supplémentaire : la distance entre les sommets. Nous caractérisons plusieurs familles de graphes se plongeant de cette façon dans les hypercubes ou les graphes de Hamming. Les plongements topologiques visent à représenter un graphe G sur une surface quelconque. Les sommets sont envoyés vers des points d'une surface et les arêtes vers des courbes continues entre ces points. Comment représenter un graphe afin de minimiser le nombre de croisements d'arêtes ? Nous nous posons ces questions à travers l'étude de la planarité et des nombres de croisements de certains graphes
This Ph. D. Manuscript is built around the notion of graph embedding. An embedding of a graph G is an application mapping the vertices of G to elements of another structure, and preserving some properties of G. There are two types of embeddings. The combinatorial embeddings map the vertices of a graph G to the vertices of a graph H. The usual property that is preserved is the adjacency between vertices. In this thesis, we consider the isometric embeddings, preserving in addition the distances between vertices. We give some structural characterizations for families of graphs isometrically embeddable in hypercubes or Hamming graphs. The topological embeddings aim at drawing a graph G on some surface. Vertices are mapped to distinct points of the surface and the edges are represented by continuous curves linking these points. Is it possible to draw a graph G so that the edges do not cross eachother ? If not, what is the minimum number of crossings of a drawing of G ? We deal with these questions on different surfaces, or in relation with some graph operations as direct product or zip product

Styles APA, Harvard, Vancouver, ISO, etc.

20

Pennarun, Claire. « Planar graphs : non-aligned drawings, power domination and enumeration of Eulerian orientations ». Thesis, Bordeaux, 2017. http://www.theses.fr/2017BORD0609/document.

Texte intégral

Résumé :

Dans cette thèse, nous présentons trois problèmes concernant les graphes planaires.Nous travaillons tout d'abord sur les dessins planaires non-alignés, c'est-à-dire des dessins planaires de graphes sur une grille sans que deux sommets se trouvent sur la même ligne ou la même colonne.Nous caractérisons les graphes planaires possédant un tel dessin sur une grille de taille $n times n$, et nous présentons deux algorithmes générant un dessin planaire non-aligné avec arêtes brisées sur cette grille pour tout graphe planaire, avec $n-3$ ou $min(frac{2n-3}{5},$ $#{text{triangles s{'e}parateurs}}+1)$ brisures au total.Nous proposons également deux algorithmes dessinant un dessin planaire non-aligné sur des grilles d'aire $O(n^4)$. Nous donnons des résultats spécifiques concernant les graphes 4-connexes et de type triangle-emboîté.Le second sujet de cette thèse est la domination de puissance dans les graphes planaires. Nous exhibons une famille de graphes ayant un nombre de domination de puissance $gamma_P$ au moins égal à $frac{n}{6}$. Nous montrons aussi que pour tout graphe planaire maximal $G$ à $n geq 6$ sommets, $gamma_P(G) leq frac{n-2}{4}$. Enfin, nous étudions les grilles triangulaires $T_k$ à bord hexagonal de dimension $k$ et nous montrons que $frac{k}{3} - frac{1}{6} leq gamma_P(T_k) leq lceil frac{k}{3} rceil$.Nous étudions également l'énumération des orientations planaires Eulériennes. Nous proposons une nouvelle décomposition de ces cartes. En considérant les orientations des dernières $2k-1$ arêtes autour de la racine, nous définissons des sous- et sur-ensembles des orientations planaires Eulériennes paramétrés par $k$.Pour chaque classe, nous proposons un système d'équations fonctionnelles définissant leur série génératrice, et nous prouvons que celle-ci est toujours algébrique. Nous montrons ainsi que la constance de croissance des orientations planaires Eulériennes est entre 11.56 et 13.005
In this thesis, we present results on three different problems concerning planar graphs.We first give some new results on planar non-aligned drawings, i.e. planar grid drawings where vertices are all on different rows and columns.We show that not every planar graph has a non-aligned drawing on an $n times n$-grid, but we present two algorithms generating a non-aligned polyline drawings on such a grid requiring either $n-3$ or $min(frac{2n-3}{5},$ $#{text{separating triangles}}+1)$ bends in total.Concerning non-minimal grids, we give two algorithms drawing a planar non-aligned drawing on grids with area of order $n^4$. We also give specific results for 4-connected graphs and nested-triangle graphs.The second topic is power domination in planar graphs. We present a family of graphs with power dominating number $gamma_P$ at least $frac{n}{6}$. We then prove that for every maximal planar graph $G$ of order $n$, $gamma_P(G) leq frac{n-2}{4}$, and we give a constructive algorithm.We also prove that for triangular grids $T_k$ of dimension $k$ with hexagonal-shape border, $frac{k}{3} - frac{1}{6} leq gamma_P(T_k) leq lceil frac{k}{3} rceil$.Finally, we focus on the enumeration of planar Eulerian orientations. After proposing a new decomposition for these maps, we define subsets and supersets of planar Eulerian orientations with parameter $k$, generated by looking at the orientations of the last $2k-1$ edges around the root vertex.For each set, we give a system of functional equations defining its generating function, and we prove that it is always algebraic.This way, we show that the growth rate of planar Eulerian orientations is between 11.56 and 13.005

Styles APA, Harvard, Vancouver, ISO, etc.

21

Bouttier, Jérémie. « Physique statistique des surfaces aléatoires et combinatoire bijective des cartes planaires ». Phd thesis, Université Pierre et Marie Curie - Paris VI, 2005. http://tel.archives-ouvertes.fr/tel-00010651.

Texte intégral

Résumé :

Les cartes sont des objets combinatoires apparaissant en physique comme discrétisation naturelle des surfaces aléatoires employées pour la gravité quantique bidimensionnelle ou la théorie des cordes, ainsi que dans les modèles de matrices. Après rappel de ces relations, nous établissons des correspondances entre diverses classes de cartes et d'arbres, autres objets combinatoires de structure simple. Un premier intérêt mathématique de ces constructions est de donner des preuves bijectives, élémentaires et rigoureuses, de plusieurs résultats d'énumération de cartes. Par ailleurs, nous accédons ainsi à une information fine sur la géométrie intrinsèque des cartes, conduisant à des résultats analytiques exacts grâce à une propriété inattendue d'intégrabilité. Nous abordons enfin la question de l'existence d'une limite continue universelle.

Styles APA, Harvard, Vancouver, ISO, etc.

22

Gire, Sophie. « Arbres, permutations à motifs exclus et cartes planaires : quelques problèmes algorithmiques et combinatoires ». Bordeaux 1, 1993. http://www.theses.fr/1993BOR10534.

Texte intégral

Résumé :

Dans ce travail, nous nous interessons aux arbres en tant que structure de donnees dans divers algorithmes et en tant qu'outil pour la generation d'objets combinatoires. Dans une premiere partie, nous donnons des valeurs exactes pour le cout au pire (complexite amortie) de certaines transformations sur les arbres intervenant dans plusieurs algorithmes, comme l'algorithme de gestion de partitions et l'algorithme d'exclusion mutuelle de naimi et trehel. Dans la seconde partie, nous resolvons quelques problemes d'enumeration de permutations a motifs exclus par le biais de la caracterisation d'arbres de generations de ces objets par un systeme de reecriture. En particulier, nous etablissons une bijection entre les permutations triables par deux passages consecutifs dans une pile et les cartes planaires pointees non separables et en deduisons des formules d'enumeration pour ces permutations suivant plusieurs parametres

Styles APA, Harvard, Vancouver, ISO, etc.

23

Valicov, Petru. « Problèmes de placement, de coloration et d’identification ». Thesis, Bordeaux 1, 2012. http://www.theses.fr/2012BOR14549/document.

Texte intégral

Résumé :

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques.La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum ID est n-1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour le paramètre ID dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ID dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits
In this thesis we study three theoretical computer science problems, namely the orthogonal packing problem (OPP for short), strong edge-colouring and identifying codes.OPP consists in testing whether a set of rectangular items can be packed in a rectangular container without overlapping and without exceeding the borders of this container. An additional constraint is that the rotation of the items is not allowed. The problem is NP-hard even when the problem is reduced to packing squares in a square. We propose an exact algorithm for solving OPP efficiently using the characterization of the problem by interval graphs proposed by Fekete and Schepers. For this purpose we use some compact representation of interval graphs - MPQ-trees. We show experimental results of our approach by comparing them to the results of other algorithms known in the literature. we observe promising gains.The study of strong edge-colouring and identifying codes is focused on the structural and computational aspects of these combinatorial problems. In the case of strong edge-colouring we are interested in the families of planar graphs and subcubic graphs. We show optimal upper bounds for the strong chromatic index of subcubic graphs as a function of the maximum average degree. We also show that every planar subcubic graph without induced cycles of length 4 and 5 can be strong edge-coloured with at most nine colours. Finally, we confirm the difficulty of the problem by showing that it remains NP-complete even in some restricted classes of planar subcubic graphs.For the subject of identifying codes we propose a characterization of non-trivial graphs having maximum identifying code number ID, that is n-1, where n is the number of vertices. We study the case of line graphs and prove lower and upper bounds for ID parameter in this class. At last we investigate the complexity of the corresponding decision problem and show the existence of a linear algorithm for computing ID of the line graph L(G) where G has the size of the tree-width bounded by a constant. On the other hand, we show that the identifying code problem is NP-complete in various subclasses of planar graphs

Styles APA, Harvard, Vancouver, ISO, etc.

24

Dai, Tianjiao. « Some vertex colouring problems and a generalisation of Hamilton-connectivity in graphs ». Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG067.

Texte intégral

Résumé :

La décomposition des graphes fait référence au processus de décomposer un graphe complexe en composantes plus simples et plus petites, souvent dans le but d'analyser ou de résoudre des problèmes liés au graphe. Il s'agit d'un outil important pour représenter la structure globale et les propriétés d'une manière plus détaillée. Il est aussi également utile pour résoudre des problèmes impliquant la recherche de structures spécifiques dans un graphe. Il existe plusieurs types courants de techniques de décomposition de graphe largement utilisées en théorie des graphes et dans des domaines connexes, notamment la décomposition en arbres, la décomposition en blocs, la décomposition modulaire, la décomposition hiérarchique, etc. Cette thèse étudie deux types de décomposition de sommets d'un graphe : les colorations propres (décomposition en ensembles indépendants) et la Hamilton-connectivité (décomposition en chemins internement disjoints entre deux ensembles où les chemins couvrent tous les sommets du graphe)
The decomposition of graphs refers to the process of breaking down a complex graph into simpler, smaller components, often with the goal of analysing or solving problems related to the graph. It is an important tool to display the global structure and properties in a more fine-grained manner, and also useful in solving problems that involve finding specific structures in a graph. There are several common types of graph decomposition techniques that are widely used in graph theory and related fields, including tree decomposition, block decomposition, modular decomposition, hierarchical decomposition, etc. This thesis studies two kinds of vertex decomposition of a graph: proper colourings (decomposition into independent sets) and Hamilton-connectivity (decomposition into internally-disjoint paths between two sets where the paths cover all the vertices of graphs)

Styles APA, Harvard, Vancouver, ISO, etc.

25

Marcus, Michel. « Cartes, hypercartes et diagrammes de cordes ». Bordeaux 1, 1997. http://www.theses.fr/1997BOR10509.

Texte intégral

Résumé :

Il s'agit de generaliser aux graphes plonges dans une surface de genre quelconque des resultats connus pour les cartes planaires. Les principaux resultats sont: une bijection entre les cartes de genre donne ayant n aretes et une famille de diagrammes de meme genre ayant n cordes. L'enumeration des diagrammes non isomorphes de genre 1. L'enumeration des diagrammes non isomorphes de genre maximal

Styles APA, Harvard, Vancouver, ISO, etc.

26

Naves, Guyslain. « Routages optimaux : tours, flots et chemins ». Phd thesis, Grenoble, 2010. http://tel.archives-ouvertes.fr/tel-00465585.

Texte intégral

Résumé :

L'étude des cycles, flots et chemins des graphes est intimement liée au développement de l'optimisation combinatoire. Dans l'introduction nous mettons en parallèle ces concepts à partir de résultats classiques, et les deux autres parties de la thèse développent les nouveaux résultats dans deux directions différentes. La première porte sur les problèmes d'existence de multiflots entiers. Plusieurs paramètres naturels s'appliquent à ces problèmes, générant plus d'une centaine de cas. Après un rappel des résultats de la littérature sous une forme synthétique, nous résolvons plusieurs problèmes ouverts. En particulier, nous montrons que trouver deux flots disjoints dans les graphes planaires est un problème NP-complet. Nous donnons aussi un algorithme polynomial pour router les digraphes planaires acycliques eulériens, lorsque le nombre de classes d'arcs de demande est fixé. Ensuite, nous nous intéressons au problème consistant à trouver une plus courte marche fermée passant par tous les sommets d'un graphe. Spéciquement, nous cherchons à caractériser les graphes pour lesquels une bonne caractérisation est donnée par des empilements d'ensembles éclatants. Nous présentons quelques résultats de nature polyédrale, puis étudions le cas des cographes et des graphes d'intervalles.

Styles APA, Harvard, Vancouver, ISO, etc.

27

Hocquard, Hervé. « Colorations de graphes sous contraintes ». Phd thesis, Université Sciences et Technologies - Bordeaux I, 2011. http://tel.archives-ouvertes.fr/tel-00987686.

Texte intégral

Résumé :

Dans cette thèse, nous nous intéressons à différentes notions de colorations sous contraintes. Nous nous intéressons plus spécialement à la coloration acyclique, à la coloration forte d'arêtes et à la coloration d'arêtes sommets adjacents distinguants.Dans le Chapitre 2, nous avons étudié la coloration acyclique. Tout d'abord nous avons cherché à borner le nombre chromatique acyclique pour la classe des graphes de degré maximum borné. Ensuite nous nous sommes attardés sur la coloration acyclique par listes. La notion de coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. De notre côté, nous avons proposé des conditions suffisantes de 3-liste coloration acyclique des graphes planaires. Dans le Chapitre 3, nous avons étudié la coloration forte d'arêtes des graphes subcubiques en majorant l'indice chromatique fort en fonction du degré moyen maximum. Nous nous sommes également intéressés à la coloration forte d'arêtes des graphes subcubiques sans cycles de longueurs données et nous avons également obtenu une majoration optimale de l'indice chromatique fort pour la famille des graphes planaires extérieurs. Nous avons aussi présenté différents résultats de complexité pour la classe des graphes planaires subcubiques. Enfin, au Chapitre 4, nous avons abordé la coloration d'arêtes sommets adjacents distinguants en déterminant les majorations de l'indice avd-chromatique en fonction du degré moyen maximum. Notre travail s'inscrit dans la continuité de celui effectué par Wang et Wang en 2010. Plus précisément, nous nous sommes focalisés sur la famille des graphes de degré maximum au moins 5.

Styles APA, Harvard, Vancouver, ISO, etc.

28

Chen, Linxiao. « Cartes planaires aléatoires couplées aux systèmes de spins ». Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS096/document.

Texte intégral

Résumé :

Cette thèse vise à améliorer notre compréhension des cartes planaires aléatoires décorées par les modèles de physique statistique. On examine trois modèles particuliers à l'aide des outils provenant de l'analyse, de la combinatoire et des probabilités. Dans une perspective géométrique, on se concentre sur les propriétés des interfaces et les limites locales des cartes aléatoires décorées. Le premier modèle consiste en une famille de quadrangulations aléatoires du disque décorées par un modèle de boucles O(n). Après avoir complété la preuve de son diagramme de phase initiée par [BBG12c] (chap. II), on étudie les longueurs et la structure d'imbrication des boucles dans la phase critique non-générique (chap. III). On montre que ces statistiques, décrites par un arbre étiqueté, convergent en loi vers une cascade multiplicative explicite lorsque le périmètre du disque tend vers l'infini. Le deuxième modèle (chap. IV) consiste en une carte planaire aléatoire décorée par la percolation de Fortuin-Kasteleyn. On complète la preuve de la convergence du modèle esquissée dans [She16b] et établit un certain nombre de propriétés de la limite. Le troisième modèle (chap. V) est celui des triangulations aléatoires du disque décorées par le modèle d'Ising. Il est étroitement lié au modèle des quadrangulations décorées par un modèle O(n) quand n=1. On calcule explicitement la fonction de partition du modèle muni des conditions au bord de Dobrushin au point critique, sous une forme exploitable pour les asymptotiques. À l'aide de ces asymptotiques, on étudie le processus d'épluchage le long de l'interface d'Ising dans la limite où le périmètre du disque tend vers l'infini. Mots clés. Carte planaire aléatoire, modèle de boucles O(n), percolation de Fortuin-Kasteleyn, modèle d'Ising, limite locale, géométrie d'interfaces
The aim of this thesis is to improve our understanding of random planar maps decorated by statistical physics models. We examine three particular models using tools coming from analysis, combinatorics and probability. From a geometric perspective, we focus on the interface properties and the local limits of the decorated random maps. The first model defines a family of random quadrangulations of the disk decorated by an O(n)-loop model. After completing the proof of its phase diagram initiated in [BBG12c] (Chap. II), we look into the lengths and the nesting structure of the loops in the non-generic critical phase (Chap. III). We show that these statistics, described as a labeled tree, converge in distribution to an explicit multiplicative cascade when the perimeter of the disk tends to infinity. The second model (Chap. IV) consists of random planar maps decorated by the Fortuin-Kasteleyn percolation. We complete the proof of its local convergence sketched in [She16b] and establish a number of properties of the limit. The third model (Chap. V) is that of random triangulations of the disk decorated by the Ising model. It is closely related to the O(n)-decorated quadrangulation when n=1. We compute explicitly the partition function of the model with Dobrushin boundary conditions at its critical point, in a form ameneable to asymptotics. Using these asymptotics, we study the peeling process along the Ising interface in the limit where the perimeter of the disk tends to infinity.Key words. Random planar map, O(n) loop model, Fortuin-Kasteleyn percolation, Ising model, local limit, interface geometry

Styles APA, Harvard, Vancouver, ISO, etc.

29

Mazoit, Frédéric. « Décomposition algorithmique des graphes ». Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2004. http://tel.archives-ouvertes.fr/tel-00148807.

Texte intégral

Résumé :

Dans cette thèse, nous nous intéressons à deux types de décompositions des graphes introduits par Robertson et Seymour: les décompositions arborescentes et les décompositions en branches. À ces décompositions sont associés deux paramètres des graphes: la largeur arborescente et la largeur de branches. Nous montrons que ces deux décompositions peuvent être vues comme issues d'une même structure combinatoire; les deux paramètres mentionné ci-dessus sont égaux aux valeurs minimales de deux paramètres de cette structure commune. En poussant plus avant cette analogie, nous montrons comment adapter une technique de calcul de la largeur arborescente au calcul de la largeur de branches. Ceci nous permet de calculer la largeur de branches des graphes de nombre astéroïde borné ayant un nombre polynômial de séparateurs minimaux et celle des graphes d-trapézoïdes circulaires. Ce parallèle nous permet aussi d'adapter certains résultats structurels sur les décompositions en branches aux décompositions arborescentes. Dans le cas des graphes planaires, nous interprétons ces propriétés à l'aide d'outils topologiques. De cette façon, nous donnons une démonstration simple d'un théorème de dualité reliant la largeur arborescente d'un graphe planaire et celle de son dual. Ces outils nous permettent aussi d'énumérer de façon efficace les séparateurs minimaux des graphes planaires.

Styles APA, Harvard, Vancouver, ISO, etc.

30

Lehéricy, Thomas. « Cycles séparants, isopérimétrie et modifications de distances dans les grandes cartes planaires aléatoires ». Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS476/document.

Texte intégral

Résumé :

Les cartes planaires sont des graphes planaires dessinés sur la sphère et vus à déformation près. De nombreuses propriétés des cartes sont supposées universelles, dans le sens où elles ne dépendent pas des détails du modèle choisi. Nous commençons par établir une inégalité isopérimétrique dans la quadrangulation infinie du plan. Nous confirmons également une conjecture de Krikun portant sur la longueur des cycles les plus courts séparant la boule de rayon $r$ de l'infini. Dans un deuxième temps, nous nous intéressons à l'effet de modifications de distances sur la géométrie à grande échelle des quadrangulations uniformes, élargissant la classe d'universalité de la carte brownienne. Nous montrons également que la bijection de Tutte, entre quadrangulations et cartes planaires, est asymptotiquement une isométrie. Enfin, nous établissons une borne supérieure sur le temps de mélange de la marche aléatoire dans les cartes aléatoires
Planar maps are planar graphs drawn on the sphere and seen up to deformation. Many properties of maps are conjectured to be universal, in the sense that they do not depend on the details of the model.We begin by establishing an isoperimetric inequality in the infinite quadrangulation of the plane. We also confirm a conjecture by Krikun concerning the length of the shortest cycles separating the ball of radius $r$ from infinity. We then consider the effect of modifications of distances on the large-scale geometry of uniform quadrangulations, extending the universality class of the Brownian map. We also show that the Tutte bijection, between quadrangulations and planar maps, is asymptotically an isometry. Finally, we establish an upper bound on the mixing time of the random walk in random maps

Styles APA, Harvard, Vancouver, ISO, etc.

31

Pierron, Théo. « Induction Schemes : From Language Separation to Graph Colorings ». Thesis, Bordeaux, 2019. http://www.theses.fr/2019BORD0119/document.

Texte intégral

Résumé :

Cette thèse présente des résultats obtenus dans deux domaines : la théorie des langages, et la théorie des graphes. En théorie des langages, on s’intéresse à des problèmes de caractérisation de classes de langages réguliers. Le problème générique consiste à déterminer si un langage régulier donné peut être défini dans un certain formalisme. Les méthodes actuelles font intervenir un problème plus général appelé séparation. On présente ici deux types de contributions : une généralisation d’un résultat de décidabilité au cadre des langages de mots infinis, ainsi que des bornes inférieures pour la complexité du problème de séparation. En théorie des graphes, on considère le problème classique de coloration de graphes, où on cherche à attribuer des couleurs aux sommets d’un graphe de sorte que les sommets adjacents reçoivent des couleurs différentes, le but étant d’utiliser le moins de couleurs possible. Dans le cas des graphes peu denses, la méthode de déchargement est un atout majeur. Elle a notamment joué un rôle décisif dans la preuve du théorème des quatre couleurs. Cette méthode peut être vue comme une construction non conventionnelle d’un schéma de preuve par induction, spécifique à la classe de graphes et à la propriété considérées, et où la validité du schéma est rarement immédiate. On utilise des variantes de la méthode de déchargement pour étudier deux types de problèmes de coloration
In this thesis, we present results obtained in two fields: formal language theory and graph theory. In formal language theory, we consider some problems of characterization of classes of regular languages. The generic problem consists in determining whether a given regular language can be defined in a fixed formalism. The current approaches use a more general problem called separation. We present here two types of contributions: a generalization of a decidability result to the setting of infinite words, together with lower bounds for the complexity of the separation problem. In graph theory, we consider the classical problem of graph coloring, where we assign colors to vertices of a graph in such a way that two adjacent vertices receive different colors. The goal is to use the fewest colors. When the graphs are sparse, a crucial tool for this is the discharging method. It is most notably decisive in the proof of the Four-Color Theorem. This method can be seen as an unconventional construction of an inductive proof scheme, specific to the considered problem and graph class, where arguing the validity of the scheme is rarely immediate. We use variants of the discharging method to study two types of coloring problems

Styles APA, Harvard, Vancouver, ISO, etc.

32

Castelli, Aleardi Luca. « Représentations compactes de structures de données géométriques ». Phd thesis, Ecole Polytechnique X, 2006. http://tel.archives-ouvertes.fr/tel-00336188.

Texte intégral

Résumé :

Nous considérons le problème de concevoir des représentations compactes ou succinctes de structures de données géométriques. Dans ce cadre, en plus des questions de simple compression, l'attention est portée sur l'étude de structures de données nécessitant une petite quantité de ressources mémoire et permettant de répondre à des requêtes locales en temps O(1). L'une des contributions de cette thèse consiste à proposer un cadre algorithmique général pour la conception de représentations compactes de structures telles que les graphes planaires et les maillages surfaciques. Comme application nous présentons différentes structures spécialement conçues pour représenter de manière compacte la connectivité (ou information combinatoire) de certaines classes de graphes localement planaires. Pour le cas des triangulations planaires à m faces, nous proposons une représentation compacte de l'information combinatoire nécessitant asymptotiquement 2:175 bits par triangle pour le coût en espace et qui permet la navigation entre triangles adjacents, ainsi que d'autres requêtes locales d'incidence entre sommets, en temps constant : cette structure est ainsi optimale pour la classe des triangulations ayant un bord de taille arbitraire. Une telle représentation reste valide et optimale dans le cas de triangulations d'une surface de genre g borné : O(g lgm) bits supplémentaires sont alors nécessaires. Cette représentation est bien adaptée pour faire une mise à jour locale efficace de la triangulation. Plus précisément, il est possible d'effectuer des mises à jour en temps O(1) amorti après insertion de sommets, et en temps O(log2m) amorti après suppression de sommets et flip d'arêtes. Et en ce qui concerne les triangulations et les graphes planaires 3-connexes, correspondant aux maillages triangulaires et polygonaux homéomorphes à une sphère, nous proposons les premières représentations succinctes optimales : elles atteignent l'entropie respective des deux classes, 2 bits par arête pour les graphes 3-connexes, et 1:62 bits par triangle (ou 3:24 bits par sommet) pour les triangulations. Ces structures permettent aussi l'accès en temps O(1) aux informations associées aux sommets, notamment leurs coordonnées. Cependant nous ne traitons pas ici la compression de cette information géométrique.

Styles APA, Harvard, Vancouver, ISO, etc.

33

Bonichon, Nicolas. « Aspects algorithmiques et combinatoires des réaliseurs des graphes plans maximaux ». Phd thesis, Université Sciences et Technologies - Bordeaux I, 2002. http://tel.archives-ouvertes.fr/tel-00338407.

Texte intégral

Résumé :

Les réaliseurs, ou arbres de Schnyder, ont été introduits par Walter Schnyder à la fin des années 80 pour caractériser les graphes planaires, puis pour dessiner ces mêmes graphes sur des grilles $(n-2)\times(n-2)$.
Dans ce document nous proposons dans un premier temps une extension du théorème de Wagner aux réaliseurs, qui nous permet d'établir une relation entre le nombre de feuilles et le nombre de faces tricolores d'un réaliseur.
Ensuite, à l'aide d'une bijection entre les réaliseurs et les paires de chemins de Dyck qui ne se coupent pas, nous énumérons les réaliseurs. Un algorithme de génération aléatoire de $p$ chemins de Dyck ne se coupant pas, est également présenté. Il permet en outre de générer aléatoirement des réaliseurs en temps linéaire.
Puis nous montrons que grâce aux réaliseurs, il est possible de dessiner, à l'aide de lignes brisées des graphes planaires sur des grilles de largeur et de surface optimales.
Enfin, nous proposons une généralisation des réaliseurs minimaux aux graphes planaires connexes : les arbres recouvrants bien-ordonnés. Grâce à cette généralisation ainsi qu'à une méthode de triangulation adaptée nous proposons un algorithme de codage des graphes planaires à $n$ sommets en $5,007n$ bits.

Styles APA, Harvard, Vancouver, ISO, etc.

34

Courtiel, Julien. « Combinatoire du polynôme de Tutte et des cartes planaires ». Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0083/document.

Texte intégral

Résumé :

Cette thèse porte sur le polynôme de Tutte, étudié selon différents points de vue. Dans une première partie, nous nous intéressons à l’énumération des cartes planaires munies d’une forêt couvrante, ici appelées cartes forestières, avec un poids z par face et un poids u par composante non racine de la forêt. De manière équivalente, nous comptons selon le nombre de faces les cartes planaires C pondérées par TC(u + 1; 1), où TC désigne le polynôme de Tutte de C. Nous commençons par une caractérisation purement combinatoire de la série génératrice correspondante, notée F(z; u). Nous en déduisons que F(z; u) est différentiellement algébrique en z, c’est-à-dire que F satisfait une équation différentielle polynomiale selon z. Enfin, pour u ≥ -1, nous étudions le comportement asymptotique du n-ième coefficient de F(z; u). Nous observons une transition de phase en 0, avec notamment un régime très atypique en n-3 ln-2(n) pour u ϵ [-1; 0[, témoignant d’une nouvelle classe d’universalité pour les cartes planaires. Dans une seconde partie, nous proposons un cadre unificateur pour les différentes notions d’activités utilisées dans la littérature pour décrire le polynôme de Tutte.La nouvelle notion d’activité ainsi définie est appelée Δ-activité. Elle regroupe toutes les notions d’activité déjà connues et présente de belles propriétés, comme celle de Crapo qui définit une partition (adaptée à l’activité) du treillis des sous-graphes couvrants en intervalles. Nous conjecturons en dernier lieu que toute activité qui décrit le polynôme de Tutte et qui satisfait la propriété susmentionnée de Crapo peut être définie en termes de Δ-activités
This thesis deals with the Tutte polynomial, studied from different points of view. In the first part, we address the enumeration of planar maps equipped with a spanning forest, here called forested maps, with a weight z per face and a weight u per non-root component of the forest. Equivalently, we count (with respect to the number of faces) the planar maps C weighted by TC(u + 1; 1), where TC is the Tutte polynomial of C.We begin by a purely combinatorial characterization of the corresponding generating function, denoted by F(z; u). We deduce from this that F(z; u) is differentially algebraic in z, that is, satisfies a polynomial differential equation in z. Finally, for u ≥ -1, we study the asymptotic behaviour of the nth coefficient of F(z; u).We observe a phase transition at 0, with a very unusual regime in n-3 ln-2(n) for u ϵ [-1; 0[, which testifiesa new universality class for planar maps. In the second part, we propose a framework unifying the notions of activity used in the literature to describe the Tutte polynomial. The new notion of activity thereby defined is called Δ-activity. It gathers all the notions of activities that were already known and has nice properties, as Crapo’s property that defines a partition of the lattice of the spanning subgraphs into intervals with respect to the activity. Lastly we conjecture that every activity that describes the Tutte polynomial and that satisfies Crapo’s property can be defined in terms of Δ-activity

Styles APA, Harvard, Vancouver, ISO, etc.

35

Dross, François. « Vertex partition of sparse graphs ». Thesis, Montpellier, 2018. http://www.theses.fr/2018MONTS011/document.

Texte intégral

Résumé :

Le Théorème des Quatre Couleurs, conjecturé en 1852 et prouvé en 1976, est à l'origine de l'étude des partitions des sommets de graphes peu denses. Il affirme que toute carte plane peut être coloriée avec au plus quatre couleurs différentes, de telle manière que deux régions qui partagent une frontière aient des couleurs différentes. Énoncé en terme de théorie des graphes, cela veut dire que tout graphe planaire, c'est à dire tout graphe qui peut être représenté dans le plan sans que deux arêtes ne se croisent, peut voir son ensemble de sommets partitionné en quatre ensembles tels que chacun de ces ensembles ne contient pas les deux extrémités d'une même arête. Une telle partition est appelée une coloration propre en quatre couleurs. Dans cette thèse, on s'intéresse à l'étude de la structure des graphes peu denses, selon différentes notions de densité. D'une part, on étudie les graphes planaires sans petits cycles, et d'autre part les graphes dont tous les sous-graphes ont un degré moyen peu élevé. Pour ces classes de graphes, on recherche tout d'abord le plus petit nombre de sommets à retirer pour obtenir une forêt, c'est à dire un graphe sans cycles. Cela peut être vu comme une partition des sommets du graphe en un ensemble induisant une forêt et un ensemble de sommets contenant au plus une fraction donnée des sommets du graphe. La motivation première de cette étude est une conjecture d'Albertson et Berman (1976) comme quoi tout graphe planaire admettrait une telle partition où la forêt contient au moins la moitié des sommets du graphe. Dans un second temps, on s'intéresse aux partitions des sommets de ces graphes en deux ensembles, tels que les sous-graphes induits par ces deux ensembles ont des propriétés particulières. Par exemple, ces sous-graphes peuvent être des graphes sans arêtes, des forêts, des graphes de degré borné, ou des graphes dont les composantes connexes ont un nombre borné de sommets. Ces partitions des sommets sont des extensions de la notion de coloration propre de graphe.On montre, pour différentes classes de graphes peu denses, que tous les graphes de ces classes admettent de telles partitions. On s'intéresse également aux aspect algorithmiques de la construction de telles partitions
The study of vertex partitions of planar graphs was initiated by the Four Colour Theorem, which was conjectured in 1852, and proven in 1976. According to that theorem, one can colour the regions of any planar map by using only four colours, in such a way that any two regions sharing a border have distinct colours. In terms of graph theory, it can be reformulated this way: the vertex set of every planar graph, i.e. every graph that can be represented in the plane such that edges do not cross, can be partitioned into four sets such that no edge has its two endpoints in the same set. Such a partition is called a proper colouring of the graph.In this thesis, we look into the structure of sparse graphs, according to several notions of sparsity. On the one hand, we consider planar graphs with no small cycles, and on the other hand, we consider the graphs where every subgraph has bounded average degree.For these classes of graphs, we first look for the smallest number of vertices that can be removed such that the remaining graph is a forest, that is a graph with no cycles. That can be seen as a partition of the vertices of the graph into a set inducing a forest and a set with a bounded fraction of the vertices of the graph. The main motivation for this study is a the Albertson and Berman Conjecture (1976), which states that every planar graph admits an induced forest containing at least one half of its vertices.We also look into vertex partition of sparse graphs into two sets both inducing a subgraph with some specific prescribed properties. Exemples of such properties can be that they have no edges, or no cycles, that they have bounded degree, or that they have bounded components. These vertex partitions generalise the notion of proper colouring. We show, for different classes of sparse graphs, that every graph in those classes have some specific vertex partition. We also look into algorithmic aspects of these partitions

Styles APA, Harvard, Vancouver, ISO, etc.

36

Stephenson, Robin. « Divers aspects des arbres aléatoires : des arbres de fragmentation aux cartes planaires infinies ». Thesis, Paris 9, 2014. http://www.theses.fr/2014PA090024/document.

Texte intégral

Résumé :

Nous nous intéressons à trois problèmes issus du monde des arbres aléatoires discrets et continus. Dans un premier lieu, nous faisons une étude générale des arbres de fragmentation auto-similaires, étendant certains résultats de Haas et Miermont en 2006, notamment en calculant leur dimension de Hausdorff sous des hypothèses malthusiennes. Nous nous intéressons ensuite à une suite particulière d’arbres discrets k-aires, construite de manière récursive avec un algorithme similaire à celui de Rémy de 1985. La taille de l’arbre obtenu à la n-ième étape est de l’ordre de n^(1/k), et après renormalisation, on trouve que la suite converge en probabilité vers un arbre de fragmentation. Nous étudions également des manières de plonger ces arbres les uns dans les autres quand k varie. Dans une dernière partie, nous démontrons la convergence locale en loi d’arbres de Galton-Watson multi-types critiques quand on les conditionne à avoir un grand nombre de sommets d’un certain type fixé. Nous appliquons ensuite ce résultat aux cartes planaires aléatoire pour obtenir la convergence locale en loi de grandes cartes de loi de Boltzmann critique vers une carte planaire infinie
We study three problems related to discrete and continuous random trees. First, we do a general study of self-similar fragmentation trees, extending some results established by Haas and Miermont in 2006, in particular by computing the Hausdorff dimension of these trees under some Malthusian hypotheses. We then work on a particular sequence of k-ary growing trees, defined recursively with a similar method to Rémy’s algorithm from 1985. We show that the size of the tree obtained at the n-th step if of order n^(1/k), and, after renormalization, we prove that the sequence convergences to a fragmentation tree. We also study embeddings of the limiting trees as k varies. In the last chapter, we show the local convergence in distribution of critical multi-type Galton-Watson trees conditioned to have a large number of vertices of a fixed type. We then apply this result to the world of random planar maps, obtaining that large critical Boltzmann-distributed maps converge locally in distribution to an infinite planar map

Styles APA, Harvard, Vancouver, ISO, etc.

37

Chen, Min. « Vertex coloring of graphs via the discharging method ». Thesis, Bordeaux 1, 2010. http://www.theses.fr/2010BOR14090/document.

Texte intégral

Résumé :

Dans cette thèse, nous nous intéressons à differentes colorations des sommets d’un graphe et aux homomorphismes de graphes. Nous nous intéressons plus spécialement aux graphes planaires et aux graphes peu denses. Nous considérons la coloration propre des sommets, la coloration acyclique, la coloration étoilée, lak-forêt-coloration, la coloration fractionnaire et la version par liste de la plupart de ces concepts.Dans le Chapitre 2, nous cherchons des conditions suffisantes de 3-liste colorabilité des graphes planaires. Ces conditions sont exprimées en termes de sous-graphes interdits et nos résultats impliquent plusieurs résultats connus.La notion de la coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud, et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. Dans le Chapitre 3, on obtient des conditions suffisantes pour qu’un graphe planaire admette une k-coloration acyclique par liste avec k 2 f3; 4; 5g.Dans le Chapitre 4, nous montrons que tout graphe subcubique est 6-étoilé coloriable.D’autre part, Fertin, Raspaud et Reed ont montré que le graphe de Wagner ne peut pas être 5-étoilé-coloriable. Ce fait implique que notre résultat est optimal. De plus, nous obtenons des nouvelles bornes supérieures sur la choisissabilité étoilé d’un graphe planaire subcubique de maille donnée.Une k-forêt-coloration d’un graphe G est une application ¼ de l’ensemble des sommets V (G) de G dans l’ensemble de couleurs 1; 2; ¢ ¢ ¢ ; k telle que chaque classede couleur induit une forêt. Le sommet-arboricité de G est le plus petit entier ktel que G a k-forêt-coloration. Dans le Chapitre 5, nous prouvons une conjecture de Raspaud et Wang affirmant que tout graphe planaire sans triangles intersectants admet une sommet-arboricité au plus 2.Enfin, au Chapitre 6, nous nous concentrons sur le problème d’homomorphisme des graphes peu denses dans le graphe de Petersen. Plus précisément, nous prouvons que tout graphe sans triangles ayant un degré moyen maximum moins de 5=2 admet un homomorphisme dans le graphe de Petersen. En outre, nous montrons que la borne sur le degré moyen maximum est la meilleure possible
In this thesis, we are interested in various vertex coloring and homomorphism problems of graphs with special emphasis on planar graphs and sparsegraphs. We consider proper vertex coloring, acyclic coloring, star coloring, forestcoloring, fractional coloring and the list version of most of these concepts.In Chapter 2, we consider the problem of finding sufficient conditions for a planargraph to be 3-choosable. These conditions are expressed in terms of forbiddensubgraphs and our results extend several known results.The notion of acyclic list coloring of planar graphs was introduced by Borodin,Fon-Der Flaass, Kostochka, Raspaud, and Sopena. They conjectured that everyplanar graph is acyclically 5-choosable. In Chapter 3, we obtain some sufficientconditions for planar graphs to be acyclically k-choosable with k 2 f3; 4; 5g.In Chapter 4, we prove that every subcubic graph is 6-star-colorable. On theother hand, Fertin, Raspaud and Reed showed that the Wagner graph cannot be5-star-colorable. This fact implies that our result is best possible. Moreover, weobtain new upper bounds on star choosability of planar subcubic graphs with givengirth.A k-forest-coloring of a graph G is a mapping ¼ from V (G) to the set f1; ¢ ¢ ¢ ; kgsuch that each color class induces a forest. The vertex-arboricity of G is the smallestinteger k such that G has a k-forest-coloring. In Chapter 5, we prove a conjecture ofRaspaud and Wang asserting that every planar graph without intersecting triangleshas vertex-arboricity at most 2.Finally, in Chapter 6, we focus on the homomorphism problems of sparse graphsto the Petersen graph. More precisely, we prove that every triangle-free graph withmaximum average degree less than 5=2 admits a homomorphism to the Petersengraph. Moreover, we show that the bound on the maximum average degree in ourresult is best possible

Styles APA, Harvard, Vancouver, ISO, etc.

38

Budzinski, Thomas. « Cartes aléatoires hyperboliques ». Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS426/document.

Texte intégral

Résumé :

Cette thèse s'inscrit dans la théorie des cartes planaires aléatoires, active depuis une quizaine d'années, et plus précisément dans l'étude de modèles de nature hyperbolique.Dans un premier temps, nous nous intéressons à un modèle de triangulations aléatoires dynamiques basé sur les flips d'arêtes, et nous montrons une borne inférieure sur le temps de mélange de ce modèle.Dans la suite, l'objet d'étude principal est une famille de triangulations aléatoires hyperboliques, appelées PSHT. Il s'agit de variantes de la triangulation uniforme du plan (UIPT), qui ont été introduites en 2014 par Nicolas Curien. Nous commençons par établir un résultat de limite d'échelle quasi-critique : si on renormalise les distances tout en faisant tendre le paramètre d'hyperbolicité vers sa valeur critique, les triangulations étudiées convergent vers un espace métrique aléatoire appelé plan brownien hyperbolique. Nous étudions également des propriétés métriques fines des PSHT et du plan brownien hyperbolique, et notamment la structure de leurs géodésiques infinies. Nous présentons aussi de nouvelles propriétés de la frontière de Poisson des PSHT.Enfin, nous nous intéressons à un autre modèle naturel de cartes aléatoires hyperboliques : les cartes causales surcritiques, qui sont construites à partir d'arbres de Galton--Watson surcritiques, en ajoutant des arêtes entre sommets de même hauteur. Nous établissons des résultats d'hyperbolicité métrique, ainsi que des propriétés de la marche aléatoire sur ces cartes, dont un résultat de vitesse positive. Certaines des propriétés obtenues sont robustes, et peuvent se généraliser à n'importe quelle carte planaire contenant un arbre de Galton--Watson surcritique
This thesis falls into the theory of random planar maps, which has been active in the last fifteen years, and more precisely into the study of hyperbolic models.We are first interested in a model of dynamical random triangulations based on edge-flips, where we prove a lower bound on the mixing time.In the rest of this thesis, the main objects that we study are the random hyperbolic triangulations called PSHT. These are hyperbolic variants of the Uniform Infinite Planar Triangulation (UIPT), and were introduced by Nicolas Curien in 2014. We first establish a near-critical scaling limit result: if we let the hyperbolicity parameter go to its critical value at the same time as the distances are renormalized, the PSHT converge to a random metric space that we call the hyperbolic Brownian plane. We also study precise metric properties of the PSHT and of the hyperbolic Brownian plane, such as the structure of their infinite geodesics. We obtain as well new properties of the Poisson boundary of the PSHT.Finally, we are interested in another natural model of hyperbolic random maps: supercritical causal maps, which are obtained from supercritical Galton--Watson trees by adding edges between vertices at the same height. We establish metric hyperbolicity results about these maps, as well as properties of the simple random walk (including a positive speed result). Some of the properties we obtain are robust, and may be generalized to any planar map containing a supercritical Galton--Watson tree

Styles APA, Harvard, Vancouver, ISO, etc.

39

Lagesse, Claire. « Lire les lignes de la ville : méthodologie de caractérisation des graphes spatiaux ». Sorbonne Paris Cité, 2015. http://www.theses.fr/2015USPCC162.

Texte intégral

Résumé :

La ville regroupe une grande diversité de composants et d'interactions. Parmi sa pluralité, nous choisissons un élément qui structure son développement et son usage : le réseau de ses rues. À partir de sa représentation sous forme de graphe, nous construisons un objet, la voie, qui se révèle être multi-échelle, rendant son analyse robuste au découpage du réseau. Nous étudions plusieurs indicateurs et nous établissons une grammaire de caractérisations non-redondantes des graphes spatiaux. La voie montre ainsi des propriétés spatiales particulières, rendant équivalentes certaines analyses globales à d'autres locales. L'application de cette méthodologie nous permet de mettre en évidence les propriétés particulières partagées par des graphes viaires de différents continents, et celles qui se retrouvent également dans d'autres réseaux spatiaux (biologiques, etc). Dans une approche diachronique, nous construisons une méthodologie de différentiation temporelle, permettant de quantifier les changements de proximité topologique entre les éléments du graphe. Cela nous permet d'avoir une première appréhension de la cinématique de croissance des réseaux étudiés. Cette recherche se termine par l'intégration de l'objet voie et de ses indicateurs dans une approche qualitative. Nous montrons ainsi comment l'analyse de villes, à travers les propriétés topologiques et topographiques de leurs réseaux viaires, permet de retrouver une partie des contextes historiques et géographiques de leur construction. La mise en perspective de ces travaux, par une synthèse des échanges pluridisciplinaires qui les ont entourés, révèle le potentiel de leurs applications et les pistes de recherches offertes
Cities arise from a large set of interactions and components. Amid this diversity, we chose an object which orchestrates the development and use of an urban area : the road network. From its representation with a graph we can build a geographical object called the way, which is multi-scale, making its analysis robust against zoning. We evaluate several indicators, and identify those that give the most relevant and non-redundant information. The way, appears to have unique spatial properties, revealing parallels between global and local analyses. With this methodology, we demonstrate how different road graphs, from various places in the world, show similar properties, and how some of those properties are also present in other networks (biological, hydrographical, etc). After considering the static properties of networks, we analyze how global characterization evolves through time. We define a model of temporal differentiation, where the change in accessibility of each object is highlighted. It is thus possible to have a first estimation of the growth kinematic of the road networks studied. This work culminates with the integration of the way and its associated indicators into a qualitative approach. We show how such analysis, based on the topological and topographical properties of their road networks, allows us to trace back some aspects of the historical and geographical contexts of city formation. Multidisciplinary discussions are synthesized to reveal research applications and future work

Styles APA, Harvard, Vancouver, ISO, etc.

40

Jacques, Isabelle. « Aspects combinatoires en modélisation 2D et 3D et application à l'énumération des cartes et des solides ». Mulhouse, 1991. http://www.theses.fr/1991MULH0185.

Texte intégral

Résumé :

Après les travaux de W. T. Tutte sur le comptage de diverses familles de cartes planaires, le point de vue adopté ici est celui de la définition de transformations topologiques sur les cartes à partir desquelles on déduit des équations sur leurs séries génératrices. Un premier résultat concerne l'énumération des cartes sur le tore en fonction du nombre d'arêtes et du degré d'une face distinguée. Une nouvelle équation sur la série génératrice est obtenue après une étude détaillée d'une transformation topologique consistant à contracter une face distinguée. Un second résultat concerne l'étude d'un problème d'évolution linéaire sur un multigraphe muni d'une valuation formelle. La résolution de ce problème conduit à une équation nouvelle attachée à tout graphe. Cette équation, appliquée dans le cas particulier de l'arbre infini naturellement associé à la famille des cartes planaires, conduit à une équation nouvelle pour la série génératrice de ces cartes planaires, exprimant celle-ci en fonction de la série génératrice des mots de Dyck. Le troisième résultat concerne une généralisation à trois dimensions au niveau des solides topologiques, des notions classiques sur les cartes. La notion de solide est introduite en termes de sommets, arêtes, faces et en y ajoutant une composante supplémentaire : celle de volume. Une propriété importante mise en évidence est celle d'effeuillabilité, celle-ci permettant de généraliser en 3D la notion d'arbre par celle de solide effeuillable. On donne alors l'énumération d'une classe particulière de tels solides effeuillables : les solides-arbres par la suite de Schröder-Etherington

Styles APA, Harvard, Vancouver, ISO, etc.

41

Samuel, Emilie. « Recherche de motifs dans des images : apport des graphes plans ». Phd thesis, Université Jean Monnet - Saint-Etienne, 2011. http://tel.archives-ouvertes.fr/tel-00719187.

Texte intégral

Résumé :

La reconnaissance de formes s'intéresse à la détection automatique de motifs dans des données d'entrée, afin de pouvoir, par exemple, les classer en catégories. La matière première de ces techniques est bien souvent l'image numérique. Cette dernière, dans sa forme la plus courante, est codée sous la forme d'une matrice de pixels. Néanmoins, la question du développement de représentations plus riches se pose. Ainsi, la structuration de l'information contenue dans l'image devrait permettre la mise en évidence des différents objets représentés, et des liens les unissant. C'est pourquoi nous proposons de modéliser les images numériques sous forme de graphes, pour leur richesse et expressivité d'une part, et pour exploiter les résultats de la théorie des graphes en reconnaissance de formes d'autre part. Nous développons pour cela une méthode d'extraction de graphes plans à partir d'images, basée sur le respect de la sémantique. Nous montrons que nous pouvons, étant donné un graphe, reconstruire avec perte limitée l'image d'origine. Par la suite, nous introduisons les graphes plans à trous, graphes dont les faces peuvent être visibles ou invisibles. Leur justification trouve sa place dans la recherche de motifs notamment, pour laquelle les éléments constituant l'arrière-plan d'une image ne doivent pas être retrouvés. En dirigeant notre attention sur la planarité de ces graphes, nous proposons des algorithmes polynomiaux d'isomorphisme de graphes plans et de motifs ; nous traitons également leur équivalence, qui se trouve être un isomorphisme aux faces invisibles près

Styles APA, Harvard, Vancouver, ISO, etc.

42

Valicov, Petru. « Problèmes de placement, de coloration et d'identiﬁcation ». Phd thesis, Université Sciences et Technologies - Bordeaux I, 2012. http://tel.archives-ouvertes.fr/tel-00801982.

Texte intégral

Résumé :

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identiﬁants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-diﬃcile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution eﬃcace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identiﬁants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enﬁn nous conﬁrmons la diﬃculté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques. La troisième partie de la thèse est consacrée aux codes identiﬁants. Nous proposons une caractérisation des graphes identiﬁables dont la cardinalité du code identiﬁant minimum est n − 1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour la cardinalité du code identiﬁant minimum dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ce paramètre dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits.

Styles APA, Harvard, Vancouver, ISO, etc.

43

Radak, Jovan. « Algorithms for Realistic Wireless Sensor Networks ». Thesis, Lille 1, 2011. http://www.theses.fr/2011LIL10079/document.

Texte intégral

Résumé :

Réseaux de capteurs sont des réseaux composés de petits objets répartis dans l'espace, appelés nœuds ou capteurs, qui travaillent en collaboration - échange de messages sans fil - sur la même application. Aujourd'hui, ces types des réseaux sont largement utilisés dans le suivi environnemental, industriel et les applications grand public et à des fins militaires. Dans ces travaux, nous nous attaquons à différents domaines de recherche dans les réseaux de capteurs: contrôle de topologie, la mobilité, la découverte de voisinage et d'expérimentation à grande échelle. Nous utilisons une réduction de graphe des plus proches voisins avec les données obtenues d'alimentation du nœud pour développer l'algorithme de contrôle de topologie. Cet algorithme conserve une connectivité du réseau dans les situations critiques où certains des capteurs épuisent de leurs batteries. Les paramètres de découverte de voisinage sont utilisés pour en déduire la mobilité relative des capteurs. Ensuite, ces paramètres sont adaptés avec la puissance d’ émission pour obtenir un algorithme efficace de découverte de voisinage. Les sites d'expérimentation à grands échelle sont un outil précieux pour développer et tester des algorithmes pour les réseaux de capteurs sans fil, mais ils ont aussi des défauts divers, le plus grand d'entre eux est le coût. Nous présentons une émulation de réseaux à grande échelle comme une solution. On utilise de petits réseaux avec un placement précis des capteurs qui permet la réplication de comportement ainsi émuler des réseaux à grande échelle. Les algorithmes sont testés et évalués sur le simulateur WSNet et pratiquement en utilisant la plate-forme SensLab et nœuds de capteurs WSN430
Wireless sensor networks can be defined as networks of small spatially distributed devices, called sensor nodes, which are working cooperatively - exchanging messages wirelessly - on the same application. Today these kinds of networks are widely used in environmental monitoring, industrial and consumer applications and for military purposes. In this thesis we are tackling different areas of research in wireless sensor networks: topology control, mobility, neighborhood discovery and large scale experimentation. We are using relative neighborhood graph reduction along with power supply data obtained from the sensor node to develop topology control algorithm. This algorithm maintains connectivity of the network in critical situations when some of the sensors drain their batteries. Neighborhood discovery parameters are used to deduce relative mobility of the sensor nodes. Then these parameters are adapted with transmission range to obtain energy efficient neighborhood discovery algorithm. Large scale experimentation sites are valuable tool for developing and testing of algorithms for wireless sensor networks but they also have various deficiencies, the biggest of them is cost. We present emulation of large scale networks as a solution. It uses small networks with the specific placement of the sensor nodes which allows replicating thus emulating behavior of the large scale networks. Algorithms are tested and evaluated on the WSNet simulator and practically using the SensLab platform and WSN430 sensor nodes

Styles APA, Harvard, Vancouver, ISO, etc.

44

Xu, Renyu. « Quelques problèmes de coloration du graphe ». Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLS104/document.

Texte intégral

Résumé :

Un k-coloriage total d'un graphe G est un coloriage de V(G)cup E(G) utilisant (1,2,…,k) couleurs tel qu'aucune paire d'éléments adjacents ou incidents ne reçoivent la même couleur. Le nombre chromatique total chi''(G) est le plus petit entier k tel que G admette un k-coloriage total. Dans le chapitre 2, nous étudions la coloration totale de graphe planaires et obtenons 3 résultats : (1) Soit G un graphe planaire avec pour degré maximum Deltageq8. Si toutes les paires de 6-cycles cordaux ne sont pas adjacentes dans G, alors chi''(G)=Delta+1. (2) Soit G un graphe planaire avec pour degré maximum Deltageq8. Si tout 7-cycle de G contient au plus deux cordes, alors chi''(G)=Delta+1. (3) Soit G un graphe planaire sans 5-cycles cordaux qui s'intersectent, c'est à dire tel que tout sommet ne soit incident qu'à au plus un seul 5-cycle cordal. Si Deltageq7, alors chi''(G)=Delta+1.Une relation L est appelé assignation pour un graphe G s'il met en relation chaque x à une liste de couleur. S'il est possible de colorier G tel que la couleur de chaque x soit présente dans la liste qu'il lui a été assignée, et qu'aucune paire de sommets adjacents n'aient la même couleur, alors on dit que G est L-coloriable. Un graphe G est k-selectionable si G est L-coloriable pour toute assignation L de G qui satisfait |L(v)geq k| pour tout x. Nous démontrons que si chaque 5-cycle de G n'est pas simultanément adjacent à des 3-cycles et des 4-cycles, alors G est 4-sélectionable. Dans le chapitre 3, nous prouvons que si aucun des 5-cycles de G n'est adjacent à un 4-cycles, alors chi'_l(G)=Delta et chi''_l(G)=Delta+1 si Delta(G)geq8, et chi'_l(G)leqDelta+1 et chi''_l(G)leqDelta+2 si Delta(G)geq6.Dans le chapitre 4, nous allons fournir une définition du coloriage total somme-des-voisins-distinguant, et passer en revue les progrgrave{e}s et conjecture concernant ce type de coloriage. Soit f(v) la somme des couleurs d'un sommet v et des toutes les arrêtes incidentes à v. Un k-coloriage total somme-des-voisins-distinguant de G est un k coloriage total de G tel que pour chaque arrête uvin E(G), f(u)eq f(v). Le plus petit k tel qu'on ai un tel coloriage sur G est appelé le nombre chromatique total somme-des-voisins-distinguant, noté chi''_{sum} (G). Nous avons démontré que si un graphe G avec degré maximum Delta(G) peut être embedded dans une surface Sigma de caractéristique eulérienne chi(Sigma)geq0, alors chi_{sum}^{''}(G)leq max{Delta(G)+2, 16}.Une forêt linéaire est un graphe pour lequel chaque composante connexe est une chemin. L'arboricité linéaire la(G) d'un graphe G tel que définie est le nombre minimum de forêts linéaires dans G, dont l'union est égale à V(G). Dans le chapitre 5, nous prouvons que si G est une graphe planaire tel que tout 7-cycle de G contienne au plus deux cordes, alors G est linéairementleft lceil frac{Delta+1}{2}ightceil-sélectionable si Delta(G)geq6, et G est linéairement left lceil frac{Delta}{2}ightceil-sélectionable si Delta(G)geq 11
A k-total-coloring of a graph G is a coloring of V(G)cup E(G) using (1,2,…,k) colors such that no two adjacent or incident elements receive the same color．The total chromatic number chi''(G) is the smallest integer k such that G has a k-total-coloring. In chapter 2, we study total coloring of planar graphs and obtain three results: (1) Let G be a planar graph with maximum degree Deltageq8. If every two chordal 6-cycles are not adjacent in G, then chi''(G)=Delta+1. (2) Let G be a planar graph G with maximum degree Deltageq8. If any 7-cycle of G contains at most two chords, then chi''(G)=Delta+1. (3) Let G be a planar graph without intersecting chordal 5-cycles, that is, every vertex is incident with at most one chordal 5-cycle. If Deltageq7, then chi''(G)=Delta+1.A mapping L is said to be an assignment for a graph G if it assigns a list L(x) of colors to each xin V(G)cup E(G). If it is possible to color G so that every vertex gets a color from its list and no two adjacent vertices receive the same color, then we say that G is L-colorable. A graph G is k-choosable if G is an L-colorable for any assignment L for G satisfying |L(x)|geq k for every vertex xin V(G)cup E(G). We prove that if every 5-cycle of G is not simultaneously adjacent to 3-cycles and 4-cycles, then G is 4-choosable. In chapter 3, if every 5-cycles of G is not adjacent to 4-cycles, we prove that chi'_l(G)=Delta, chi''_l(G)=Delta+1 if Delta(G)geq8, and chi'_l(G)leqDelta+1, chi''_l(G)leqDelta+2 if Delta(G)geq6.In chapter 4, we will give the definition of neighbor sum distinguishing total coloring. Let f(v) denote the sum of the colors of a vertex v and the colors of all incident edges of v. A total k-neighbor sum distinguishing-coloring of G is a total k-coloring of G such that for each edge uvin E(G), f(u)eq f(v). The smallestnumber k is called the neighbor sum distinguishing total chromatic number, denoted by chi''_{sum} (G). Pilsniak and Wozniak conjectured that for any graph G with maximum degree Delta(G) holds that chi''_{sum} (G)leqDelta(G)+3. We prove for a graph G with maximum degree Delta(G) which can be embedded in a surface Sigma of Euler characteristic chi(Sigma)geq0, then chi_{sum}^{''}(G)leq max{Delta(G)+2, 16}.Lastly, we study the linear L-choosable arboricity of graph. A linear forest is a graph in which each component is a path. The linear arboricity la(G) of a graph G is the minimum number of linear forests in G, whose union is the set of all edges of G. A list assignment L to the edges of G is the assignment of a set L(e)subseteq N of colors to every edge e of G, where N is the set of positive integers. If G has a coloring varphi (e) such that varphi (e)in L(e) for every edge e and (V(G),varphi^{-1}(i)) is a linear forest for any iin C_{varphi}, where C_{varphi }=left { varphi (e)|ein E(G)ight }, then we say that G is linear L-colorable and varphi is a linear L-coloring of G. We say that G is linear k-choosable if it is linear L-colorable for every list assignment L satisfying |L(e)| geq k for all edges e. The list linear arboricity la_{list}(G) of a graph G is the minimum number k for which G is linear k-list colorable. It is obvious that la(G)leq la_{list}(G). In chapter 5, we prove that if G is a planar graph such that every 7-cycle of G contains at most two chords, then G is linear left lceil frac{Delta+1}{2}ightceil-choosable if Delta(G)geq6, and G is linear left lceil frac{Delta}{2}ightceil-choosable if Delta(G)geq 11

Styles APA, Harvard, Vancouver, ISO, etc.

45

Pakovitch, Fedor. « Combinatoire des arbres planaires et arithmétiques des courbes hyperelliptiques ». Université Joseph Fourier (Grenoble ; 1971-2015), 1997. http://www.theses.fr/1997GRE10073.

Texte intégral

Résumé :

Le but principal de cette these est de proposer une nouvelle methode pour des etudes dans le cadre de la theorie des dessins d'enfants de a. Grotendieck de certaines questions concernant l'action du groupe de galois absolu sur l'ensemble des arbres planaires. On definit l'application qui associe a chaque arbre planaire a n aretes, une courbe hyperelliptique avec un point de n-division. Cette construction permet d'etablir un lien entre la theorie de la torsion des courbes hyperelliptiques et celle des dessins d'enfants. En particulier, en utilisant les resultats correspondants sur la torsion des courbes elliptiques, on obtient des estimations inferieures sur les degres des corps des modules des arbres de certaines classes. D'autre part, la construction ci-dessus donne une suite interessante d'exemples de diviseurs rationnels de torsion sur des courbes hyperelliptiques definies sur des corps de nombres. Les trois premiers chapitres de cette these sont consacres a la presentation de ces questions. Le quatrieme chapitre porte sur la theorie geometrique des fonctions et est motive par un probleme d'unicite pose en 1976 par c. C. Yang : est-il vrai que le polynome complexe de degre n est defini a symetrie pres par l'image reciproque de deux points. On prouve que la reponse a cette question est affirmative et on donne quelques generalisations.

Styles APA, Harvard, Vancouver, ISO, etc.

46

Curien, Nicolas. « Etude asymptotique de grands objets combinatoires aléatoires ». Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00607721.

Texte intégral

Résumé :

Dans ce travail, nous nous sommes intéressés à l'étude asymptotique d'objets combinatoires aléatoires. Deux thèmes ont particulièrement retenu notre attention : les cartes planaires aléatoires et les modèles combinatoires liés à la théorie des fragmentations. La théorie mathématique des cartes planaires aléatoires est née à l'aube de notre millénaire avec les travaux pionniers de Benjamini & Schramm, Angel & Schramm et Chassaing & Schaeffer. Elle a ensuite beaucoup progressé, mais à l'heure où ces lignes sont écrites, de nombreux problèmes fondamentaux restent ouverts. Résumons en quelques mots clés nos principales contributions dans le domaine : l'introduction et l'étude du cactus brownien (avec J.F. Le Gall et G. Miermont), l'étude de la quadrangulation infinie uniforme vue de l'infini (avec L. Ménard et G. Miermont), ainsi que des travaux plus théoriques sur les graphes aléatoires stationnaires d'une part et les graphes empilables dans $\R^d$ d'autre part (avec I. Benjamini). La théorie des fragmentations est beaucoup plus ancienne et remonte à des travaux de Kolmogorov (1941) et de Filippov (1961). Elle est maintenant bien développée (voir par exemple l'excellent livre de J. Bertoin), et nous ne nous sommes pas focalisés sur cette théorie mais plutôt sur ses applications à des modèles combinatoires. Elle s'avère en effet très utile pour étudier différents modèles de triangulations récursives du disque (travail effectué avec J.F. Le Gall) et les recherches partielles dans les quadtrees (travail effectué avec A. Joseph).

Styles APA, Harvard, Vancouver, ISO, etc.

47

Zhou, Hang. « Graph algorithms : network inference and planar graph optimization ». Thesis, Paris, Ecole normale supérieure, 2015. http://www.theses.fr/2015ENSU0016/document.

Texte intégral

Résumé :

Cette thèse porte sur deux sujets d’algorithmique des graphes. Le premier sujet est l’inférence de réseaux. Quelle est la complexité pour déterminer un graphe inconnu à partir de requêtes de plus court chemin entre ses sommets ? Nous supposons que le graphe est de degré borné. Dans le problème de reconstruction, le but est de reconstruire le graphe ; tandis que dans le problème de vérification, le but est de vérifier qu’un graphe donné est correct. Nous développons des algorithmes probabilistes utilisant une décomposition en cellules de Voronoi. Ensuite, nous analysons des algorithmes de type glouton, et montrons qu’ils sont quasi-optimaux. Nous étudions aussi ces problèmes sur des familles particulières de graphes, démontrons des bornes inférieures, et étudions la reconstruction approximative. Le deuxième sujet est l’étude de deux problèmes d’optimisation sur les graphes planaires. Dans le problème de classification par corrélations, l’entrée est un graphe pondéré, où chaque arête a une étiquette h+i ou h-i, indiquant si ses extrémités sont ou non dans la même catégorie. Le but est de trouver une partition des sommets en catégories qui respecte au mieux les étiquettes. Dans le problème d’augmentation 2-arête-connexe, l’entrée est un graphe pondéré et un sous-ensemble R des arêtes. Le but est de trouver un sous-ensemble S des arêtes de poids minimum, tel que pour chaque arête de R, ses extrémités sont dans une composante 2-arête-connexe de l’union de R et S. Pour les graphes planaires, nous réduisons le premier problème au deuxième et montrons que les deux problèmes, bien que NP-durs, ont un schéma d’approximation en temps polynomial. Nous utilisons la technique récente de décomposition en briques
This thesis focuses on two topics of graph algorithms. The first topic is network inference. How efficiently can we find an unknown graph using shortest path queries between its vertices? We assume that the graph has bounded degree. In the reconstruction problem, the goal is to find the graph; and in the verification problem, the goal is to check whether a given graph is correct. We provide randomized algorithms based on a Voronoi cell decomposition. Next, we analyze greedy algorithms, and show that they are near-optimal. We also study the problems on special graph classes, prove lower bounds, and study the approximate reconstruction. The second topic is optimization in planar graphs. We study two problems. In the correlation clustering problem, the input is a weighted graph, where every edge has a label of h+i or h−i, indicating whether its endpoints are in the same category or in different categories. The goal is to find a partition of the vertices into categories that tries to respect the labels. In the two-edge-connected augmentation problem, the input is a weighted graph and a subset R of edges. The goal is to produce a minimum-weight subset S of edges, such that for every edge in R, its endpoints are two-edge-connected in the union of R and S. For planar graphs, we reduce correlation clustering to two-edge-connected augmentation, and show that both problems, although they are NP-hard, have a polynomial-time approximation scheme. We build on the brick decomposition technique developed recently

Styles APA, Harvard, Vancouver, ISO, etc.

48

Linhares, Sales Cláudia. « Graphes parfais et paires d'amis ». Université Joseph Fourier (Grenoble), 1996. http://tel.archives-ouvertes.fr/tel-00345386.

Texte intégral

Résumé :

A partir du concept de paire d'amis dans un graphe (paire de sommets telle que toutes les chaînes sans cordes qui les relient sont de longueur paire) deux classes de graphes parfaits ont été déjà définies. La première notée QPS (graphes de quasi-parité stricte) est définie par l'existence de paires d'amis pour tout sous-graphe induit incomplet. La deuxième notée PC (graphes parfaitement contractibles) est définie à partir de l'idée algorithmique de coloration du graphe ou de ses sous-graphes induits par enchaînement de contractions successives des sommets d'une paire d'amis jusqu'à obtenir une clique, auquel cas la coloration est optimale. Dans cette thèse nous avons abordé deux conjectures: la première (relative à la classe QPS) énoncée par S. Hougardy est proche de la conjecture forte de graphes parfaits et la deuxième énoncée par H. Everett et B. Reed consite à caractériser les graphes PC par sous-graphes exclus. Nous avons pu valider ces deux conjectures dans deux cas: le cas des graphes planaires et le cas des graphes sans griffe. Ces quatre résultats sont assortis d'algorithmes polynomiaux de reconnaissance (ainsi que de coloration pour la classe PC)

Styles APA, Harvard, Vancouver, ISO, etc.

49

Moreau, Jean Michel. « Hiérarchisation et facettisation de la représentation par segments d'un graphe planaire ». Phd thesis, Ecole Nationale Supérieure des Mines de Saint-Etienne, 1990. http://tel.archives-ouvertes.fr/tel-00831581.

Texte intégral

Résumé :

L'organisation structurée (graphe avec hiérarchies et propriétés sémantiques) d'objets du plan implique plusieurs opérations complexes qui doivent être effectuées en toute sécurité de cohérence topologique. La précision inhérente d'une machine étant nécessairement limitée, il faut souvent recourir à une arithmétique exacte couteuse. Cette thèse présente, à partir de travaux liés à la réalisation du module de facettisation d'un simulateur de vol industriel, une solution permettant l'utilisation d'une arithmétique mixte, de précision arbitraire et de coût très inférieur statistiquement a la solution exacte. On y trouve aussi l'unification des méthodes de construction d'un diagramme de Voronoi, d'une triangulation de Delaunay pour un nuage de points dans le plan et de la triangulation contrainte de Delaunay de la représentation par segments d'un graphe planaire, autour d'une technique incrémentale optimale, fondamentalement plus simple que la méthode diviser-pour-résoudre classique. La technique incrémentale permet, par ailleurs, de donner un algorithme linéaire et très simple de construction du diagramme de Voronoi et de la triangulation de Delaunay d'un nuage de points situes sur la frontière d'un polygone monotone ou convexe.

Styles APA, Harvard, Vancouver, ISO, etc.

50

Fredes, Carrasco Luis. « Some models on the interface of probability and combinatorics : particle systems and maps ». Thesis, Bordeaux, 2019. http://www.theses.fr/2019BORD0142/document.

Texte intégral

Résumé :

Cette thèse se compose de plusieurs travaux portant sur deux branches de la théorie des probabilités: processus de particules et cartes planaires aléatoires. Un premier travail concerne les aspects algébriques des mesures invariantes des processus de particules. Nous obtenons des conditions nécessaires et suffisantes sous lesquelles un processus de particules en temps continu avec espace d’états local discret possède une mesure invariante simple. Dans un deuxième travail nous étudions un modèle "biologique" de coexistence de 2 espèces en compétition sur un espace partagé, et soumis à des épidémies modélisées par un modèle probabiliste appelé "feux de forêts". Notre résultat principal montre que pour deux espèces, il existe des régions explicites de paramètres pour lesquelles une espèce domine ou les deux espèces coexistent. Il s’agit d’un des premiers modèles pour lesquels la coexistence d’espèces sur le long terme est prouvée. Les troisièmes et quatrièmes travaux. portent sur les cartes planaires décorées par des arbres. Dans le troisième nous présentons une bijection entre l’ensemble des cartes décorées par des arbres et le produit Cartésien entre l’ensemble des arbres planaires et l’ensemble de cartes à bord simple. Nous obtenons quelques formules de comptage et quelques outils pour l’étude de cartes aléatoires décorées par un arbre. Le quatrième travail montre que les triangulations et quadrangulations aléatoires uniformes avec f faces, bord simple de taille p et décorées par un arbre avec a arêtes, convergent en loi pour la topologie locale vers différentes limites, dépendant du comportement fini ou infini de la limite de f, p et a
This thesis consists in several works exploring some models belonging to two branches of probability theory: interacting particle systems and random planar maps. A first work concerns algebraic aspects of interacting particle systems invariant measures. We obtain some necessary and sufficient conditions for some continuous time particle systems with discrete local state space, to have a simple invariant measure. In a second work we investigate the effect on survival and coexistence of introducing forest fire epidemics to a certain two-species spatial competition model. Our main results show that, for the two-type model, there are explicit parameter regions where either one species dominates or there is coexistence; contrary to the same model without forest fires, for which the fittest species alwaysdominates. The third and fourth works are related to tree-decorated planar maps. In the third work we present a bijection between the set of tree-decorated maps and the Cartesian product between the set of trees and the set of maps with a simple boundary. We obtain some counting results and some tools to study random decorated map models. In the fourth work we prove that uniform tree-decorated triangulations and quadrangulations with f faces, boundary of length p and decorated by a tree of size a converge weakly for the local topology to different limits, depending on the finite or infinite behavior of f, p and a

Styles APA, Harvard, Vancouver, ISO, etc.

Thèses sur le sujet « Graphes planaires »

Créez une référence correcte selon les styles APA, MLA, Chicago, Harvard et plusieurs autres