En théorie des graphes, le problème de couverture minimum par sous-graphes bipartis complets (ou problème de couverture biclique) est un problème algorithmique qui consiste, étant donné un graphe, à trouver une famille minimale de sous-graphes bipartis complets couvrant ses arêtes, c'est-à-dire telle que chaque arête du graphe d'origine apparaisse dans au moins un sous-graphe de la couverture.
Le problème de décision associé au problème d'optimisation de couverture par au plus sous-graphes bipartis complets est NP-complet, et ce même si l'on se restreint à la couverture de graphes bipartisM.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman. 1983. ..
Couverture par sous-graphes bipartis complets
Définition Une couverture par sous-graphes bipartis complets d'un graphe est un ensemble de sous-graphes bipartis complets de tel que pour toute arête de , il existe un entier tel que (ces sous-graphes ne sont pas nécessairement deux à deux disjoints).
Propriétés combinatoires Nombre minimal de sous-graphes couvrants
Étant donné un graphe , on note le nombre minimum de graphes bipartis complets couvrant les arêtes de (aussi appelé dimension bipartie). Pour un entier naturel , si est un graphe à sommets, on a , car on obtient une couverture à au plus sous-graphes bipartis complets en prenant les sous graphes étoiles de .
On peut donc noter la valeur maximale des , où est un graphe à sommets. Les premières valeurs de sont données par le tableau suivant (on observe bien que est majoré par :
2 3 4 5 6 7 8 9 10 1 2 2 3 4 5 5 6 7
On peut obtenir les premières valeurs de en étudiant systématiquement les graphes à sommets. Pour plus grand, on peut utiliser les propriétés suivantes :
Si est un graphe possédant deux sous-graphes de sommets disjoints et , reliés par au plus une arête, alors : Si , alors En particulier, si pour un certain et , , alors pour tout entier , , et donc . Ce comportement et les premières valeurs de amènent à conjecturer que , ce qui est en fait vrai.
Plus précisément, il a été démontré par Zsolt Tuza que l'on avait : .
Nombre minimal de sommets couverts Pour un graphe , on note la valeur minimale de , où est une couverture biclique de . En d'autres termes, désigne le nombre minimal de sommets d'une couverture biclique de , comptés avec multiplicités. Si est un entier fixé, on note la valeur maximale de pour les graphes à sommets. Zsolt Tuza a donné une minoration optimale de la valeur de :
Partition en graphes bipartis complets
Définition Une partition par sous-graphes bipartis complets est une couverture par sous-graphes bipartis complets où l'on impose que tous les sous-graphes soient disjoints.
Propriétés combinatoires
Théorème de Graham-Pollak
Nombre minimal de sommets couverts De la même manière que pour la couverture biclique, on peut définir le nombre minimal de sommets d'une partition biclique d'un graphe , toujours comptés avec multiplicités. Pour un entier fixé, on note la valeur maximale de pour les graphes à sommets. Un premier résultat démontré par Fan Chung, Paul Erdős et J. Spencer donne un encadrement des valeurs de et :
Ce résultat montre en particulier que la minoration de trouvée par Zsolt Tuza est bien optimale. Il a ensuite été démontré par Paul Erdős et László Pyber qu'il existe une constante telle que pour tout entier suffisamment grand, tout graphe à sommets admet une partition biclique pour laquelle tout sommet de est contenu dans au plus sous-graphes de la partition.
Articles connexes Graphe biparti complet Théorème de Graham-Pollak Dimension bipartie Liste de problèmes NP-complets
Références
Catégorie:Théorie des graphes