Source : http://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes

Théorie des graphes

Aller à :Navigation,rechercher

	Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d'une fonction.

La théorie des graphes est une théorie informatique et mathématique. Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette théorie ont de nombreuses applications dans tous les domaines liés à la notion de réseau (réseau social, réseau informatique, Télécom…) et dans bien d'autres domaines (e.g. génétique) tant le concept de graphe, à peu près équivalent à celui de relation binaire (à ne pas confondre donc avec graphe d'une fonction), est général. De grands théorèmes difficiles, comme le Théorème des quatre couleurs et le Théorème des graphes parfaits, ont contribué à asseoir cette matière auprès des mathématiciens, et les questions qu'elle laisse ouvertes, comme la Conjecture d'Hadwiger, en font une branche vivace des Mathématiques discrètes.

Sommaire

 [masquer]

• 1 Définition de graphe et vocabulaire
• 2 Origines
• 3 Flots dans les réseaux
• 4 Introduction de probabilités
• 5 Représentations et invariants
  • 5.1 Étiquetage et morphismes
  • 5.2 Graphes et algèbre linéaire
  • 5.3 Décompositions arborescentes et en branches
• 6 Aspect algorithmique
  • 6.1 Structures de données
  • 6.2 Sous-graphes utiles : séparateurs, spanners et arbres de Steiner
  • 6.3 Réduction de données
• 7 Notions connexes
• 8 Notes
• 9 Références

Définition de graphe et vocabulaire [modifier]

Article détaillé : Lexique en théorie des graphes.

Intuitivement, un graphe est un ensemble de points, dont certaines paires sont directement reliées par un lien. Ces liens peuvent être orientés, c'est-à-dire qu'un lien entre deux points uet v relie soit u vers v, soit v vers u : dans ce cas, le graphe est dit orienté. Sinon, les liens sont symétriques, et le graphe est non-orienté.

Dans la littérature récente de la théorie des graphes, les points sont appelés les sommets (en référence aux polyèdres) ou les nœuds (en références à la loi des nœuds). Les liens sont appelés arêtes dans les graphes non-orienté et arcs dans un graphe orienté.

L'ensemble des sommets est le plus souvent noté V, tandis que E désigne l'ensemble des arêtes. Dans le cas général, un graphe peut avoir des arêtes multiples, c'est-à-dire que plusieurs arêtes différentes relient la même paire de points. De plus, un lien peut être une boucle, c'est-à-dire ne relier qu'un point à lui-même. Un graphe est simple si il n'a ni liens multiples ni boucles, il peut alors être défini simplement par un couple G = (V,E), où E est un ensemble de paires d'éléments de V. Dans le cas d'un graphe simple orienté, E est un ensemble de couples d'éléments de V. Notons qu'un graphe sans arête multiple peut être représenté par une relation binaire, qui est symétrique si le graphe est non-orienté.

Pour définir un graphe général, il faut une fonction d'incidence γ qui associe à chaque arête une paire de sommets (ou un couple en cas orienté). Ainsi, un graphe est un triplet G = (V,E,γ) avec . Toutefois l'usage veut que l'on note simplement G = (V,E), sachant que ce n'est parfaitement rigoureux que pour les graphes simples.

Origines [modifier]

Un article du mathématicien suisse Leonhard Euler, présenté à l'Académie de Saint Pétersbourg en 1735 puis publié en 1741, traitait du problème des sept ponts de Königsberg^{A 1}, ainsi que schématisé ci-dessous. Le problème consistait à trouver une promenade à partir d'un point donné qui fasse revenir à ce point en passant une fois et une seule par chacun des sept ponts de la ville de Königsberg. Un chemin passant par toute arête exactement une fois fut nommé chemin eulérien, ou circuit eulérien s'il finit là où il a commencé. Par extension, un graphe admettant un circuit eulérien est dit graphe eulérien, ce qui constitue donc le premier cas de propriété d'un graphe. Euler avait formulé¹ qu'un graphe n'est eulérien que si chaque sommet a un nombre pair d'arêtes. L'usage est de s'y référer comme théorème d'Euler, bien que la preuve n'y ait été apportée que 130 ans plus tard par le mathématicien allemand Carl Hierholzer^{A 2}. Un problème similaire consiste à passer par chaque sommet exactement une fois, et fut d'abord résolu avec le cas particulier d'un cavalier devant visiter chaque case d'un échiquier par le théoricien d'échec arabe Al-Adli dans son ouvrage Kitab ash-shatranj paru vers 840 et perdu depuis^{A 3}. Ce problème du cavalier fut étudié plus en détails au xviii^e sièclepar les mathématiciens français Alexandre-Théophile Vandermonde^{A 4}, Pierre de Rémond de Montfort et Abraham de Moivre; le mathématicien britannique Thomas Kirkman étudia le problème plus général du parcours où on ne peut passer par un sommet qu'une fois, mais un tel parcours prit finalement le nom de chemin hamiltonien d'après le mathématicien irlandaisWilliam Rowan Hamilton, et bien que ce dernier n'en ait étudié qu'un cas particulier^{A 5}. On accorde donc à Euler l'origine de la théorie des graphes parce qu'il fut le premier à proposer un traitement mathématique de la question, suivi par Vandermonde.

 

 →  → 

Liste des arbres à 2, 3 et 4 sommets.

