Théorie des graphes -Graph theory

Un dessin d'un graphique.

En mathématiques , la théorie des graphes est l'étude des graphes , qui sont des structures mathématiques utilisées pour modéliser des relations par paires entre des objets. Un graphe dans ce contexte est composé de sommets (également appelés nœuds ou points ) qui sont reliés par des arêtes (également appelées liens ou lignes ). On distingue les graphes non orientés , où les arêtes relient symétriquement deux sommets, et les graphes orientés , où les arêtes relient asymétriquement deux sommets. Les graphes sont l'un des principaux objets d'étude en mathématiques discrètes .

Définitions

Les définitions de la théorie des graphes varient. Voici quelques-unes des façons les plus élémentaires de définir des graphiques et des structures mathématiques associées .

Graphique

Un graphe à trois sommets et trois arêtes.

Dans un sens restreint mais très courant du terme, un graphe est un couple ordonné comprenant :

  • , un ensemble de sommets (aussi appelés nœuds ou points ) ;
  • , un ensemble d' arêtes (également appelées liens ou lignes ), qui sont des paires non ordonnées de sommets (c'est-à-dire qu'une arête est associée à deux sommets distincts).

Pour éviter toute ambiguïté, ce type d'objet peut être appelé précisément un graphe simple non orienté .

Dans l'arête , les sommets et sont appelés les extrémités de l'arête. On dit que le bord rejoint et et est incident sur et sur . Un sommet peut exister dans un graphe et ne pas appartenir à une arête. Les arêtes multiples , non autorisées par la définition ci-dessus, sont deux arêtes ou plus qui joignent les deux mêmes sommets.

Dans un sens plus général du terme autorisant plusieurs arêtes, un graphe est un triplet ordonné comprenant :

  • , un ensemble de sommets (aussi appelés nœuds ou points ) ;
  • , un ensemble d' arêtes (également appelées liens ou lignes ) ;
  • , une fonction d'incidence mappant chaque arête à une paire non ordonnée de sommets (c'est-à-dire qu'une arête est associée à deux sommets distincts).

Pour éviter toute ambiguïté, ce type d'objet peut être appelé précisément un multigraphe non orienté .

Une boucle est une arête qui joint un sommet à lui-même. Les graphes tels que définis dans les deux définitions ci-dessus ne peuvent pas avoir de boucles, car une boucle joignant un sommet à lui-même est l'arête (pour un graphe simple non orienté) ou est incidente sur (pour un multigraphe non orienté) qui n'est pas dans . Donc, pour autoriser les boucles, les définitions doivent être étendues. Pour les graphes simples non orientés, la définition de doit être modifiée en . Pour les multigraphes non orientés, la définition de doit être modifiée en . Pour éviter toute ambiguïté, ces types d'objets peuvent être appelés respectivement graphe simple non orienté permettant des boucles et multigraphe permettant des boucles (parfois aussi pseudographe non orienté ).

et sont généralement considérés comme finis, et de nombreux résultats bien connus ne sont pas vrais (ou sont plutôt différents) pour les graphes infinis car de nombreux arguments échouent dans le cas infini . De plus, est souvent supposé non vide, mais est autorisé à être l'ensemble vide. L' ordre d'un graphe est , son nombre de sommets. La taille d'un graphe est , son nombre d'arêtes. Le degré ou la valence d'un sommet est le nombre d'arêtes qui lui sont incidentes, où une boucle est comptée deux fois. Le degré d'un graphe est le maximum des degrés de ses sommets.

Dans un graphe simple non orienté d'ordre n , le degré maximum de chaque sommet est n − 1 et la taille maximum du graphe estn ( n - 1)/2.

Les arêtes d'un graphe simple non orienté autorisant des boucles induisent une relation homogène symétrique sur les sommets de que l'on appelle la relation d'adjacence de . Plus précisément, pour chaque arête , ses extrémités et sont dites adjacentes l'une à l'autre, ce que l'on note .

Graphique dirigé

Un graphe orienté avec trois sommets et quatre arêtes dirigées (la double flèche représente une arête dans chaque direction).

Un graphe orienté ou digraphe est un graphe dans lequel les arêtes ont des orientations.

