• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 309
  • 139
  • 27
  • 1
  • Tagged with
  • 468
  • 214
  • 134
  • 133
  • 60
  • 51
  • 48
  • 46
  • 44
  • 43
  • 42
  • 42
  • 41
  • 40
  • 39
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
41

Complétions d'intervalles minimales

Suchan, Karol 12 December 2006 (has links) (PDF)
La largeur linéaire et la largeur arborescente ont été introduites par Robertson et Seymour dans leurs travaux sur les mineurs de graphes. De manière informelle, la largeur linéaire (resp. la largeur arborescente) d'un graphe mesure l'écart entre ce graphe et la classe des chaînes (des arbres). Les deux paramètres se sont révélés très puissants de point de vue algorithmique, car de nombreux problèmes NP-difficiles deviennent polynomiaux lorsque l'on se restreint à des classes de graphes de largeur linéaire ou de largeur arborescente bornée. Etant donné un graphe G=(V,E) quelconque, un graphe d'intervalles H=(V,F) contenant G est appelé complétion d'intervalles de G. Calculer la largeur linéaire de G revient à trouver une complétion d'intervalles H, tout en minimisant la clique maximum de H. Le problème étant NP-difficile, nous calculerons des complétions d'intervalles minimales, où l'on demande seulement que l'ensemble d'arêtes rajoutées F\E soit minimal par inclusion parmi toutes les complétions possibles. Une approche similaire, à travers les triangulations minimales, est fortement utilisée pour comprendre et calculer la largeur arborescente. Ce mémoire présente nos résultats sur les complétions d'intervalles minimales. Nous donnons trois algorithmes calculant une complétion d'intervalles minimale, basés sur des approches différentes. Nous présentons également un algorithme calculant une complétion d'intervalles propres minimale. Enfin, nous montrons que la largeur linéaire des graphes d'intervalles circulaires peut être calculée en temps polynomial.
42

Transformation de Legendre en théorie des espèces

Mathlouthi, Walid January 2007 (has links) (PDF)
La transformation de Legendre envoie des fonctions convexes définies sur un espace vectoriel à des fonctions convexes définies sur l'espace vectoriel dual. Elle est reliée à la dualité projective, aux coordonnées tangentielles en géometrie algébrique et à la construction des espaces de Banach duaux en analyse. On l'utilise aussi en mécanique statistique pour définir des potentiels thermodynamiques à partir des fonctions de variables d'état. Plus précisément, la transformation de Legendre permet de transformer une fonction d'état d'un système en une autre fonction d'état mieux adaptée à un problème particulier. Le chapitre un se veut un résumé des résultats connus à propos de la transformation de Legendre en analyse. Nous donnons plusieurs exemples afin d'illustrer les propriétés essentielles de cette transformation. Dans le chapitre deux, nous rappelons quelques notions en thermodynamique statistique: Les variables intensives, les variables extensives, l'énergie interne, l'entropie. Ensuite nous définissons les potentiels thermodynamiques qui sont des transformées de Legendre de l'énergie interne. Dans le chapitre trois, nous rappelons des résultats fondamentaux de la théorie des espèces de structures. Mentionnons en particulier le théorème de dissymétrie pour les arbres et pour les graphes, ainsi que les équations fonctionnelles fondamentales pour les CB-graphes, i.e les graphes connexes dont tous les blocs sont dans une classe des graphes inséparables B, ainsi que pour les CM-graphes, i.e les graphes connexes dont toutes les mottes sont dans une classe de graphes irréductibles (2-arêtes-connexes). Dans le chapitre quatre, nous donnons la définition de la transformation de Legendre pour les espèces de structures à une sorte ou à deux sortes par rapport à une sorte. En effet, Pierre Leroux a été le premier à relier ces deux notions (Transformation de Legendre et espèces de structures). Il a démontré (Leroux, 2003) que les CM-graphes sont liées au M-graphes par transformation de Legendre. Dans ce mémoire on montre par une construction originale que l'espèce M des graphes irréductibles peut être remplacée par une espèce N quelconque, avec N[0] =0. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Fonctions convexes, Ensembles convexes, Transformation de Legendre, Potentiels thermodynamiques, Énergie interne, Fonction de partition, Graphes, Isthme, Bloc, Motte, Graphes inséparables, Graphes irréductibles, Espèce de structures, Note.
43

Etude d'une nouvelle classe de graphes : les graphes hypotriangulés

