Graphique implicite

Dans l'étude des algorithmes graphiques , une représentation graphique implicite (ou plus simplement graphe implicite ) est un graphe dont les sommets ou les arêtes ne sont pas représentés comme des objets explicites dans la mémoire d'un ordinateur, mais sont plutôt déterminés algorithmiquement à partir d'une autre entrée, par exemple une fonction calculable .

La notion de graphe implicite est courante dans divers algorithmes de recherche qui sont décrits en termes de graphes. Dans ce contexte, un graphe implicite peut être défini comme un ensemble de règles pour définir tous les voisins de tout sommet spécifié. Ce type de représentation de graphe implicite est analogue à une liste d'adjacence , dans la mesure où il fournit un accès facile aux voisins de chaque sommet. Par exemple, dans la recherche d'une solution à un puzzle tel que le Rubik's Cube , on peut définir un graphe implicite dans lequel chaque sommet représente l'un des états possibles du cube, et chaque arête représente un déplacement d'un état à un autre. Il est simple de générer les voisins de n'importe quel sommet en essayant tous les déplacements possibles du puzzle et en déterminant les états atteints par chacun de ces déplacements ; cependant, une représentation implicite est nécessaire, car l'espace d'état du Rubik's Cube est trop grand pour permettre à un algorithme de lister tous ses états.

En théorie de la complexité computationnelle , plusieurs classes de complexité ont été définies en relation avec les graphes implicites, définis comme ci-dessus par une règle ou un algorithme permettant de lister les voisins d'un sommet. Par exemple, PPA est la classe de problèmes dans laquelle on donne en entrée un graphe implicite non orienté (dans lequel les sommets sont des chaînes binaires de n bits, avec un algorithme en temps polynomial pour lister les voisins de tout sommet) et un sommet de degré impair dans le graphe, et on doit trouver un deuxième sommet de degré impair. Par le lemme de la poignée de main , un tel sommet existe ; en trouver un est un problème dans NP , mais les problèmes qui peuvent être définis de cette manière ne sont pas nécessairement NP-complets , car on ne sait pas si PPA = NP. PPAD est une classe analogue définie sur les graphes implicites orientés qui a attiré l'attention dans la théorie algorithmique des jeux car elle contient le problème du calcul d'un équilibre de Nash . Le problème de tester l'accessibilité d'un sommet à un autre dans un graphe implicite peut également être utilisé pour caractériser les classes de complexité non déterministes limitées par l'espace, notamment NL (la classe de problèmes qui peuvent être caractérisés par l'accessibilité dans les graphes implicites orientés dont les sommets sont des chaînes de bits de O(log n ) bits), SL (la classe analogue pour les graphes non orientés) et PSPACE (la classe de problèmes qui peuvent être caractérisés par l'accessibilité dans les graphes implicites avec des chaînes de bits de longueur polynomiale). Dans ce contexte de théorie de la complexité, les sommets d'un graphe implicite peuvent représenter les états d'une machine de Turing non déterministe , et les arêtes peuvent représenter des transitions d'état possibles, mais les graphes implicites peuvent également être utilisés pour représenter de nombreux autres types de structures combinatoires. PLS , une autre classe de complexité, capture la complexité de la recherche d'optima locaux dans un graphe implicite.

Les modèles de graphes implicites ont également été utilisés comme une forme de relativisation afin de prouver des séparations entre classes de complexité plus fortes que les séparations connues pour les modèles non relativisés. Par exemple, Childs et al. ont utilisé des représentations de voisinage de graphes implicites pour définir un problème de parcours de graphe qui peut être résolu en temps polynomial sur un ordinateur quantique mais qui nécessite un temps exponentiel pour être résolu sur n'importe quel ordinateur classique.

Dans le contexte des représentations efficaces de graphes, JH Muller a défini une structure locale ou un schéma d'étiquetage d'adjacence pour un graphe G dans une famille F donnée de graphes comme étant une affectation d'un identifiant O (log n ) bits à chaque sommet de G , ainsi qu'un algorithme (qui peut dépendre de F mais est indépendant du graphe individuel G ) qui prend en entrée deux identifiants de sommet et détermine s'ils sont ou non les extrémités d'une arête dans G . Autrement dit, ce type de représentation implicite est analogue à une matrice d'adjacence : il est simple de vérifier si deux sommets sont adjacents, mais trouver les voisins de n'importe quel sommet peut impliquer de parcourir tous les sommets et de tester lesquels sont voisins.