Dans un sens restreint mais très courant du terme, un graphe orienté est un couple ordonné comprenant :

  • , un ensemble de sommets (aussi appelés nœuds ou points ) ;
  • , un ensemble d' arêtes (également appelées arêtes dirigées , liens dirigés , lignes dirigées , flèches ou arcs ) qui sont des paires ordonnées de sommets (c'est-à-dire qu'une arête est associée à deux sommets distincts).

Pour éviter toute ambiguïté, ce type d'objet peut être appelé précisément un graphe simple orienté . En théorie des ensembles et en théorie des graphes, désigne l'ensemble des n - tuples d'éléments de c'est-à-dire des séquences ordonnées d' éléments qui ne sont pas nécessairement distincts.

Dans l'arête dirigée de à , les sommets et sont appelés les extrémités de l'arête, la queue de l'arête et la tête de l'arête. On dit que le bord rejoint et et est incident sur et sur . Un sommet peut exister dans un graphe et ne pas appartenir à une arête. L'arête est appelée arête inversée de . Les arêtes multiples , non autorisées par la définition ci-dessus, sont deux arêtes ou plus avec à la fois la même queue et la même tête.

Dans un sens plus général du terme autorisant plusieurs arêtes, un graphe orienté est un triplet ordonné comprenant :

  • , un ensemble de sommets (aussi appelés nœuds ou points ) ;
  • , un ensemble d' arêtes (également appelées arêtes orientées , liens orientés , lignes orientées , flèches ou arcs ) ;
  • , une fonction d'incidence mappant chaque arête à une paire ordonnée de sommets (c'est-à-dire qu'une arête est associée à deux sommets distincts).

Pour éviter toute ambiguïté, ce type d'objet peut être appelé précisément un multigraphe orienté .

Une boucle est une arête qui joint un sommet à lui-même. Les graphes orientés tels que définis dans les deux définitions ci-dessus ne peuvent pas avoir de boucles, car une boucle joignant un sommet à lui-même est l'arête (pour un graphe simple orienté) ou est incidente sur (pour un multigraphe orienté) qui n'est pas dans . Donc, pour autoriser les boucles, les définitions doivent être étendues. Pour les graphes simples orientés, la définition de doit être modifiée en . Pour les multigraphes orientés, la définition de doit être modifiée en . Pour éviter toute ambiguïté, ces types d'objets peuvent être appelés précisément un graphe simple orienté permettant des boucles et un multigraphe orienté permettant des boucles (ou un carquois ) respectivement.

Les arêtes d'un graphe simple orienté permettant des boucles est une relation homogène ~ sur les sommets de que l'on appelle la relation d'adjacence de . Plus précisément, pour chaque arête , ses extrémités et sont dites adjacentes l'une à l'autre, ce qui est noté ~ .

Applications

Le graphe de réseau formé par les éditeurs de Wikipédia (arêtes) contribuant aux différentes versions linguistiques de Wikipédia (sommets) pendant un mois à l'été 2013.

Les graphes peuvent être utilisés pour modéliser de nombreux types de relations et de processus dans les systèmes physiques, biologiques, sociaux et d'information. De nombreux problèmes pratiques peuvent être représentés par des graphiques. Soulignant leur application aux systèmes du monde réel, le terme réseau est parfois défini comme signifiant un graphe dans lequel des attributs (par exemple des noms) sont associés aux sommets et aux arêtes, et le sujet qui exprime et comprend les systèmes du monde réel en tant que réseau est appelé science des réseaux .

L'informatique

Au sein de l'informatique , la cybernétique utilise des graphes pour représenter les réseaux de communication, l'organisation des données, les dispositifs de calcul, le flux de calcul, etc. Par exemple, la structure des liens d'un site Web peut être représentée par un graphe orienté, dans lequel les sommets représentent des pages Web. et les bords dirigés représentent des liens d'une page à une autre. Une approche similaire peut être adoptée pour les problèmes liés aux médias sociaux, aux voyages, à la biologie, à la conception de puces informatiques, à la cartographie de la progression des maladies neurodégénératives et à de nombreux autres domaines. Le développement d' algorithmes de manipulation de graphes est donc d'un intérêt majeur en informatique. La transformation de graphes est souvent formalisée et représentée par des systèmes de réécriture de graphes . En complément des systèmes de transformation de graphes axés sur la manipulation en mémoire basée sur des règles de graphes, il existe des bases de données de graphes orientées vers le stockage et l'interrogation persistants et sécurisés des transactions de données structurées en graphes .

