Graphique de complément

Dans le domaine mathématique de la théorie des graphes , le complément ou l'inverse d'un graphe G est un graphe H sur les mêmes sommets tel que deux sommets distincts de H sont adjacents si et seulement s'ils ne sont pas adjacents dans G. Autrement dit, pour générer le complément d'un graphe, on remplit toutes les arêtes manquantes nécessaires pour former un graphe complet , et on supprime toutes les arêtes qui s'y trouvaient auparavant.

Le complément n'est pas le complément d'ensemble du graphe ; seules les arêtes sont complémentées.

Soit G = ( V , E ) un graphe simple et soit K constitué de tous les sous-ensembles à 2 éléments de V . Alors H = ( V , K \ E ) est le complément de G , où K \ E est le complément relatif de E dans K . Pour les graphes orientés , le complément peut être défini de la même manière, comme un graphe orienté sur le même ensemble de sommets, en utilisant l'ensemble de toutes les paires ordonnées à 2 éléments de V à la place de l'ensemble K dans la formule ci-dessus. En termes de matrice d'adjacence A du graphe, si Q est la matrice d'adjacence du graphe complet du même nombre de sommets (c'est-à-dire que toutes les entrées sont égales à un sauf les entrées diagonales qui sont nulles), alors la matrice d'adjacence du complément de A est QA .

Le complément n'est pas défini pour les graphes multigraphes . Dans les graphes qui autorisent les boucles automatiques (mais pas les adjacences multiples), le complément de G peut être défini en ajoutant une boucle automatique à chaque sommet qui n'en a pas dans G , et sinon en utilisant la même formule que ci-dessus. Cette opération est cependant différente de celle des graphes simples, car l'appliquer à un graphe sans boucles automatiques donnerait lieu à un graphe avec des boucles automatiques sur tous les sommets.

Plusieurs concepts de la théorie des graphes sont liés les uns aux autres via la complémentation :

• Le complémentaire d'un graphe sans arête est un graphe complet et vice versa.
• Tout sous-graphe induit du graphe complémentaire d'un graphe G est le complémentaire du sous-graphe induit correspondant dans G .
• Un ensemble indépendant dans un graphe est une clique dans le graphe complémentaire et vice versa. Il s'agit d'un cas particulier des deux propriétés précédentes, car un ensemble indépendant est un sous-graphe induit sans arête et une clique est un sous-graphe induit complet.
• Le groupe d' automorphismes d'un graphe est le groupe d'automorphismes de son complémentaire.
• Le complémentaire de tout graphe sans triangle est un graphe sans griffes , bien que l'inverse ne soit pas vrai.

Un graphe auto-complémentaire est un graphe isomorphe à son propre complément. graphe de chemin à quatre sommets et le graphe de cycle à cinq sommets . Il n'existe aucune caractérisation connue des graphes auto-complémentaires.

Plusieurs classes de graphes sont auto-complémentaires, dans le sens où le complémentaire de tout graphe d'une de ces classes est un autre graphe de la même classe.

• Les graphes parfaits sont les graphes dans lesquels, pour chaque sous-graphe induit, le nombre chromatique est égal à la taille de la clique maximale. Le fait que le complément d'un graphe parfait soit également parfait est le théorème du graphe parfait de László Lovász .
• Les cographes sont définis comme des graphes qui peuvent être construits à partir de sommets simples par des opérations d'union et de complémentation disjointes . Ils forment une famille de graphes auto-complémentaires : le complément de tout cographe est un autre cographe différent. Pour les cographes de plus d'un sommet, exactement un graphe de chaque paire complémentaire est connexe, et une définition équivalente des cographes est que chacun de leurs sous-graphes induits connexe a un complément déconnecté. Une autre définition auto-complémentaire est qu'ils sont les graphes sans sous-graphe induit sous la forme d'un chemin à quatre sommets.
• Une autre classe de graphes auto-complémentaires est la classe des graphes fractionnés , les graphes dans lesquels les sommets peuvent être partitionnés en une clique et un ensemble indépendant. La même partition donne un ensemble indépendant et une clique dans le graphe complémentaire.
• Les graphes de seuil sont les graphes formés en ajoutant de manière répétée soit un sommet indépendant (sans voisins), soit un sommet universel (adjacent à tous les sommets précédemment ajoutés). Ces deux opérations sont complémentaires et génèrent une classe de graphes auto-complémentaires.

Dans l' analyse des algorithmes sur les graphes, la distinction entre un graphe et son complément est importante, car un graphe clairsemé (un graphe avec un petit nombre d'arêtes par rapport au nombre de paires de sommets) n'aura en général pas de complément clairsemé, et donc un algorithme qui prend un temps proportionnel au nombre d'arêtes sur un graphe donné peut prendre beaucoup plus de temps si le même algorithme est exécuté sur une représentation explicite du graphe complémentaire. Par conséquent, les chercheurs ont étudié des algorithmes qui effectuent des calculs graphiques standard sur le complément d'un graphe d'entrée, en utilisant une représentation graphique implicite qui ne nécessite pas la construction explicite du graphe complémentaire. En particulier, il est possible de simuler soit une recherche en profondeur d'abord , soit une recherche en largeur d'abord sur le graphe complémentaire, dans un laps de temps linéaire par rapport à la taille du graphe donné, même lorsque le graphe complémentaire peut avoir une taille beaucoup plus grande. Il est également possible d'utiliser ces simulations pour calculer d'autres propriétés concernant la connectivité du graphe complémentaire.