Les familles de graphes avec des schémas d’étiquetage d’adjacence incluent :

Graphiques à degrés délimités

Si chaque sommet de G a au plus d voisins, on peut numéroter les sommets de G de 1 à n et laisser l'identifiant d'un sommet être le ( d + 1) -uplet de son propre numéro et des numéros de ses voisins. Deux sommets sont adjacents lorsque les premiers numéros de leurs identifiants apparaissent plus tard dans l'identifiant de l'autre sommet. Plus généralement, la même approche peut être utilisée pour fournir une représentation implicite des graphes à arboricité bornée ou à dégénérescence bornée , y compris les graphes planaires et les graphes de toute famille de graphes mineurs fermés .

Graphiques d'intersection

Un graphe d'intervalle est le graphe d'intersection d'un ensemble de segments de droite dans la droite réelle . On peut lui donner un schéma d'étiquetage d'adjacence dans lequel les points qui sont les extrémités des segments de droite sont numérotés de 1 à 2 n et chaque sommet du graphe est représenté par les numéros des deux extrémités de son intervalle correspondant. Avec cette représentation, on peut vérifier si deux sommets sont adjacents en comparant les nombres qui les représentent et en vérifiant que ces nombres définissent des intervalles qui se chevauchent. La même approche fonctionne pour d'autres graphes d'intersection géométriques, y compris les graphes de boxicité bornée et les graphes circulaires , et les sous-familles de ces familles telles que les graphes héréditaires de distance et les cographes . Cependant, une représentation de graphe d'intersection géométrique n'implique pas toujours l'existence d'un schéma d'étiquetage d'adjacence, car elle peut nécessiter plus qu'un nombre logarithmique de bits pour spécifier chaque objet géométrique. Par exemple, représenter un graphe sous forme de graphe de disque unitaire peut nécessiter un nombre exponentiel de bits pour les coordonnées des centres de disque.

Graphiques de comparabilité à faible dimension

Le graphe de comparabilité d'un ensemble partiellement ordonné comporte un sommet pour chaque élément de l'ensemble et une arête entre deux éléments de l'ensemble qui sont liés par l'ordre partiel. La dimension d'ordre d'un ordre partiel est le nombre minimum d'ordres linéaires dont l'intersection est l'ordre partiel donné. Si un ordre partiel a une dimension d'ordre bornée, alors un schéma d'étiquetage d'adjacence pour les sommets de son graphe de comparabilité peut être défini en étiquetant chaque sommet avec sa position dans chacun des ordres linéaires de définition, et en déterminant que deux sommets sont adjacents si chaque paire de nombres correspondante dans leurs étiquettes a la même relation d'ordre que chaque autre paire. En particulier, cela permet un schéma d'étiquetage d'adjacence pour les graphes de comparabilité chordaux , qui proviennent d'ordres partiels de dimension au plus quatre.

Toutes les familles de graphes n'ont pas de structures locales. Pour certaines familles, un simple argument de comptage prouve que les schémas d'étiquetage d'adjacence n'existent pas : seuls O(nlogn ) ^bits peuvent être utilisés pour représenter ^un graphe entier, donc une représentation de ce type ne peut exister que lorsque le nombre de graphes à n sommets dans la famille donnée F est au plus égal à 2 ^{O ( nlogn )} . Les familles de graphes qui ont un nombre de graphes plus grand que cela, comme les graphes bipartis ou les graphes sans triangles , n'ont pas de schémas d'étiquetage d'adjacence. Cependant, même les familles de graphes dans lesquelles le nombre de graphes dans la famille est petit peuvent ne pas avoir de schéma d'étiquetage d'adjacence ; par exemple, la famille de graphes avec moins d'arêtes que de sommets a 2 ^{O ( nlogn )} n graphes à n ^{sommets mais n'a pas de schéma d'étiquetage d'adjacence, car on pourrait transformer n'importe quel graphe donné en un graphe plus grand dans cette famille en} ajoutant un nouveau sommet isolé pour chaque arête, sans changer son étiquetage. Kannan et al. ont demandé si le fait d'avoir une caractérisation de sous-graphe interdit et d'avoir au plus 2 graphes ^{O ( n log n )} n -sommets suffisent à garantir l'existence d'un schéma d'étiquetage d'adjacence ; cette question, que Spinrad a reformulée sous forme de conjecture, reste ouverte. Parmi les familles de graphes qui satisfont les conditions de la conjecture et pour lesquelles il n'existe pas de schéma d'étiquetage d'adjacence connu figurent la famille des graphes de disques et des graphes d'intersection de segments de droite.