Linguistique

Les méthodes de la théorie des graphes, sous diverses formes, se sont révélées particulièrement utiles en linguistique , car le langage naturel se prête souvent bien à la structure discrète. Traditionnellement, la syntaxe et la sémantique compositionnelle suivent des structures arborescentes, dont le pouvoir expressif réside dans le principe de compositionnalité , modélisé dans un graphe hiérarchique. Des approches plus contemporaines telles que la grammaire de structure de phrase basée sur la tête modélisent la syntaxe du langage naturel à l'aide de structures de caractéristiques typées , qui sont des graphes acycliques dirigés . Dans la sémantique lexicale , en particulier appliquée aux ordinateurs, la modélisation du sens des mots est plus facile lorsqu'un mot donné est compris en termes de mots apparentés ; les réseaux sémantiques sont donc importants en linguistique computationnelle . Pourtant, d'autres méthodes en phonologie (par exemple la théorie de l'optimalité , qui utilise des graphes en treillis ) et en morphologie (par exemple, la morphologie à états finis, utilisant des transducteurs à états finis ) sont courantes dans l'analyse du langage en tant que graphe. En effet, l'utilité de ce domaine des mathématiques pour la linguistique a donné naissance à des organisations telles que TextGraphs , ainsi qu'à divers projets «Net», tels que WordNet , VerbNet et autres.

Physique et chimie

La théorie des graphes est également utilisée pour étudier les molécules en chimie et en physique . En physique de la matière condensée , la structure tridimensionnelle de structures atomiques simulées complexes peut être étudiée quantitativement en rassemblant des statistiques sur les propriétés théoriques des graphes liées à la topologie des atomes. De plus, "les graphes et les règles de calcul de Feynman résument la théorie quantique des champs sous une forme en contact étroit avec les nombres expérimentaux que l'on veut comprendre." En chimie, un graphe constitue un modèle naturel pour une molécule, où les sommets représentent les atomes et les arêtes les liaisons . Cette approche est particulièrement utilisée dans le traitement informatique des structures moléculaires, allant des éditeurs chimiques à la recherche de bases de données. En physique statistique , les graphes peuvent représenter des connexions locales entre des parties en interaction d'un système, ainsi que la dynamique d'un processus physique sur de tels systèmes. De même, dans les neurosciences computationnelles , les graphiques peuvent être utilisés pour représenter des connexions fonctionnelles entre des zones cérébrales qui interagissent pour donner lieu à divers processus cognitifs, où les sommets représentent différentes zones du cerveau et les bords représentent les connexions entre ces zones. La théorie des graphes joue un rôle important dans la modélisation électrique des réseaux électriques, ici, des poids sont associés à la résistance des segments de fil pour obtenir les propriétés électriques des structures du réseau. Les graphiques sont également utilisés pour représenter les canaux à micro-échelle des milieux poreux , dans lesquels les sommets représentent les pores et les arêtes représentent les canaux plus petits reliant les pores. La théorie des graphes chimiques utilise le graphe moléculaire comme moyen de modéliser les molécules. Les graphes et les réseaux sont d'excellents modèles pour étudier et comprendre les transitions de phase et les phénomènes critiques. La suppression de nœuds ou de bords conduit à une transition critique où le réseau se divise en petits clusters qui est étudié comme une transition de phase. Cette répartition est étudiée via la théorie de la percolation .

Sciences sociales

Théorie des graphes en sociologie : Moreno Sociogram (1953).

La théorie des graphes est également largement utilisée en sociologie comme moyen, par exemple, de mesurer le prestige des acteurs ou d'explorer la diffusion de rumeurs , notamment grâce à l'utilisation de logiciels d'analyse des réseaux sociaux . Sous l'égide des réseaux sociaux, il existe de nombreux types de graphiques différents. Les graphiques de connaissance et d'amitié décrivent si les gens se connaissent. Les graphiques d'influence modélisent si certaines personnes peuvent influencer le comportement des autres. Enfin, les graphiques de collaboration modélisent si deux personnes travaillent ensemble d'une manière particulière, comme jouer ensemble dans un film.

La biologie