Au milieu du XIX^e siècle, le mathématicien britannique Arthur Cayley s'intéressa aux arbres, qui sont un type particulier de graphe n'ayant pas de cycle, i.e. dans lequel il est impossible de revenir à un point de départ sans faire le chemin inverse. En particulier, il étudia le nombre d'arbres à n sommets^{A 6} et montra qu'il en existe . Ceci constitua « une des plus belles formules en combinatoire énumérative »^{A 7}, domaine consistant à compter le nombre d'éléments dans un ensemble fini, et ouvrit aussi la voie à l'énumération de graphes ayant certaines propriétés. Ce champ de recherche fut véritablement initié par le mathématicien hongrois George Pólya^{A 8}, qui publia un théorème d'énumération en 1937^{A 9}, et le mathématicien hollandais Nicolaas Govert de Bruijn. Les travaux de Cayley, tout comme ceux de Polya, présentaient des applications à la chimie et le mathématicien anglais James Joseph Sylvester, co-auteur de Cayley, introduisit en 1878 le terme de "graphe" basé sur la chimie :

« Il peut ne pas être entièrement sans intérêt pour les lecteurs de Nature d'être au courant d'une analogie qui m'a récemment fortement impressionné entre des branches de la connaissance humaine apparemment aussi dissemblables que la chimie et l'algèbre moderne. […] Chaque invariant et covariant devient donc exprimable par un graphe précisément identique à un diagramme Kékuléan ou chemicograph.^{A 10} »

Équivalence entre les régions d'une carte et un graphe pour le théorème des quatre couleurs.

Un des problèmes les plus connus de théorie des graphes vient de la coloration de graphe, où le but est de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon qu'aucun sommet n'ait la même couleur que ses voisins. En 1852, le mathématicien sud-africain Francis Guthrie énonça le problème des quatre couleurs par une discussion à son frère, qui demandera à son professeur Auguste De Morgan si toute carte peut être coloriée avec quatre couleurs de façon à ce que des pays voisins aient des couleurs différentes. De Morgan envoya d'abord une lettre au mathématicien irlandais William Rowan Hamilton, qui n'était pas intéressé, puis le mathématicien anglais Alfred Kempe publia une preuve erronée^{A 11} dans l’American Journal of Mathematics, qui venait d'être fondé par Sylvester. L'étude de ce problème entraîna de nombreux développements en théorie des graphes, par Peter Guthrie Tait, Percy John Heawood,Frank Ramsey et Hugo Hadwiger.

Les problèmes de factorisation de graphe émergèrent ainsi à la fin du XIX^e siècle en s'intéressant aux sous-graphes couvrants, c'est-à-dire aux graphes contenants tous les sommets mais seulement une partie des arêtes. Un sous-graphe couvrant est appelé un k-facteur si chacun de ses sommets a k arêtes et les premiers théorèmes furent donnés par Julius Petersen^{A 12}; par exemple, il montra qu'un graphe peut être séparé en 2-facteurs si et seulement si tous les sommets ont un nombre pair d'arêtes (mais il fallut attendre 50 ans pour que Bäbler traite le cas impair^{A 13}). Les travaux de Ramsey sur la coloration, et en particulier les résultats du mathématicien hongrois Pal Turan, permirent le développement de la théorie des graphes extrémaux s'intéressant aux graphes atteignant le maximum d'une quantité particulière (par exemple le nombre d'arêtes) avec des contraintes données^{A 14}, telles que l'absence de certains sous-graphes.

Dans la seconde moitié du xx^e siècle, le mathématicien français Claude Berge contribue au développement de la théorie des graphes par ses contributions sur les graphes parfaits^{A 15} et l'introduction du terme d’hypergraphe (suite à la remarque de Jean-Marie Pla l'ayant utilisé dans un séminaire) avec un monographe^{A 16} sur le sujet. Son ouvrage d'introduction à la théorie des graphes^{A 17} proposa également une alternative originale, consistant plus en une promenade personnelle qu'une description complète. Il marquera également la recherche française en ce domaine, par la création conjointe avec Marcel-Paul Schützenberger d'un séminaire hebdomadaire à l'Institut Henri Poincaré, des réunions le lundi à la Maison des Sciences de l'Homme, et la direction de l'équipe Combinatoire de Paris.

Flots dans les réseaux [modifier]

Représentation du flot dans un graphe, indiquant pour chaque arête le flot a qui la traverse et sa capacité maximale b, sous la forme a/b.

Coupe dans un graphe, avec la source set le puits t'.

Exemple d'application des flots réseaux pour le mouvement d'un fluide dans un réseau hydraulique.

Les Allemands Franz Ernst Neumann et Jacobi, respectivement physicien et mathématicien, fondèrent en 1834 une série de séminaires. Le physicien allemand Gustav Kirchhoff était un des étudiants participant au séminaire entre 1843 et 1846, et il étendit le travail de Georg Ohmpour établir en 1845 les Lois de Kirchhoff exprimant la conservation de l'énergie et de la charge dans un circuit électrique. En particulier, sa loi des nœuds stipule que la somme des intensités des courants entrant dans un nœud est égale à celle qui en sort. Un circuit électrique peut se voir comme un graphe, dans lequel les sommets sont les nœuds du circuit, et les arêtes correspondent aux connexions physiques entre ces nœuds. Pour modéliser les courants traversant le circuit, on considère que chaque arête peut-être traversée par un flot. Ceci offre de nombreuses analogies, par exemple à l'écoulement d'un liquide comme l'eau à travers un réseau de canaux^{B 1}, ou la circulation dans un réseau routier. Comme stipulé par la loi des nœuds, le flot à un sommet est conservé, ou identique à l'entrée comme à la sortie; par exemple, l'eau qui entre dans un canal ne disparaît pas et le canal n'en fabrique pas, donc il y a autant d'eau en sortie qu'en entrée. De plus, une arête a une limite de capacité, tout comme un canal peut transporter une certaine quantité maximale d'eau. Si l'on ajoute que le flot démarre à un certain sommet (la source) et qu'il se termine à un autre (le puits), on obtient alors les principes fondamentaux de l'étude des flots dans un graphe.