Topart, Hélène 26 May 2011 (has links) (PDF)
Dans cette thèse, nous définissons une nouvelle classe de graphes : les graphes hypotriangulés. Les graphes hypotriangulés vérifient que pour tout chemin de longueur deux, il existe une arête ou un autre chemin de longueur deux entre ses extrémités. Cette classe permet par exemple de modéliser des réseaux robustes. En effet, nous montrons que dans de tels graphes, la suppression d'une arête ou d'un sommet ne modifie pas la distance initiale entre toutes paires de sommets non adjacents. Ensuite, nous étudions et démontrons plusieurs propriétés pour cette classe de graphes. En particulier, après avoir introduit une famille de partitions spécifiques, nous montrons les relations entre certains éléments de cette famille et leur caractère hypotriangulé. De plus, grâce à ces partitions, nous caractérisons les graphes hypotriangulés minimum, qui, parmi les graphes hypotriangulés connexes, minimisent le nombre d'arêtes pour un nombre de sommets fixés.Dans une deuxième partie, nous étudions la complexité, pour la classe des graphes hypotriangulés, de problèmes difficiles dans le cas général. Nous montrons d'abord que les problèmes classiques de cycle hamiltonien, coloration, clique maximum et stable maximum restent NP-difficiles pour cette classe de graphes. Ensuite, nous nous intéressons à des problèmes de modification de graphes, pour lesquels il s'agit de déterminer le nombre minimal d'arêtes à ajouter ou supprimer à un graphe pour obtenir un graphe hypotriangulé : nous montrons la complexité de ces problèmes pour plusieurs classes de graphes.
44

Verification formelle et optimisation de l'allocation de registres

Robillard, Benoit, Bruno 30 November 2010 (has links) (PDF)
La prise de conscience générale de l'importance de vérifier plus scrupuleusement les programmes a engendré une croissance considérable des efforts de vérification formelle de programme durant cette dernière décennie. Néanmoins, le code qu'exécute l'ordinateur, ou code exécutable, n'est pas le code écrit par le développeur, ou code source. La vérification formelle de compilateurs est donc un complément indispensable à la vérification de code source.L'une des tâches les plus complexes de compilation est l'allocation de registres. C'est lors de celle-ci que le compilateur décide de la façon dont les variables du programme sont stockées en mémoire durant son exécution. La mémoire comporte deux types de conteneurs : les registres, zones d'accès rapide, présents en nombre limité, et la pile, de capacité supposée suffisamment importante pour héberger toutes les variables d'un programme, mais à laquelle l'accès est bien plus lent. Le but de l'allocation de registres est de tirer au mieux parti de la rapidité des registres, car une allocation de registres de bonne qualité peut conduire à une amélioration significative du temps d'exécution du programme.Le modèle le plus connu de l'allocation de registres repose sur la coloration de graphe d'interférence-affinité. Dans cette thèse, l'objectif est double : d'une part vérifier formellement des algorithmes connus d'allocation de registres par coloration de graphe, et d'autre part définir de nouveaux algorithmes optimisants pour cette étape de compilation. Nous montrons tout d'abord que l'assistant à la preuve Coq est adéquat à la formalisation d'algorithmes d'allocation de registres par coloration de graphes. Nous procédons ainsi à la vérification formelle en Coq d'un des algorithmes les plus classiques d'allocation de registres par coloration de graphes, l'Iterated Register Coalescing (IRC), et d'une généralisation de celui-ci permettant à un utilisateur peu familier du système Coq d'implanter facilement sa propre variante de cet algorithme au seul prix d'une éventuelle perte d'efficacité algorithmique. Ces formalisations nécessitent des réflexions autour de la formalisation des graphes d'interférence-affinité, de la traduction sous forme purement fonctionnelle d'algorithmes impératifs et de l'efficacité algorithmique, la terminaison et la correction de cette version fonctionnelle. Notre implantation formellement vérifiée de l'IRC a été intégrée à un prototype du compilateur CompCert.Nous avons ensuite étudié deux représentations intermédiaires de programmes, dont la forme SSA, et exploité leurs propriétés pour proposer de nouvelles approches de résolution optimale de la fusion, l'une des optimisations opéréeslors de l'allocation de registres dont l'impact est le plus fort sur la qualité du code compilé. Ces approches montrent que des critères de fusion tenant compte de paramètres globaux du graphe d'interférence-affinité, tels que sa largeur d'arbre, ouvrent la voie vers de nouvelles méthodes de résolution potentiellement plus performantes.
45

Topologie et algorithmes sur les cartes combinatoires / A structural and algorithmic study of combinatorial maps and their curves.