De même, la théorie des graphes est utile dans les efforts de biologie et de conservation où un sommet peut représenter des régions où certaines espèces existent (ou habitent) et les bords représentent des voies de migration ou des mouvements entre les régions. Ces informations sont importantes lorsqu'il s'agit d'examiner les schémas de reproduction ou de suivre la propagation des maladies, des parasites ou de la manière dont les changements de mouvement peuvent affecter d'autres espèces.

Les graphes sont également couramment utilisés en biologie moléculaire et en génomique pour modéliser et analyser des ensembles de données avec des relations complexes. Par exemple, les méthodes basées sur les graphiques sont souvent utilisées pour « regrouper » les cellules en types de cellules dans l'analyse du transcriptome unicellulaire . Une autre utilisation consiste à modéliser des gènes ou des protéines dans une voie et à étudier les relations entre eux, telles que les voies métaboliques et les réseaux de régulation des gènes. Les arbres évolutifs, les réseaux écologiques et le regroupement hiérarchique des modèles d'expression génique sont également représentés sous forme de structures de graphes.

La théorie des graphes est également utilisée en connectomique ; Les systèmes nerveux peuvent être vus comme un graphe, où les nœuds sont les neurones et les arêtes sont les connexions entre eux.

Mathématiques

En mathématiques, les graphes sont utiles en géométrie et dans certaines parties de la topologie comme la théorie des nœuds . La théorie algébrique des graphes a des liens étroits avec la théorie des groupes . La théorie des graphes algébriques a été appliquée à de nombreux domaines, notamment les systèmes dynamiques et la complexité.

Autres sujets