Si on considère que la source est un champ pétrolifère et que le puits est la raffinerie où on l'écoule, alors on souhaite régler les vannes de façon à avoir le meilleur débit possible de la source vers le puits. En d'autres mots, on cherche à avoir une utilisation aussi efficace que possible de la capacité de chacune des arêtes, ce qui est le problème de flot maximum. Supposons que l'on « coupe » le graphe en deux parties, telle que la source est dans l'une et le puits est dans l'autre. Chaque flot doit passer entre les deux parties, et est donc limité par la capacité maximale qu'une partie peut envoyer à l'autre. Trouver la coupe avec la plus petite capacité indique donc l'endroit où le réseau est le plus limité, ce qui revient à établir le flot maximal qui peut le traverser^{B 2}. Ce théorème est appelé flot-max/coupe-min et fut établi en 1956.

L’étude des flots réseaux se généralise de plusieurs façons. La recherche d'un maximum, ici dans le cas du flot, est un problème d'optimisation, qui est la branche des mathématiques consistant à optimiser (i.e. trouver un minimum ou maximum) une fonction sous certaines contraintes. Un flot réseau est soumis à trois contraintes^{B 3} : la limite de capacité sur chaque arête, la création d'un flot non nul entre la source et le puits (i.e. la source crée un flot), et l'égalité du flot en entrée/sortie pour tout sommet autre que la source et les puits (i.e.ils ne consomment ni ne génèrent une partie du flot). Ces contraintes étant linéaires, le problème d'un flot réseau fait partie de laprogrammation linéaire. Il est également possible de rajouter d'autres variables au problème pour prendre en compte davantage de situations : on peut ainsi avoir plusieurs sources et puits, une capacité minimale sur chaque arête, un coût lorsqu'on utilise une arête, ou une amplification du flot passant par une arête.

Introduction de probabilités [modifier]

Schéma d'une transition de phase, ayant l'allure typique rencontrée dans le cas d'un graphe aléatoire.

Jusqu'au milieu du XX^e siècle, l'algorithme construisant un graphe n'avait rien d'aléatoire : tant que les paramètres fournis à l'algorithme ne changeaient pas, alors le graphe qu'il construisait était toujours le même. Une certaine dose d'aléatoire fut alors introduite, et les algorithmes devinrent ainsi probabilistes. Le mathématicien d'origine russe Anatol Rapoport eut d'abord cette idée en 1957^{C 1} mais elle fut proposée indépendamment deux ans après, de façon plus formelle, par les mathématiciens hongrois Paul Erdős et Alfréd Rényi^{C 2}. Ceux-ci se demandèrent à quoi ressemble un graphe « typique » avec n sommets et m arêtes. Ils souhaitaient ainsi savoir quelles propriétés pouvaient être trouvées avec n sommets, et m arêtes créées au hasard. Une quantité fixe m n'étant pas pratique pour répondre à cette question^{C 3}, il fut décidé que chaque arête existerait avec une probabilité p. Ceci fut le début de la théorie des graphes aléatoires, où l'on considère un nombre de sommets n assez grand, et l'on s'intéresse à la probabilité p suffisante pour que le graphe ait une certaine propriété.

Abstraction d'une pierre par une grille de 50 x 50. Seuls les canaux sont représentés.

Exemples de graphes aléatoires

 (1/3)▶

20 sommets et probabilité 0.1

La distribution du degré donne la quantité de sommets par nombre de connexions (par exemple, il y a 30 sommets ayant 25 voisins, où 30 est en ordonnée et25 en abscisse). Le graphe aléatoire d'Erdős et Rényi engendre une distribution normale.

Erdős et Rényi découvrirent que le graphe n'évoluait pas de façon linéaire mais qu'il y avait au contraire une probabilité critique p après laquelle il changeait de façon radicale. Ce comportement est bien connu en physique : si l'on observe un verre d'eau que l'on met dans un congélateur, il ne se change pas progressivement en glace mais plutôt brutalement lorsque la température passe en dessous de 0°C. L'eau avait deux phases (liquide et glace) et passe de l'une à l'autre par un phénomène nommé transition de phase, la transition étant rapide autour d'un point critique qui est dans ce cas la température de 0°C. Pour nombre de propriétés observées, les graphes aléatoires fonctionnent de la même manière^{C 4} : il existe une probabilité critique  en dessous de laquelle ils se trouvent dans une phase sous-critique, et au-dessus de laquelle ils passent en phase sur-critique. Dans le cas d'un graphe aléatoire, la probabilité que l'on observe la propriété nous intéressant est faible en phase sous-critique mais devient très forte (i.e. quasi-certitude) en phase sur-critique; le tracé de la probabilité d'avoir la propriété en fonction de p a donc une allure bien particulière, simplifiée dans le schéma à droite.