Despré, Vincent 18 October 2016 (has links)
Dans cette thèse, nous nous intéressons aux propriétés topologiques des surfaces, i.e. celles qui sont préservées par des déformations continues. Intuitivement, ces propriétés peuvent être imaginées comme étant celles qui décrivent le forme générale des surfaces. Nous utilisons des cartes combinatoires pour décrire les surfaces. Elles ont le double avantage d'être de naturels objets mathématiques et de pouvoir être transformées naturellement en structure de données.Nous étudions trois problèmes différents. Premièrement, nous donnons des algorithmes pour calculer le nombre géométrique d'intersection de courbes dessinées sur des surfaces. Nous avons obtenu un algorithm quadratique pour calculer le nombre minimal d'auto-intersections dans une classe d'homotopie, un algorithme quartique pour construire un représentant minimal et un algorithme quasi-linéaire pour décider si une classe d'homotopie contient une courbe simple. Ensuite, nous donnons des contre-exemples à une conjecture de Mohar et Thomassen au sujet de l'existence de cycles de partage dans les triangulations. Finalement, nous utilisons les travaux récents de Lévèque et Gonçalves à propos des bois de Schnyder toriques pour construire une bijection entre les triangulations du tore et certaines cartes unicellulaires analogue à le célèbre bijection de Poulalhon et Schaeffer pour les triangulations planaires.Plusieurs points de vue sont utilisés au cours de cette thèse. Nous proposons donc un important chapitre préliminaire où nous insistons sur les connections entre ces différents points de vue. / In this thesis, we focus on the topological properties of surfaces, i.e. those that are preserved by continuous deformations. Intuitively, it can be understood as the properties that describe the general shape of surfaces. We describe surfaces as combinatorial maps. They have the double advantage of being well defined mathematical objects and of being straightforwardly transformed into data-structures.We study three distinct problems. Firstly, we give algorihtms to compute geometric intersection numbers of curves on surfaces. We obtain a quadratic algorithm to compute the minimal number of self-intersections in a homotopy class, a quartic one to construct a minimal representative and a quasi-linear one to decide if a homotopy class contains a simple curve. Secondly, we give counter-examples to a conjecture of Mohar and Thomassen about the existence of splitting cycles in triangulations. Finally, we use the recent work of Gonçalves and Lévèque about toiroidal Schnyder woods to describe a bijection between toroidal triangulations and toroidal unicellular maps analogous to the well known bijection of Poulalhon and Schaeffer for planar triangulations.Many different points of view are involved in this thesis. We thus propose a large preliminary chapter where we provide connections between the different viewpoints.
46

Le raisonnement analogique en lexicographie, son informatisation et son application au Réseau Lexical du Français / The analogical reasoning in lexicography and its computerisation : application to the French Lecial Network

Ollinger, Sandrine 15 December 2014 (has links)
La lexicographie contemporaine met à disposition des ressources offrant de multiples possibilités d’exploitation automatique. Ainsi, le Réseau Lexical du Français, en cours d’élaboration, est un graphe monolingue, constitué de sommets, entre lesquels sont encodées des relations syntaxico-sémantiques. Cette thèse s’intéresse à son exploration par raisonnement analogique. Elle débute par une revue de la formalisation et de l’informatisation de l’analogie pour l’étude du lexique, qui définit les principes de l’exploration  : les sommets sont des objets disposant d’Attributs, les arcs représentent des Relations. Une réflexion est menée sur la nature de ces éléments et les rapports qu’ils entretiennent, réalisée en tenant compte leur évolution dans le temps et de la topologie du graphe. Deux séries d’expériences viennent ensuite. La première montre que la formalisation de la ressource permet de détecter des analogies conformes à l’intuition, que différents types d’exploration sont possibles et que l’approche permet de vérifier la cohérence du réseau et de faire émerger des règles lexicales. La seconde série porte sur la notion de configurations de dérivations lexicales. Elle montre que le regroupement de sous-graphes analogues fait émerger des connexions récurrentes. L’état d’avancement du réseau ne permet pas d’obtenir des règles et des modèles aboutis, mais les résultats sont encourageants. L’analogie est alors considérée comme un guide pour s’assurer de la qualité de la représentation du lexique proposée et acquérir des connaissances sur son organisation. Elle permet d’identifier des phénomènes linguistiques et d’instrumenter l’activité lexicologique. / Contemporary lexicography provide ressources offering many opportunities for natural language processing tasks. Thus, the French Lexical Network, presently under development, is a graph of lexical units connected by a rich set of lexical relations. This PhD thesis lays the groundwork for an exploration of this ressource by analogical reasonning. It begins with a selective overview of formalisation and computerisation for study of lexicon, wich defines the principle of exploration : the nodes are similar to objects, which have some attributes and edges represent relations. A reflection is conducted on the nature of this constituents and the relations between them. It takes into account the time axis and the topology of the network. Then two sets of exploratory experiments are conducted. The first one shows that the resource formalisation makes it possible to detect automatically analogies consistent with intuition, that several kind of analogical explorations are possible and that the approach allows to check the consistency of the resource and to bring out lexical rules. The second one is focused around the concept of lexical derivation configurations. It shows how grouping of analogous subgraphs reveals recurrent connections. The progress status of the resource doesn't enable us to obtain successfully completed rules and models, but results are nontheless encouraging. Analogy can already be considered as a guide to ensure the quality of lexical resources. It also allows for the acquisition of knowledge about its organisation. Such knowledge can be used to identify linguitic phenomena and to design instruments to support lexicographic activity.
47