Une structure de graphe peut être étendue en attribuant un poids à chaque arête du graphe. Les graphes avec poids, ou graphes pondérés , sont utilisés pour représenter des structures dans lesquelles les connexions par paires ont des valeurs numériques. Par exemple, si un graphique représente un réseau routier, les poids pourraient représenter la longueur de chaque route. Il peut y avoir plusieurs pondérations associées à chaque tronçon, y compris la distance (comme dans l'exemple précédent), le temps de trajet ou le coût monétaire. Ces graphiques pondérés sont couramment utilisés pour programmer les GPS et les moteurs de recherche de planification de voyage qui comparent les temps et les coûts des vols.

Histoire

Le problème du pont de Königsberg

L'article écrit par Leonhard Euler sur les sept ponts de Königsberg et publié en 1736 est considéré comme le premier article de l'histoire de la théorie des graphes. Cet article, ainsi que celui rédigé par Vandermonde sur le problème du chevalier , poursuit l' analyse situs initiée par Leibniz . La formule d'Euler reliant le nombre d'arêtes, de sommets et de faces d'un polyèdre convexe a été étudiée et généralisée par Cauchy et L'Huilier , et représente le début de la branche des mathématiques connue sous le nom de topologie .

Plus d'un siècle après l'article d'Euler sur les ponts de Königsberg et alors que Listing introduisait le concept de topologie, Cayley s'intéressait à des formes analytiques particulières issues du calcul différentiel pour étudier une classe particulière de graphes, les arbres . Cette étude a eu de nombreuses implications pour la chimie théorique . Les techniques qu'il a utilisées concernent principalement l' énumération de graphes aux propriétés particulières. La théorie énumérative des graphes est alors née des résultats de Cayley et des résultats fondamentaux publiés par Pólya entre 1935 et 1937. Ceux-ci ont été généralisés par De Bruijn en 1959. Cayley a lié ses résultats sur les arbres aux études contemporaines de composition chimique. La fusion des idées des mathématiques avec celles de la chimie a commencé ce qui est devenu une partie de la terminologie standard de la théorie des graphes.

En particulier, le terme « graphe » a été introduit par Sylvester dans un article publié en 1878 dans Nature , où il établit une analogie entre les « invariants quantiques » et les « co-variants » de l'algèbre et des diagrammes moléculaires :

"[…] Tout invariant et co-variant devient ainsi exprimable par un graphe exactement identique à un diagramme ou chimiographe de Kekulé . […] Je donne une règle pour la multiplication géométrique des graphes, c'est-à-dire pour construire un graphe au produit de in- ou co-variantes dont les graphiques séparés sont donnés. […]" (italiques comme dans l'original).

Le premier manuel sur la théorie des graphes a été écrit par Dénes Kőnig , et publié en 1936. Un autre livre de Frank Harary , publié en 1969, a été "considéré dans le monde entier comme le manuel définitif sur le sujet", et a permis aux mathématiciens, chimistes, électriciens ingénieurs et spécialistes des sciences sociales de se parler. Harary a fait don de toutes les redevances pour financer le prix Pólya .

L'un des problèmes les plus célèbres et les plus stimulants de la théorie des graphes est le problème des quatre couleurs : "Est-il vrai que toute carte dessinée dans le plan peut avoir ses régions colorées avec quatre couleurs, de telle sorte que deux régions quelconques ayant une frontière commune aient Couleurs différentes?" Ce problème a été posé pour la première fois par Francis Guthrie en 1852 et sa première trace écrite se trouve dans une lettre de De Morgan adressée à Hamilton la même année. De nombreuses preuves incorrectes ont été proposées, y compris celles de Cayley, Kempe et d'autres. L'étude et la généralisation de ce problème par Tait , Heawood , Ramsey et Hadwiger ont conduit à l'étude des colorations des graphes encastrés sur des surfaces de genre arbitraire . La reformulation de Tait a généré une nouvelle classe de problèmes, les problèmes de factorisation , particulièrement étudiés par Petersen et Kőnig . Les travaux de Ramsey sur les colorations et plus spécialement les résultats obtenus par Turán en 1941 furent à l'origine d'une autre branche de la théorie des graphes, la théorie extrémale des graphes .

Le problème des quatre couleurs est resté sans solution pendant plus d'un siècle. En 1969, Heinrich Heesch a publié une méthode pour résoudre le problème à l'aide d'ordinateurs. Une preuve assistée par ordinateur réalisée en 1976 par Kenneth Appel et Wolfgang Haken fait un usage fondamental de la notion de « décharge » développée par Heesch. La preuve impliquait de vérifier les propriétés de 1 936 configurations par ordinateur et n'a pas été entièrement acceptée à l'époque en raison de sa complexité. Une preuve plus simple ne considérant que 633 configurations a été donnée vingt ans plus tard par Robertson , Seymour , Sanders et Thomas .

Le développement autonome de la topologie à partir de 1860 et 1930 a fécondé la théorie des graphes en passant par les travaux de Jordan , Kuratowski et Whitney . Un autre facteur important du développement commun de la théorie des graphes et de la topologie est venu de l'utilisation des techniques de l'algèbre moderne. Le premier exemple d'une telle utilisation vient des travaux du physicien Gustav Kirchhoff , qui publia en 1845 ses lois de circuit de Kirchhoff pour le calcul de la tension et du courant dans les circuits électriques .

L'introduction de méthodes probabilistes dans la théorie des graphes, en particulier dans l'étude d' Erdős et Rényi de la probabilité asymptotique de la connectivité des graphes, a donné naissance à une autre branche, connue sous le nom de théorie des graphes aléatoires , qui a été une source fructueuse de résultats en théorie des graphes.

Représentation

Un graphe est une abstraction des relations qui émergent dans la nature ; elle ne peut donc pas être couplée à une certaine représentation. La façon dont il est représenté dépend du degré de commodité qu'une telle représentation offre pour une certaine application. Les représentations les plus courantes sont les représentations visuelles, dans lesquelles, généralement, les sommets sont dessinés et reliés par des arêtes, et les représentations tabulaires, dans lesquelles les lignes d'un tableau fournissent des informations sur les relations entre les sommets dans le graphe.

Visuel : Dessin graphique

Les graphes sont généralement représentés visuellement en dessinant un point ou un cercle pour chaque sommet et en traçant une ligne entre deux sommets s'ils sont reliés par une arête. Si le graphique est orienté, la direction est indiquée en dessinant une flèche. Si le graphique est pondéré, le poids est ajouté sur la flèche.

Un dessin de graphe ne doit pas être confondu avec le graphe lui-même (la structure abstraite et non visuelle) car il existe plusieurs façons de structurer le dessin de graphe. Tout ce qui compte, c'est quels sommets sont connectés à quels autres par combien d'arêtes et non la disposition exacte. En pratique, il est souvent difficile de décider si deux dessins représentent le même graphique. Selon le domaine du problème, certaines mises en page peuvent être mieux adaptées et plus faciles à comprendre que d'autres.

Le travail de pionnier de WT Tutte a été très influent sur le sujet du dessin graphique. Entre autres réalisations, il a introduit l'utilisation de méthodes algébriques linéaires pour obtenir des dessins de graphes.

On peut également dire que le dessin de graphe englobe des problèmes qui traitent du nombre de croisements et de ses diverses généralisations. Le nombre de croisements d'un graphe est le nombre minimum d'intersections entre arêtes que doit contenir un dessin du graphe dans le plan. Pour un graphe planaire , le nombre de croisements est zéro par définition. Les dessins sur des surfaces autres que le plan sont également étudiés.

Il existe d'autres techniques pour visualiser un graphe éloigné des sommets et des arêtes, notamment les emballages de cercles , le graphe d'intersection et d'autres visualisations de la matrice d'adjacence .

Tabulaire : Structures de données graphiques

La représentation tabulaire se prête bien aux applications informatiques. Il existe différentes façons de stocker des graphiques dans un système informatique. La structure de données utilisée dépend à la fois de la structure du graphe et de l' algorithme utilisé pour manipuler le graphe. Théoriquement, on peut faire la distinction entre les structures de liste et de matrice, mais dans les applications concrètes, la meilleure structure est souvent une combinaison des deux. Les structures de liste sont souvent préférées pour les graphiques clairsemés car elles nécessitent moins de mémoire. Les structures matricielles , d'autre part, offrent un accès plus rapide à certaines applications, mais peuvent consommer d'énormes quantités de mémoire. Les implémentations de structures matricielles creuses qui sont efficaces sur les architectures informatiques parallèles modernes font actuellement l'objet d'investigations.

Les structures de liste incluent la liste des arêtes , un tableau de paires de sommets et la liste d'adjacence , qui répertorie séparément les voisins de chaque sommet : tout comme la liste des arêtes, chaque sommet a une liste des sommets auxquels il est adjacent.

Les structures matricielles incluent la matrice d'incidence , une matrice de 0 et de 1 dont les lignes représentent les sommets et dont les colonnes représentent les arêtes, et la matrice d'adjacence , dans laquelle les lignes et les colonnes sont indexées par les sommets. Dans les deux cas, un 1 indique deux objets adjacents et un 0 indique deux objets non adjacents. La matrice des degrés indique le degré des sommets. La matrice laplacienne est une forme modifiée de la matrice d'adjacence qui intègre des informations sur les degrés des sommets et est utile dans certains calculs tels que le théorème de Kirchhoff sur le nombre d' arbres couvrants d'un graphe. La matrice de distance , comme la matrice de contiguïté, a ses lignes et ses colonnes indexées par des sommets, mais plutôt que de contenir un 0 ou un 1 dans chaque cellule, elle contient la longueur d'un chemin le plus court entre deux sommets.

Problèmes

Énumération

Il existe une abondante littérature sur l'énumération graphique : le problème du dénombrement des graphes remplissant des conditions spécifiées. Certains de ces travaux se trouvent dans Harary et Palmer (1973).

Sous-graphes, sous-graphes induits et mineurs

Un problème courant, appelé problème d'isomorphisme de sous-graphe , consiste à trouver un graphe fixe comme sous-graphe dans un graphe donné. Une des raisons de s'intéresser à une telle question est que de nombreuses propriétés de graphe sont héréditaires pour les sous-graphes, ce qui signifie qu'un graphe a la propriété si et seulement si tous les sous-graphes l'ont aussi. Malheureusement, trouver des sous-graphes maximaux d'un certain type est souvent un problème NP-complet . Par exemple:

Un cas particulier d'isomorphisme de sous-graphe est le problème d'isomorphisme de graphe . Il demande si deux graphes sont isomorphes. On ne sait pas si ce problème est NP-complet, ni s'il peut être résolu en temps polynomial.

Un problème similaire consiste à trouver des sous-graphes induits dans un graphe donné. Encore une fois, certaines propriétés importantes du graphe sont héréditaires par rapport aux sous-graphes induits, ce qui signifie qu'un graphe a une propriété si et seulement si tous les sous-graphes induits l'ont également. Trouver des sous-graphes induits maximaux d'un certain type est également souvent NP-complet. Par exemple:

Encore un autre problème de ce type, le problème de confinement mineur , consiste à trouver un graphe fixe comme mineur d'un graphe donné. Un mineur ou une sous-contraction d'un graphe est tout graphe obtenu en prenant un sous-graphe et en contractant certaines (ou aucune) arêtes. De nombreuses propriétés de graphe sont héréditaires pour les mineurs, ce qui signifie qu'un graphe a une propriété si et seulement si tous les mineurs l'ont aussi. Par exemple, le théorème de Wagner stipule :

Un problème similaire, le problème de confinement de subdivision, consiste à trouver un graphe fixe comme subdivision d'un graphe donné. Une subdivision ou homéomorphisme d'un graphe est tout graphe obtenu en subdivisant certaines (ou aucune) arêtes. Le confinement des subdivisions est lié aux propriétés du graphe telles que la planéité . Par exemple, le théorème de Kuratowski stipule :

Un autre problème de confinement de subdivision est la conjecture de Kelmans–Seymour :

Une autre classe de problèmes concerne la mesure dans laquelle diverses espèces et généralisations de graphes sont déterminées par leurs sous-graphes à points supprimés . Par exemple:

Coloration graphique

De nombreux problèmes et théorèmes de la théorie des graphes concernent diverses manières de colorer les graphes. En règle générale, on s'intéresse à la coloration d'un graphe afin que deux sommets adjacents n'aient pas la même couleur, ou avec d'autres restrictions similaires. On peut également envisager de colorer les bords (éventuellement pour que deux bords coïncidents ne soient pas de la même couleur), ou d'autres variations. Parmi les résultats et conjectures célèbres concernant la coloration des graphes, citons les suivants :

Subsomption et unification

Les théories de la modélisation des contraintes concernent des familles de graphes orientés liés par un ordre partiel . Dans ces applications, les graphes sont classés par spécificité, ce qui signifie que les graphes plus contraints - qui sont plus spécifiques et contiennent donc une plus grande quantité d'informations - sont subsumés par ceux qui sont plus généraux. Les opérations entre les graphes comprennent l'évaluation de la direction d'une relation de subsomption entre deux graphes, le cas échéant, et le calcul de l'unification des graphes. L'unification de deux graphes d'arguments est définie comme le graphe le plus général (ou son calcul) qui est cohérent avec (c'est-à-dire contient toutes les informations dans) les entrées, si un tel graphe existe ; des algorithmes d'unification efficaces sont connus.

Pour les cadres de contraintes strictement compositionnels , l'unification de graphes est la fonction de satisfaisabilité et de combinaison suffisante. Les applications bien connues incluent la démonstration automatique de théorèmes et la modélisation de l' élaboration de la structure linguistique .

Problèmes d'itinéraire

Flux réseau

De nombreux problèmes se posent notamment pour les applications qui ont à voir avec diverses notions de flux dans les réseaux , par exemple :

Problèmes de visibilité

Couvrir les problèmes

Les problèmes de couverture dans les graphes peuvent faire référence à divers problèmes de couverture d'ensemble sur des sous-ensembles de sommets / sous-graphes.

  • Le problème des ensembles dominants est le cas particulier du problème de couverture d'ensembles où les ensembles sont les voisinages fermés .
  • Le problème de couverture de vertex est le cas particulier du problème de couverture d'ensembles où les ensembles à couvrir sont toutes les arêtes.
  • Le problème de couverture d'ensemble d'origine, également appelé ensemble de frappe, peut être décrit comme une couverture de sommet dans un hypergraphe.

Problèmes de décomposition

La décomposition, définie comme le partitionnement de l'ensemble des arêtes d'un graphe (avec autant de sommets que nécessaire accompagnant les arêtes de chaque partie de la partition), pose une grande variété de questions. Souvent, le problème est de décomposer un graphe en sous-graphes isomorphes à un graphe fixe ; par exemple, décomposer un graphe complet en cycles hamiltoniens. D'autres problèmes spécifient une famille de graphes dans laquelle un graphe donné doit être décomposé, par exemple une famille de cycles, ou décomposent un graphe complet K n en n − 1 arbres spécifiés ayant, respectivement, 1, 2, 3, ... , n − 1 arêtes.

Certains problèmes de décomposition spécifiques qui ont été étudiés comprennent:

Classes de graphes

De nombreux problèmes impliquent de caractériser les membres de différentes classes de graphes. Quelques exemples de ces questions sont ci-dessous :

Voir également

Rubriques connexes

Algorithmes

Sous-zones

Domaines connexes des mathématiques

Généralisations

Éminents théoriciens des graphes

Remarques

Les références

Liens externes

Manuels en ligne