Si une famille de graphes F possède un schéma d'étiquetage d'adjacence, alors les graphes à n sommets de F peuvent être représentés comme des sous-graphes induits d'un graphe universel induit commun de taille polynomiale, le graphe étant constitué de tous les identifiants de sommets possibles. Inversement, si un graphe universel induit de ce type peut être construit, alors les identités de ses sommets peuvent être utilisées comme étiquettes dans un schéma d'étiquetage d'adjacence. Pour cette application de représentations de graphes implicites, il est important que les étiquettes utilisent le moins de bits possible, car le nombre de bits dans les étiquettes se traduit directement par le nombre de sommets dans le graphe universel induit. Alstrup et Rauhe ont montré que tout arbre possède un schéma d'étiquetage d'adjacence avec log ₂ n + O ( log * n ) bits par étiquette, d'où il résulte que tout graphe d' arboricité k possède un schéma avec k log ₂ n + O ( log * n ) bits par étiquette et un graphe universel avec n ^k 2 ^{O ( log * n )} sommets. En particulier, les graphes planaires ont une arboricité d'au plus trois, ils ont donc des graphes universels avec un nombre de sommets presque cubique. Cette limite a été améliorée par Gavoille et Labourel qui ont montré que les graphes planaires et les familles de graphes mineurs fermés ont un schéma d'étiquetage avec 2 log ₂ n + O (log log n ) bits par étiquette, et que les graphes de largeur arborescente bornée ont un schéma d'étiquetage avec log ₂ n + O (log log n ) bits par étiquette. La limite pour les graphes planaires a été améliorée à nouveau par Bonamy, Gavoille et Piliczuk qui ont montré que les graphes planaires ont un schéma d'étiquetage avec (4/3+o(1))log ₂ n bits par étiquette. Enfin, Dujmović et al ont montré que les graphes planaires ont un schéma d'étiquetage avec (1+o(1))log ₂ n bits par étiquette donnant un graphe universel avec n ^1+o(1) sommets.

La conjecture d'Aanderaa-Karp-Rosenberg concerne les graphes implicites donnés comme un ensemble de sommets étiquetés avec une règle de boîte noire pour déterminer si deux sommets sont adjacents. Cette définition diffère d'un schéma d'étiquetage d'adjacence dans la mesure où la règle peut être spécifique à un graphe particulier plutôt que d'être une règle générique qui s'applique à tous les graphes d'une famille. En raison de cette différence, chaque graphe a une représentation implicite. Par exemple, la règle pourrait consister à rechercher la paire de sommets dans une matrice d'adjacence distincte. Cependant, un algorithme qui reçoit en entrée un graphe implicite de ce type doit opérer sur celui-ci uniquement via le test d'adjacence implicite, sans référence à la manière dont le test est implémenté.

Une propriété de graphe est la question de savoir si un graphe appartient à une famille donnée de graphes ; la réponse doit rester invariante sous tout réétiquetage des sommets. Dans ce contexte, la question à déterminer est de savoir combien de paires de sommets doivent être testées pour l'adjacence, dans le pire des cas, avant que la propriété d'intérêt puisse être déterminée comme vraie ou fausse pour un graphe implicite donné. Rivest et Vuillemin ont prouvé que tout algorithme déterministe pour toute propriété de graphe non triviale doit tester un nombre quadratique de paires de sommets. La conjecture complète d'Aanderaa–Karp–Rosenberg est que tout algorithme déterministe pour une propriété de graphe monotone (une propriété qui reste vraie si plus d'arêtes sont ajoutées à un graphe avec la propriété) doit dans certains cas tester chaque paire de sommets possible. Plusieurs cas de la conjecture se sont avérés vrais - par exemple, on sait qu'elle est vraie pour les graphes avec un nombre premier de sommets - mais la conjecture complète reste ouverte. Des variantes du problème pour les algorithmes randomisés et les algorithmes quantiques ont également été étudiées.

Bender et Ron ont montré que, dans le même modèle utilisé pour la conjecture d'évasion, il est possible en un temps constant de distinguer les graphes acycliques orientés des graphes qui sont très loin d'être acycliques. En revanche, un temps aussi rapide n'est pas possible dans les modèles de graphes implicites basés sur le voisinage,