Au-delà du vocabulaire commun des phases, la théorie des graphes aléatoires se retrouve enphysique statistique sous la forme de la théorie de la percolation^{C 5}. Cette dernière visait à l'origine à étudier l'écoulement d'un fluide à travers un matériau poreux. Par exemple, si l'on immerge une pierre ponce dans un seau rempli d'eau^{C 6}, on s'intéresse à la façon dont l'eau va s'écouler dans la pierre. Pour modéliser ce problème, on se concentre sur les paramètres importants : l'âge ou la couleur de la pierre n'importe pas, tandis que les ouvertures ou 'canaux' dans lesquels peut circuler l'eau sont primordiaux. L'abstraction la plus simple est de voir une pierre comme une grille, où chaque canal existe avec une probabilité p. On retrouve ainsi le modèle du graphe aléatoire, mais avec une contrainte spatiale : un arc ne peut exister entre deux sommets que s'ils sont voisins dans la grille. Cependant, cette contrainte peut-être levée pour établir une équivalence entre la théorie des graphes et celle de la percolation. Tout d'abord, un graphe de n sommets peut être représenté par une grille avec n dimensions; puisqu'on s'intéresse au cas où n est assez grand, c'est-à-dire , ceci établit une équivalence avec la percolation en dimension infinie. De plus, il existe une dimension critique  telle que le résultat ne dépend plus de la dimension dès que celle-ci atteint ; on pense que cette dimension critique est 6, mais elle n'a pu être prouvée^{C 7} que pour 19.

De nombreux modèles ont été proposés depuis le début des années 2000 pour retrouver des phénomènes observés dans des graphes tels que celui représentant les connexions entre des acteurs de Hollywood (obtenu par IMDb) ou des parties du Web. En 1999, Albert-Laszlo Barabasi et Réka Albert expliquèrent qu'un de ces phénomènes « est une conséquence de deux mécanismes : le réseau grandit continuellement avec l'ajout de nouveaux sommets, et les nouveaux sommets s'attachent avec certaines préférences à d'autres qui sont déjà bien en place »^{C 8}. Une certaine confusion s'installa autour de leur modèle : s'il permet effectivement d'obtenir le phénomène souhaité, il n'est pas le seul modèle arrivant à ce résultat et on ne peut donc pas conclure en voyant le phénomène qu'il résulte d'un processus d'attachement préférentiel. Les phénomènes de petit monde et de libre d'échelle, pour lesquels de très nombreux modèles ont été proposés, peuvent être réalisés simplement par des graphes aléatoires^{C 9} : la technique de Michael Molley et Bruce Reed^{C 10} permet d'obtenir l'effet de libre d'échelle, tandis que celle de Li, Leonard et Loguinov conduit au petit-monde^{C 11}.

Représentations et invariants [modifier]

Étiquetage et morphismes [modifier]

Formellement un graphe est étiqueté : chaque sommet ou arête appartient à un ensemble, donc porte une étiquette. Typiquement, les graphes sont étiquetés par des nombres entiers, mais une étiquette peut en fait appartenir à n'importe quel ensemble : ensemble de couleurs, ensemble de mots, ensemble des réels. Les exemples ci-contre montrent des graphes étiquetés par des entiers et par des lettres. L'étiquetage d'un graphe peut-être conçu de façon à donner des informations utiles pour des problèmes comme le routage : partant d'un sommet u, on veut arriver à un sommet v, c'est-à-dire que l'on souhaite acheminer une information de u à v. Selon la façon dont les sommets sont étiquetés, les étiquettes que portent uet v peuvent nous permettre de trouver facilement un chemin. Par exemple, dans le graphe de Kautz où la distance maximale entre deux sommets est D, imaginons que l'on soit à un sommet étiqueté (x₁,x₂,...,x_D) et que l'on souhaite aller à (y₁,y₂,...,y_D) : il suffit de décaler l'étiquette en introduisant la destination^{D 1}, ce qui donne le chemin . Ce chemin se lit de la façon suivante : si on se trouve au sommet étiqueté (x₁,x₂,...,x_D) alors on va vers le voisin portant l'étiquette (x₂,...,x_D,y₁), et ainsi de suite.

On se retrouve cependant face à un problème : si on regarde plus haut l'illustration de la liste des arbres à 2, 3 et 4 sommets, beaucoup d'entre eux ont exactement la même structuremais un étiquetage différent (donné ici par des couleurs). Pour étudier uniquement la structure, il faut donc un outil permettant d'ignorer l'étiquetage, c'est-à-dire de donner une équivalence structurelle. Pour cela, on introduit la notion de morphisme. Un morphisme de graphes^{D 2}, ou homomorphisme de graphe, est une application entre deux graphes qui respecte la structure des graphes. Autrement dit l'image du graphe G dans H doit respecter les relations d'adjacences présentes dans G. Plus précisément, si G et H sont deux graphes, une application  est un morphisme de graphe si f = (f_V,f_E) où  transforme les sommets de G en ceux de H, et  les arêtes de G en celles de H en respectant la contrainte suivante : s'il existe une arête  entre deux sommets de G alors il doit y avoir une arête entre les deux sommets correspondants de H. On dit de l'homomorphisme f qu'il est une injection (respectivement surjection) si ses deux fonctions f_V et f_E sont injectives (respectivement surjectives); si elles sont à la fois injectives et surjectives, c'est-à-dire bijectives, alors f est un isomorphisme. Si deux graphes sont isomorphes, alors ils ont la même structure : peu importe la façon dont ils sont dessinés ou étiquetés, il est possible de déplacer les sommets ou de changer les étiquettes pour que l'un soit la copie conforme de l'autre, ainsi qu'illustré ci-dessous. On désigne alors par graphe non étiqueté la classe d'équivalence d'un graphe pour la relation d'isomorphisme. Deux graphes isomorphes seront alors considérés comme égaux si on les considère en tant que graphes non étiquetés.