Figures du « réseautage en ligne » sur les réseaux socionumériques professionnels : le cas d’un groupe d’anciens sur LinkedIn / Types of online networking on professional social network sites : case study of an alumni group hosted on LinkedIn

Mesangeau, Julien 11 December 2012 (has links)
Notre enquête a été conduite auprès de membres d’un groupe d’anciens élèves hébergé sur le site de réseau social professionnel LinkedIn. Elle a permis de produire deux résultats. Le premier résultat est une typologie des figures du réseautage en ligne. Nous proposons trois figures. Le NetMining, qui relève d’un usage exploratoire du site et oùl’utilisateur cumule de nombreux contacts. Le NetWorking où l’utilisateur sélectionne des relations sur la base de critères précis. Le NetSticking où l’utilisateur reproduit en ligne un réseau personnel basé sur la confiance. Ces trois tendances permettent de souligner deux caractéristiques propres aux pratiques de réseautage en ligne. D’une part, elles reposent surune pluralité de dispositifs de communication où LinkedIn occupe une place tantôt centrale, tantôt marginale. D’autre part, ces pratiques ne reposent pas nécessairement sur la poursuite d’une action planifiée. Le second résultat produit par notre enquête est un dispositif d’étude des pratiques de réseautage. Il associe des techniques de visualisation de graphes et analyses d’entretiens semi-directifs / Our study had been carried on members of a social network hosted on the professional social network site, LinkedIn. It produced two main outcomes. The first is a typology of online Networking on three different classes. The first is the NetMining, which is a exploratory use of the website, where the user accumulated contacts. The second category is the NetWorking, where the users select contacts based on defined characteristics. The NetSticking is the third category, in which the user reproduced online a personal network based on trust. Those three categories highlight two main characteristics, specific to online networking. First, networking uses different means of communication, in whichLinkedIn is sometimes central, but sometimes marginal. Those practices are besides not necessarily based on planed actions. The Second result of our enquiry is a study device of the networking practices which associated graphs visualization technics and semi-directed interviews analyses
48

Prise en compte d'une échelle mésoscopique dans l'étude du comportement des milieux granulaires

