vignette|Un graphe avec un nombre d'intersection de quatre. Les quatre zones grisées indiquent quatre cliques qui recouvrent toutes les arêtes du graphe. Dans une représentation par intersection, chaque sommet peut être représenté par le sous-ensemble des cliques auquel il appartient. En théorie des graphes, le nombre d'intersection d'un graphe est le nombre minimal d'éléments nécessaires pour représenter sous forme de graphe d'intersection d'ensembles finis. Dans cette représentation, chaque sommet correspond à un ensemble et deux sommets sont reliés par une arête dès que leurs ensembles ont un élément commun. Le nombre d'intersection est aussi égal au nombre minimal de cliques (sous-graphes dont les arêtes relient toutes les paires de sommets) nécessaires pour recouvrir toutes les arêtes du graphe . Ce nombre, et le problème associé consistant à le calculer, ont été étudiés sous de nombreux noms alternatifs.
Les applications du nombre d'intersection comprennent l'ordonnancement des opérations sur des ordinateurs à très longs mots d'instruction (Very long instruction word), l'allocation de bande passante dans les réseaux à fibres optiques, la visualisation de données à l'aide d'écrans à lettres compacts, l'analyse des réseaux trophiques en biologie et l'inférence des complexes protéiques à partir des réseaux d'interaction protéine-protéine.
Un graphe avec sommets et arêtes a un nombre d'intersection majoré par . Calculer ou approximer le nombre d'intersection est un problème NP-difficile, mais traitable avec un paramètre fixe.
Terminologie Les deux formulations équivalentes du nombre d'intersection, en termes de graphes d'intersection ou en termes de cliques qui recouvrent toutes les arêtes, ont été à l'origine de multiples noms pour ce concept et pour le problème informatique de la recherche d'un graphe d'intersection ou d'une couverture par cliques.
Un ensemble de cliques recouvrant toutes les arêtes d'un graphe est appelé Couverture d'arêtes par cliques ou simplement Couverture par cliques, bien que ce dernier terme soit ambigu : une couverture de cliques peut également désigner un ensemble de cliques recouvrant tous les sommets du graphe . Parfois, le terme « recouvrement » est utilisé à la place de « couverture » . Le nombre d'intersection est aussi parfois appelé Nombre de couverture d'arêtes par cliques ou Nombre de couverture de cliques .
Le problème du calcul du nombre d'intersection a été appelé le problème du nombre d'intersection, le problème de la base du graphe d'intersection , la couverture par cliques, le problème de la couverture d'arêtes par des cliques , et (en raison de l'une de ses premières applications) le problème du conflit de mots clés.
Définitions
Graphes d'intersection Soit être une famille d'ensembles. Le graphe d'intersection de est un graphe non orienté qui possède un sommet pour chaque ensemble de et une arête entre chaque paire d'ensembles ayant une intersection non vide. Tout graphe peut être représenté comme un graphe d'intersection de cette manière.
Le nombre d'intersection d'un graphe est le plus petit nombre telle qu'il existe une représentation de ce type pour laquelle l'union des ensembles dans a éléments.
Couverture d'arêtes par cliques Le nombre d'intersection d'un graphe est aussi défini comme le plus petit nombre de cliques dans ( sous-graphes complets de ) qui recouvrent toutes les arêtes de . Un ensemble de cliques possédant cette propriété est appelé « couverture d'arêtes par cliques » et pour cette raison, le nombre d'intersection est aussi parfois appelé « nombre de couverture d'arêtes par cliques ».
Équivalence L'égalité du nombre d'intersections et du nombre de couvertures d'arêtes par cliques admet une démonstration concise.
D'une part, supposons que soit le graphe d'intersection d'une famille d'ensembles dont l'union a éléments. Pour chaque élément , les ensembles dans qui contiennent forment une clique dans , car ces ensembles possède (deux à deux) une intersection non vide contenant . De plus, les cliques ainsi formées recouvrent chaque arête dans : si deux ensembles dans ont une intersection non vide alors il existe une arête entre ces deux ensembles et cette arête est contenue dans la clique pour chaque élément qui appartient à leur intersection. Par conséquent, les arêtes de peut être couvert par cliques, une par élément de .
Réciproquement, si les arêtes du graphe peuvent être couvertes par cliques, alors chaque sommet de peut être représenté par l'ensemble des cliques de cette couverture qui contiennent . Deux de ces ensembles de cliques, pour deux sommets et , ont une intersection non vide si et seulement s'il existe une clique dans la couverture qui contient à la fois et . Si cette clique contenant et existe, alors elle contient également l'arête , qui est une arête de . Inversement, si est une arête dans , alors elle est couverte par une clique ; cette clique contient à la fois et , elle appartient donc à l'intersection des ensembles de cliques qui représentent et . Par conséquent, une couverture par des cliques conduit à une représentation d'intersection avec éléments.
Applications La représentation abstraite d'un graphe comme un graphe d'intersection d'ensembles peut être utilisée pour construire des représentations géométriques d'intersection plus concrètes de ce même graphe. En particulier, si un graphe possède un nombre d'intersection , il peut être représenté comme un graphe d'intersection de hypersphères unitaires de dimension n. La dimension minimale des hypersphères dans une telle représentation est appelée sphéricité d'un graphe, de sorte que la sphéricité est inférieure ou égale au nombre d'intersection.
Un recouvrement par cliques peut servir de schéma d'étiquetage d'adjacence pour un graphe. Chaque sommet est étiqueté par une valeur binaire, permettant de tester rapidement l'existence d'une arête entre deux sommets en comparant leurs valeurs. Ces étiquettes comportent un bit par clique : zéro si le sommet n'appartient pas à la clique, un s'il y appartient. Avec ce schéma, deux sommets sont adjacents si et seulement si la valeur binaire de leurs étiquettes est non nulle. La longueur des étiquettes correspond au nombre d'intersection du graphe. Lorsque cette longueur est faible, une représentation informatique du graphe utilisant uniquement ces étiquettes consomme moins de mémoire que les méthodes explicites telles que les listes d'adjacence et permet des tests d'adjacence plus rapides. Cette méthode a été utilisée par E. Kellerman d'IBM dans une des premières applications des nombres d'intersection, pour étiqueter un ensemble de mots-clés et détecter rapidement les conflits. C’est pourquoi le problème du calcul des nombres d’intersection est également appelé problème de conflit de mots-clés. De même, en géométrie algorithmique, les représentations basées sur le nombre d’intersection ont été considérées comme une représentation compacte pour les graphes de visibilité, bien qu’il existe des entrées géométriques pour lesquelles cette représentation nécessite un nombre de cliques quasi quadratique.
Bornes supérieures Tout graphe ayant arêtes a un nombre d'intersection majoré par . Cela découle de l'observation que chaque arête est elle-même une clique à deux sommets. Il y a de ces cliques, et ensemble elles recouvrent tous les bords, formant ainsi une couverture d'arêtes par cliques de taille .
En outre, tout graphe ayant sommets a un nombre d'intersection majoré par . Un résultat plus fort est que les arêtes d'un graphe à sommets peut être couvert par au plus cliques, chacune étant soit une arête simple, soit un triangle. Un algorithme glouton peut trouver cette couverture en supprimant deux sommets adjacents et en s'appelant récursivement sur le graphe restant. Après avoir rétabli les deux sommets supprimés, l'algorithme ajoute à la couverture chaque triangle auquel ils appartiennent, ce qui couvre toutes les arêtes les reliant à des voisins communs. Toutes les arêtes restantes reliant l'un des deux sommets supprimés à un de leurs voisins, sans former de triangle, sont couvertes par des cliques de deux sommets. S'il n'y a pas de triangle contenant les deux sommets supprimés, l'arête entre eux est également couverte par une clique de deux sommets. Par hypothèse de récurrence, la couverture du graphe après suppression des deux sommets comporte au plus cliques. Les deux sommets supprimés appartiennent à au plus autres cliques, il y a égalité lorsque tous les autres sommets sont des voisins non partagés et que l'arête entre les deux sommets doit être utilisée comme clique. L'addition de ces deux quantités donne cliques au total. Ceci généralise le théorème de Mantel selon lequel un graphe sans triangle possède au plus arêtes, car dans un graphe sans triangle, la seule couverture optimale d'arêtes par cliques a une clique par arête et donc le nombre d'intersections est égal au nombre d'arêtes.
Une borne encore plus précise est possible lorsque le nombre d'arêtes est strictement supérieur à . On note le nombre de paires de sommets non reliés par une arête dans un graphe donné et l'unique entier pour lequel . Alors le nombre d'intersection de est au plus . Les graphes qui sont complémentaires d'un graphe creux ont de petits nombres d'intersection : le nombre d'intersection de tout graphe à sommets est au plus , où est la base du logarithme naturel et est le degré maximal du graphe complémentaire de .
Il ressort des résultats sur la structure des graphes sans étoile que, lorsqu'un graphe sans étoile connexe à sommets possède au moins trois sommets indépendants, il a un nombre d'intersection inférieur ou égal à . Il reste à déterminer si cela est vrai pour tous les graphes sans étoile sans qu'ils possèdent nécessairement de grands ensembles indépendants. Les graphes adjoints (line graph), qui représentent les arêtes et les paires d'arêtes tangentes d'un autre graphe , constituent une sous-classe importante des graphes sans étoile. Une couverture optimale de cliques d'un graphe adjoint peut être formé avec une clique pour chaque triangle dans qui possède deux ou trois sommets de degré 2, et une clique pour chaque sommet de degré au moins deux qui n'est pas un sommet de degré deux de l'un de ces triangles. Le nombre d'intersection est le nombre de cliques de ces deux types.
Dans le modèle Erdős – Rényi – Gilbert de graphes aléatoires, dans lequel tous les graphes à sommets étiquetés sont équiprobables (ou, de manière équivalente, chaque arête est présente ou absente, indépendamment des autres arêtes, avec une probabilité ), le numéro d'intersection d'un graphe aléatoire à n sommets est, avec une forte probabilité à un facteur constant près, de Cette valeur est plus petite d'un facteur de que le nombre d'arêtes. Dans ces graphes, les cliques maximales possèdent (avec une forte probabilité) un nombre logarithmique de sommets, ce qui implique qu'il en faut autant pour couvrir toutes les arêtes. L'autre sens de la borne consiste à prouver qu'il est possible de trouver suffisamment de cliques de taille logarithmique pour couvrir la plupart des arêtes, les arêtes restantes pouvant être couvertes par des cliques à deux sommets.
Les premières recherches sur les nombres d'intersection consistaient en grande partie à calculer ce nombre pour divers graphes spécifiques, tels que les graphes formés en supprimant un sous-graphe complet ou bine en supprimant un couplage parfait d'un graphe complet plus grand.
Complexité Tester si un graphe a un nombre d'intersection inférieur ou égale à est un problème NP-complet. Par conséquent, calculer le nombre d'intersection d'un graphe donné est également NP-difficile. La difficulté du calcul du nombre d'intersections a été utilisée pour prouver que reconnaître les carrés des graphes scindés est NP-complet.