Graphe G	Graphe H	Isomorphisme entre G et H
		ƒ(a) = 1 ƒ(b) = 6 ƒ(c) = 8 ƒ(d) = 3 ƒ(g) = 5 ƒ(h) = 2 ƒ(i) = 4 ƒ(j) = 7

Le mot graphe peut désigner, selon les contextes, un graphe étiqueté ou non étiqueté. Quand on parle du graphe du web, les étiquettes sont des URL et ont un sens. Le mot est utilisé pour désigner un graphe étiqueté. À l'opposé le graphe de Petersen est toujours considéré à isomorphisme près, donc non étiqueté, seules ses propriétés structurelles étant intéressantes.

L'hypercube Q3 étiqueté sur l'alphabet {0,1}

Graphe étiqueté par des entiers

Graphe étiqueté par des lettres

Graphes et algèbre linéaire [modifier]

Tout graphe G = (V,E) peut être représenté par une matrice. Les relations entre arêtes et sommets, appelées les relations d'incidence, sont toutes représentées par la matrice d'incidence du graphe. Les relations d'adjacences (si deux sommets sont reliés par une arête ils sont adjacents) sont représentés par sa matrice d'adjacence. Elle est définie par

Graphe	Représentation par une matrice d'adjacence	Représentation par une matrice laplacienne (non normalisée)

De nombreuses informations d'un graphe peuvent-être représentées par une matrice. Par exemple, la matrice des degrés D est une matrice diagonale où les éléments D_ii correspondent au nombre de connexions du sommet i, c'est-à-dire à son degré. En utilisant cette matrice et la précédente, on peut également définir la matrice laplacienne L = D − A; on obtient sa forme normalisée L' par L' = D ^{− 1 / 2}LD ^{− 1 / 2} = I − D ^{− 1 / 2}AD ^{− 1 / 2}, où I dénote la matrice identité, ou on peut aussi l'obtenir directement par chacun de ses éléments :

Ces représentations dépendent de la façon dont les sommets du graphe sont étiquetés. Imaginons que l'on garde la même structure que dans l'exemple ci-dessus et que l'on inverse les étiquettes 1 et 6 : on inverse alors les colonnes 1 et 6 de la matrice d'adjacence. Il existe en revanche des quantités qui ne dépendent pas de la façon dont on étiquette les sommets, tels que le degré minimal/maximal/moyen du graphe. Ces quantités sont des invariants du graphe : elles ne changent pas selon la numérotation. Tandis qu'une matrice d'adjacence ou laplacienne varie, son spectre, c'est-à-dire l'ensemble de ses valeurs propres , est un invariant. L'étude du rapport entre les spectres et les propriétés d'un graphe est le sujet de la théorie spectrale des graphes^{D 3}; parmi les rapports intéressants, le spectre donne des renseignements sur le nombre chromatique, le nombre de composantes connexes et les cycles du graphe.

Décompositions arborescentes et en branches [modifier]

Décomposition arborescente à 6 sommets d'un graphe à 8 sommets. Chaque nœud de la décomposition contient au plus trois sommets du graphe original, et la profondeur de cette décomposition est donc 2.

Les graphes permettant de représenter de nombreuses situations, il existe de nombreux algorithmes (i.e. programmes) les utilisant. Lacomplexité d'un algorithme consiste essentiellement à savoir, pour un problème donné, combien de temps est nécessaire pour le résoudre et quel est l'espace machine que cela va utiliser. Certaines représentations de graphes permettent d'obtenir de meilleures performances, c'est-à-dire que le problème est résolu plus rapidement ou en occupant moins d'espace. Dans certains cas, un problème NP-complet (classe la plus ardue) sur une représentation d'un graphe peut être résolu en temps polynomial (classe simple) avec une autre représentation; l'idée n'est pas qu'il suffit de regarder le graphe différemment pour résoudre le problème plus vite, mais que l'on « paye » pour le transformer et que l'on « économise » alors pour résoudre le problème. Une telle transformation est la décomposition arborescente proposée par les mathématiciensRobertson et Seymour dans leur série Graph Minors ^{D 4}. Intuitivement, une décomposition arborescente représente le graphe d'origine G par un arbre, où chaque sommet correspond à un sous-ensemble des sommets de G, avec quelques contraintes. Formellement, pour un graphe donné G = (V,E), sa décomposition arborescente est (f,T) où T est un arbre et f une fonction associant à chaque sommet  un ensemble de sommets . Trois contraintes doivent être satisfaites :

• . La décomposition n'oublie aucun sommet du graphe d'origine.
•  tel que .
•  si q est sur le chemin de p à r alors . Si l'on prend l'intersection des sommets abstraits par deux nœuds de l'arbre, alors cette intersection doit être contenue dans un sommet intermédiaire. Sur l'exemple ci-contre, l'intersection de {A,B,C} et {C,D,E} est {C} qui est bien contenue dans le sommet intermédiaire {C,B,E}.