Nguyen, Ngoc Son 11 December 2009 (has links)
La technique de changement d’échelles a été largement développée dans la littérature pour décrire le comportement global des milieux granulaires en prenant en compte leurs propriétés locales. Cette technique considère classiquement deux échelles : l’échelle macroscopique du volume élémentaire représentatif et l’échelle microscopique du contact entre particules. Le défi majeur de ce changement d’échelles "micro-macro" réside dans la définition de la déformation macroscopique : en effet, si la contrainte macroscopique peut être clairement définie à partir des forces de contact, il a été montré qu’il n’était pas approprié de déduire la déformation macroscopique à partir de la cinématique aux contacts. Dans ce cadre, ce travail propose d’introduire une troisième échelle dite mésoscopique. Cette échelle, à laquelle peuvent être définies à la fois contrainte et déformation, est intermédiaire entre les échelles microscopique et macroscopique et permet de palier au défi majeur mentionné ci-dessus. Elle est définie au niveau d’arrangements locaux de particules, appelés sous-domaines, et sa pertinence est étudiée sur la base d’échantillons numériques composés de particules circulaires puis sphériques, simulés par la méthode des éléments discrets. Les milieux bidimensionnels sont géométriquement représentés par un graphe de particules composé de sous-domaines fermés, encore appelés cellules de vide, dont la frontière est constituée de branches connectant les centres de particules en contact : l’échelle mésoscopique est donc définie au niveau de ces cellules de vide fermées. A cette échelle locale, on décrit tout d’abord la structure du milieu en termes de densité et de texture puis l’on définit les variables statique et cinématique locales du milieu en termes de contrainte et déformation. De fortes hétérogénéités des milieux granulaires en termes de structure, déformation et contrainte sont mises en évidence à l’échelle mésoscopique, avec de plus une structuration des hétérogénéités de contraintes et de déformations et une forte corrélation entre ces deux quantités. Concernant les milieux tridimensionnels, une partition en cellules de vide fermées est impossible du fait de la complexité de la structure 3D de ces milieux. On propose donc une méthode de partition du milieu basée sur la distribution des vides en son sein. La méthode consiste en premier lieu en une subdivision du milieu en tétraèdres, par une partition de Delaunay, puis en une association de tétraèdres voisins selon un critère prédéfini en vue de la création de sous-domaines, non fermés, mais au rôle analogue aux sous-domaines fermés de l’étude 2D. Le critère d’association proposé est basé sur le rapport entre la taille des constrictions (vide sur chaque face des tétraèdres) et la taille des pores au voisinage de chaque constriction. Cette méthode d’association constitue donc l’étape préliminaire à l’extension au cas tridimensionnel des résultats obtenus dans le cas bidimensionnel. / The technique of change of scales has been extensively developed in the literature to describe the global behaviour of granular materials taking into account their local properties. This method usually considers two scales : the macroscopic scale at the level of representative elementary volume and the microscopic scale at the level of contact between particles. The major difficulty of this "micro-macro" change of scales lies in the definition of the macroscopic strain : indeed, the macroscopic stress is clearly defined from contact forces while it is not appropriate to derive the macroscopic strain from the kinematics at contacts. In this framework, this work proposes to introduce a third scale called mesoscopic scale. This scale, at which both stress and strain can be defined, is intermediate between macroscopic and microscopic scales and allows to overcome the major difficulty mentioned above. The mesoscopic scale is defined at the level of local arrangements of particles, called sub-domains, and its relevance is studied on numerical 2D and 3D materials composed of circular then spherical particles, simulated with the discrete element method. Bidimensional media are geometrically represented by a particle graph composed of closed sub-domains, also called void cells, whose border is constituted by the branches joining the centers of particles in contact : the mesoscopic scale is thus defined at the level of these closed void cells. At this local scale, we fist describe the structure of the medium in terms of density and fabric ; we define then the static and kinematic variables in terms of stress and of strain. Strong heterogeneities of granular media in terms of structure, stress and strain are highlighted at this scale, with a structuration of heterogeneities of stress and strain and a significant correlation between these two quantities. Concerning tridimensional media, a partition into closed void cells is impossible, because of the complexity of the 3D structure of these media. We propose a partition method based on the distribution of voids inside the medium. This method consists first in subdividing the medium into tetrahedrons by a Delaunay partition and then in associating neighbouring tetrahedrons, according to a criterion to be defined. This allows us to form sub-domains which are not closed but which play a role analogous to the role of closed sub-domains in the 2D study. The proposed association criterion is based on the ratio between the size of constriction (void on each face of tetrahedrons) and the size of pores around each constriction. This partition method constitutes a preliminary step for an extension of the results obtained in the bidimensional case to the tridimensional case.
49

Quelques problèmes d'algorithmique et combinatoires en théorie des grapphes / A Few Problems of Algorithm and Complexity in Graph Theory