La largeur arborescente tw(G) d'une décomposition (f,T) d'un graphe G est , c'est-à-dire la taille du plus grand ensemble représenté par un sommet moins 1; on peut la voir comme l'abstraction maximale : pour un sommet de l'arbre, jusqu'à combien de sommets du graphe représente-t-on ? Construire la décomposition arborescente d'un graphe quelconque avec la plus petite largeur arborescente est un problème NP-dur^{D 5}. Cependant, cela peut-être fait rapidement pour certains graphes^{D 6}, ou approximée^{D 7} pour d'autres tels les graphes planaires (i.e. pouvant être dessinés sans croiser deux arêtes).

Exemple d'un arbre, ayant 1 comme racine, {2,4,5,7} comme nœuds internes et{3,6,8,9,10,11,12} comme feuilles.

Robertson et Seymour développèrent également le concept de décomposition en branches. Pour la comprendre, il faut introduire davantage de vocabulaire sur un arbre. Dans les graphes, un arbre est dessiné "à l'envers" : on démarre de la racine en haut, et on descend jusqu'à atteindre les feuilles en bas; tout sommet n'étant pas une feuille est appelé un 'nœud interne'. La décomposition en branches résulte en un arbre dans lequel tout nœud interne a exactement trois voisins (comme sur l'exemple ci-contre), et où chaque feuille représente une arête du graphe d'origine. La profondeur minimale de la décomposition d'un graphe G est notée bw(G), et on a la relation . De même que pour la décomposition arborescente, il est NP-dur de construire une décomposition en branches avec bw(G) minimal pour un graphe quelconque; dans ce cas, cette construction est réalisable pour un graphe planaire^{D 8}.

Ces représentations sont utilisées sur des problèmes NP-complets par des techniques de programmation dynamique, qui prennent généralement un temps exponentiel en bw(G) ou tw(G). Un tel problème est par exemple l'ensemble dominant : on veut savoir s'il y a un sous-ensemble D de sommets de taille au plus k tel qu'un sommet n'étant pas dans D y soit relié par une arête. Si le graphe est planaire, cette technique permet de résoudre le problème^{D 9} en temps .

Aspect algorithmique [modifier]

Structures de données [modifier]

La façon dont le graphe est représenté en tant que objet mathématique a été exposée dans la section précédente. Dans l'aspect algorithmique de la théorie des graphes, on cherche à concevoir un processus efficace pour traiter un problème faisant intervenir un graphe. Les principaux critères d'efficacités d'un processus sont le temps nécessaire avant d'obtenir la réponse, et l'espace que le processus consomme dans son travail. La façon dont on représente le graphe influence la performance en temps et en espace : par exemple, si l'on veut connaître l'existence d'une arête entre deux sommets, la matrice d'adjacence permettra d'obtenir un résultat immédiatement, ce que l'on appelle en θ(1). En revanche, une opération de base telle que trouver le voisin d'un sommet est en O(n) sur une matrice d'adjacence : dans le pire des cas, il faudra scanner la totalité de la colonne pour s'apercevoir qu'il n'y a pas de voisin. Une autre structure de données est la liste d'adjacences, consistant en un tableau dont l'entrée i donne la liste des voisins du sommet i : sur une telle structure, trouver un voisin se fait en θ(1) tandis que l'existence d'une arête est en O(n). Ainsi, au niveau du temps, le choix de la structure dépend des opérations de base que l'on souhaite optimiser.

Un graphe étiqueté et sa représentation par liste d'adjacence ci-contre.

Représentation par liste d'adjacence du graphe ci-contre:
0	adjacent à	0,1,2,3
1	adjacent à	0
2	adjacent à	0,3,4
3	adjacent à	0,2
4	adjacent à	2

De même, l'espace qu'une structure consomme dépend du type de graphe considéré : un raccourci abusif consiste à dire qu'une liste d'adjacences consomme moins d'espace qu'une matrice car celle-ci sera creuse, mais cela prend par exemple plus d'espace pour stocker un graphe aléatoire avec les listes qu'avec une matrice; dans le cas général, une matrice utilise un espace θ(n²) et les listes utilisent  donc si le graphe est dense alors m peut-être suffisamment grand pour qu'une matrice consomme moins d'espace, et si le graphe est peu dense alors les listes consommeront moins d'espace. Des modifications simples d'une structure de données peuvent permettre d'avoir un gain appréciable : par exemple, dans une représentation partiellement complémentée d'une liste, un bit spécial indique si la liste est celle des voisins présents ou manquants; cette technique permet d'avoir des algorithmes linéaires sur le complément d'un graphe ^{E 1}.

Tandis que ces structures sont locales, il existe aussi des structures de données distribuées. Le principe de ces structures est de concevoir un schéma d'étiquetage tel que, pour deux sommets x et y, on puisse répondre à une question comme « quelle est la distance entre x et y » uniquement en utilisant les étiquettes de ces nœuds; une telle utilisation des étiquettes a été vue en section 4.1 avec le graphe de Kautz où l'on peut déduire le chemin entre deux sommets uniquement grâce à leur étiquette, et la longueur de ce chemin nous donne la distance. Un étiquetage est efficace s'il permet de répondre à une question donnée uniquement en utilisant deux étiquettes, tout en minimisant le nombre maximum de bits d'une étiquette^{E 2}. Outre la distance, une question type peut-être de tester l'adjacence, c'est-à-dire de savoir si deux sommets sont voisins; notons que cela se ramène également au cas particulier d'une distance 1. Le premier exemple d'étiquetage efficace pour tester l'adjacence fut proposé dans le cas des arbres, et chaque étiquette est constituée de deux parties de  bits : la première partie identifie le sommet, et un nombre allant jusqu'à n nécessite  bits pour être codé, tandis que la seconde partie identifie le parent de ce sommet; pour tester l'adjacence, on utilise le fait que deux sommets sont voisins dans un arbre si et seulement si l'un est le parent de l'autre^{E 3}.

Sous-graphes utiles : séparateurs, spanners et arbres de Steiner [modifier]

Cette section est vide, pas assez détaillée ou incomplète. Votre aide est la bienvenue !

L'efficacité d'un schéma d'étiquetage est lié à la taille des séparateurs du graphe.

Définition — un séparateur S est un sous-ensemble de sommet qui « sépare » les sommets du graphe en deux composants A₁ et A₂ tel que  et il n'y a pas d'arêtes entre des sommets de A₁ et A₂.

Illustration d'un séparateur

 (1/3)▶

Étant donné un graphe avec un ensemble de sommets V, ...

Si un graphe a des séparateurs de taille r(n), alors on peut par exemple concevoir des étiquettes de  bits pour la distance; ceci permet directement d'en déduire l'étiquetage pour des graphes dont on connaît la taille des séparateurs, tels un graphe planaire où le séparateur est de taille ^{E 4}. Enfin, il ne faut pas considérer que la taille de l'étiquetage mais également le temps nécessaire, étant donnés deux étiquettes, pour effectuer le décodage répondant à la question (i.e. quelle est la distance ? sont-ils voisins ?).

Réduction de données [modifier]

Cette section est vide, pas assez détaillée ou incomplète. Votre aide est la bienvenue !

De nombreux problèmes sur les graphes sont NP-complets, c'est-à-dire durs à résoudre. Cependant, cette dureté est inégale : certaines parties du problème peuvent être particulièrement dures, et en constituent ainsi le cœur, tandis que d'autres sont assez faciles à gérer. Ainsi, avant d'exécuter un algorithme sur un problème qui peut-être dur, il est préférable de passer du temps à réduire ce problème pour ne plus avoir à considérer que son cœur.

Notions connexes [modifier]

• Un graphe est également un espace topologique de dimension 1 dont la généralisation est un complexe simplicial.

Notes [modifier]

1. ↑ Au regard des mathématiques modernes, la formulation d'Euler est une conjecture puisque le résultat est énoncé sans preuve. Cependant, les mathématiques en son temps ne présentaient pas la même rigueur : tandis que conjecturer un résultat signifie maintenant que l'on renonce à le démontrer, pour Euler l'absence d'une preuve peut signifier que celle-ci n'était pas considérée utile.

Références [modifier]

A - Origines ↑ (la) Leonhard Euler - Solutio problematis ad geometriam situs pertinentis [archive],Commentarii academiae scientiarum Petropolitanae 8, 1741, pages 128-140. ↑ (de) Carl Hierholzer - Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren [archive], Mathematische Annalen VI, 1873, pages 30–32. ↑ (en) Martin G. - The arab role in the development of Chess [archive], Al Shindagah 45, Mars-Avril 2002 ↑ (fr) Alexandre-Théophile Vandermonde - Remarques sur des problèmes de situation,Mémoires de l’Académie Royale des Sciences, 1771, pages 566-574. Références par (ru)LJ.Rossia.org [archive] ↑ (en) William Tutte - Graph theory as I have known it, Oxford Science Publications, Clarendon Press, 1998, (ISBN 0198502516). Chapitre 2 : Knight Errant. ↑ (en) Arthur Cayley - On the Theory of the Analytical Forms called Trees [archive], Phil. Mag., 1857, pages 172-176. ↑ (fr) Martin Aigner et Günter M. Ziegler - La formule de Cayley pour le nombre d’arbres [archive], Raisonnements divins 2ème édition, 2006 ↑ (en) George Polya et R. C. Read - Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds [archive], Springer 1987. ↑ (de) George Polya - Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen [archive], Acta Mathematica 68 (1), pages 145–254. ↑ (en) James Joseph Sylvester - Chemistry and algebra [archive], Nature 17, page 284, 7 février 1878. ↑ (en) Alfred Bray Kempe - On the Geographical Problem of the Four Colours [archive],American Journal of Mathematics, Vol. 2, No. 3, septembre 1879, pages 193-200. ↑ (de) Julius Petersen - Die Theorie der regulären Graphen [archive], Acta Mathematica 15, 1891, page 193-220. ↑ (de) F. Bäbler - Über die Zerlegung regulärer Streckencomplexe ungerader Ordnung,Comment. Math. Helv. 10, 1938, pages 275–287. ↑ (en) Bela Bollobas - Extremal Graph Theory [archive], Dover, 2004. ↑ (en) Claude Berge - Some classes of perfect graphs, dans Six papers on Graph Theory,Indian. Statistical Institute, Calculatta, pages 1-21, 1969. ↑ (fr) Claude Berge - Graphes et hypergraphes, Dunod, 1970. ↑ (fr) Claude Berge - Théorie des graphes et ses applications, Dunod, 1958. C - Probabilités ↑ (en) Anatol Rapoport - Contribution to the theory of random and biased nets, Bulletin of Mathematical Biology, vol. 19, no. 4, 1957. ↑ (en) Paul Erdős et Alfréd Rényi - On random graphs, Publicationes Mathematicae 6, 1959. Voir également des mêmes auteurs : On the evolution of random graphs, Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5, 1960. ↑ (en) Rick Durrett - Random Graph Dynamics [archive], Cambridge Series in Statistical and Probabilistic Mathematics, chapitre 1, 2006. ↑ (en) A. V. Lapshin - The property of phase transitions in random graphs, Probabilistic Methods in Discrete Mathematics: Proceedings of the Third International Petrozavodsk Conference, Petrozavodsk, Russia, May 12-15, 1992. ↑ (en) Bela Bollobas et Oliver Riordan - Percolation, Cambridge University Press, 2006. Cet ouvrage présente la théorie de la percolation avec une approche inspirée de la théorie des graphes. ↑ (en) Harry Kesten - What is percolation? Notices of the Americal Mathematical Society, 53(5), 2006. ↑ (en) Takashi Hara et Gordon Slade - Mean-field critical behaviour for percolation in high dimensions, Commun. Math. Phys. 128, 1990. ↑ (en) Albert-Laszlo Barabasi et Reka Albert - Emergence of scaling in random networks,Science, 286, 1999. ↑ (en) Philippe Giabbanelli - Self-improving immunization policies for epidemics over complex networks, thèse de master, Université Simon Fraser, 2009, sous la direction de Joseph G. Peters. ↑ (en) Michael Molloy et Bruce A. Reed - A critical point for random graphs with a given degree sequence [archive], Random Struct. Algorithms, 6(2/3), pages 161–180, 1995. ↑ (en) Xiafeng Li, Derek Leonard et Dmitri Loguinov - On Reshaping of Clustering Coefficients in Degree-Based Topology Generators [archive], Algorithms and Models for the Web-Graph, Springer Berlin, pages 68-79, 2004.

B - Flots ↑ (en) V.V. Ostapenko et A. P. Yakovleva - Mathematical questions of modeling and control in water distribution problems, Control Cybern., 20, No. 4, 1991, pages 99-111. ↑ (en) Kevin Wayne - Diaporama présentant l'équivalence entre la coupe minimale et le flot maximal [archive]. Support d'étude pour le livre Algorithm Design [archive] de Jon Kleinberg et Éva Tardos, Addison Wesley, 2005. ↑ (en) John W. Chinneck - Practical optimization: a gentle introduction [archive], chapitre 10, 2001 D - Représentations ↑ (fr) J-C. Bermond, P. Fraigniaud, A. Germa, M-C. Heydemann, E. Lazard, P. Michallon, A. Raspaud, D. Sotteau, M. Syska et D. Trystram - Communications dans les réseaux de processeurs,Masson, 1994, (ISBN 2225844100). Paru sous le pseudonyme Jean de Rumeur. ↑ (en) Pavol Hell et Jaroslav Nesetril - Graphs and Homomorphisms, Oxford University Press, 2004,(ISBN 0198528175). ↑ (en)Fan R. K. Chung - Spectral Graph Theory, Regional Conference Series in Mathematics, numéro 92, publié par l'American Mathematical Society, 1997. ↑ (en) Neil Robertson et Paul D. Seymour - Graph Minors II Algorithmic Aspects of Tree-Width,Journal of Algorithms, volume 7 numéro 3, 1983. ↑ (en) S. Arnborg, D.G. Corneil et A. Proskurowski - Complexity of finding embedding in a k-tree.SIAM Journal on Discrete Mathematics, volume 8, pages 277-284, 1987. ↑ (en) Hans L. Bodlaender - A linear time algorithm for finding tree-decomposition of small treewidth,SIAM journal on Computing, volume 25, pages 1305-1317, 1996. ↑ (en) Paul D. Seymour et R. Thomas - Call routing and the ratcatcher, Combinatorica, volume 14, numéro 2, pages 217-241, 1994 ↑ (en) Q.P. Gu et H. Tamaki, Optimal branch decomposition of planar graphs in O(n3) time,proceedings of the 32nd International Colloquium on Automata, Languages, and Programming, Springer-Verlag LNCS 3580, pages 373-384, 2005. ↑ Pour les notations et techniques, voir (en) Qianping Gu - Tree/Branch Decompositions and Their Applications [archive], notes de cours à l'Université Simon Fraser. E - Aspect algorithmique ↑ [pdf] (en) Elias Dahlhaus, Jens Gustedt et Ross M. McConnell - Partially complemented representations of digraphs [archive], Discrete Mathematics and Theoretical Computer Science, volume 5, numéro 1, pages 147-168, 2002. ↑ (en) Stephen Alstrup et Theis Rauhe - Small Induced-Universal Graphs and Compact Implicit Graph Representations, Proceedings of the 43rd annual IEEE Symposium on Foundations of Computer Science, pages 53-62, 2002. ↑ (en) Sampath Kannan, Moni Naor, et Steven Rudich - Implicit Representation of Graphs, SIAM J. on Discrete Math., volume 5, pages 596-603, 1992. ↑ (en) Cyril Gavoille, David Peleg, Stéphane Pérennes et Ran Razb - Distance labeling in graphs,Journal of Algorithms, volume 53, pages 85-112, 2004.

•  Portail de l'informatique théorique

Catégories : Théorie des graphes | Optimisation combinatoire | [+]