Legay, Sylvain 15 February 2017 (has links)
Le sujet de cette thèse est la théorie des graphes. Formellement, un graphe est un ensemble de sommets et un ensemble d’arêtes, c’est à dire de paires de sommets, qui relient les sommets. Cette thèse traite de différents problèmes de décisions binaires ou de minimisations liés à la notion de graphe, et cherche, pour chacun de ces problèmes, à déterminer sa classe de complexité, ou à fournir un algorithme. Le premier chapitre concerne le problème de trouver le plus petit sous-graphe connexe tropical dans un graphe sommet-colorié, c’est à dire le plus petit sous-graphe connexe contenant toutes les couleurs. Le deuxième chapitre concerne les problèmes d’homomorphisme tropical, une généralisation des problèmes de coloriage de graphe. On y trouve un lien entre ces problèmes et plusieurs classes de problèmes d’homomorphismes, dont la classe des Problèmes de Satisfaction de Contraintes. Le troisième chapitre concerne deux variantes lointaines du problème de domination, nommément les problèmes d’alliances globales dans un graphe pondéré et le problème de l’ensemble sûr. Le quatrième chapitre concerne la recherche d’une décomposition arborescente étoilée, c’est à dire une décomposition arborescente dont le rayon des sacs est 1. Enfin, le cinquième chapitre concerne une variante du problème de décider du comportement asymptotique de l’itéré du graphe des bicliques. / This thesis is about graph theory. Formally, a graph is a set of vertices and a set of edges, which are pair of vertices, linking vertices. This thesis deals with various decision problem linked to the notion of graph, and, for each of these problem, try to find its complexity class, or to give an algorithm. The first chapter is about the problem of finding the smallest connected tropical subgraph of a vertex-colored graph, which is the smallest connecter subgraph containing every colors. The second chapter is about problems of tropical homomorphism, a generalization of coloring problem. A link between these problems and several other class of homomorphism problems can be found in this chapter, especially with the class of Constraint Satisfaction Problem. The third chapter is about two variant of the domination problem, namely the global alliance problems in a weighted graph and the safe set problem. The fourth chapter is about the problem of finding a star tree-decomposition, which is a tree-decomposition where the radius of bags is 1. Finally, the fifth chapter is about a variant of the problem of deciding the asymptotic behavior of the iterated biclique graph
50

G-graphs and Expander graphs / G-graphes et les graphes d’expansion

Badaoui, Mohamad 30 March 2018 (has links)
L’utilisation de l’algèbre pour résoudre des problèmes de graphes a conduit au développement de trois branches : théorie spectrale des graphes, géométrie et combinatoire des groupes et études des invariants de graphes. La notion de graphe d’expansions (invariant de graphes) est relativement récente, elle a été développée afin d’étudier la robustesse des réseaux de télécommunication. Il s’avère que la construction de familles infinies de graphes expanseurs est un problème difficile. Cette thèse traite principalement de la construction de nouvelles familles de tels graphes. Les graphes expanseurs possèdent des nombreuses applications en informatique, notamment dans la construction de certains algorithmes, en théorie de la complexité, sur les marches aléatoires (random walk), etc. En informatique théorique, ils sont utilisés pour construire des familles de codes correcteurs d’erreur. Comme nous l’avons déjà vu les familles d’expanseurs sont difficiles à construire. La plupart des constructions s'appuient sur des techniques algébriques complexes, principalement en utilisant des graphes de Cayley et des produit Zig-Zag. Dans cette thèse, nous présentons une nouvelle méthode de construction de familles infinies d’expanseurs en utilisant les G-graphes. Ceux-ci sont en quelque sorte une généralisation des graphes de Cayley. Plusieurs nouvelles familles infinies d’expanseurs sont construites, notamment la première famille d’expanseurs irréguliers. / Applying algebraic and combinatorics techniques to solve graph problems leads to the birthof algebraic and combinatorial graph theory. This thesis deals mainly with a crossroads questbetween the two theories, that is, the problem of constructing infinite families of expandergraphs.From a combinatorial point of view, expander graphs are sparse graphs that have strongconnectivity properties. Expanders constructions have found extensive applications in bothpure and applied mathematics. Although expanders exist in great abundance, yet their explicitconstructions, which are very desirable for applications, are in general a hard task. Mostconstructions use deep algebraic and combinatorial approaches. Following the huge amountof research published in this direction, mainly through Cayley graphs and the Zig-Zagproduct, we choose to investigate this problem from a new perspective; namely by usingG-graphs theory and spectral hypergraph theory as well as some other techniques. G-graphsare like Cayley graphs defined from groups, but they correspond to an alternative construction.The reason that stands behind our choice is first a notable identifiable link between thesetwo classes of graphs that we prove. This relation is employed significantly to get many newresults. Another reason is the general form of G-graphs, that gives us the intuition that theymust have in many cases such as the relatively high connectivity property.The adopted methodology in this thesis leads to the identification of various approaches forconstructing an infinite family of expander graphs. The effectiveness of our techniques isillustrated by presenting new infinite expander families of Cayley and G-graphs on certaingroups. Also, since expanders stand in no single stem of graph theory, this brings us toinvestigate several closely related threads from a new angle. For instance, we obtain newresults concerning the computation of spectra of certain Cayley and G-graphs, and theconstruction of several new infinite classes of integral and Hamiltonian Cayley graphs.

Page generated in 0.0395 seconds