Couverture par sous-graphes bipartis complets
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Bipartite-dimension-biclique-cover.svg/220px-Bipartite-dimension-biclique-cover.svg.png)
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[1], 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 bipartis[2].
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/02/Exemples_de_couvertures_bicliques_extr%C3%AAmales.svg/220px-Exemples_de_couvertures_bicliques_extr%C3%AAmales.svg.png)
On remarque que dans le graphe de gauche, les sous-graphes ne sont pas disjoints.
É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 [3], car on obtient une couverture à au plus sous-graphes bipartis complets en prenant les sous graphes étoiles[4] 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 :
n | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|
b(n) | 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.
Théorème[3] — Pour un nombre entier naturel , le nombre est équivalent, lorsque tend vers , à . Soit :
Plus précisément, il a été démontré[5] 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[5] de la valeur de :
Théorème — Il existe une constante telle que pour tout entier suffisamment grand :
Et cette minoration est optimale, à la constante près.
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
Théorème de Graham-Pollak — Un graphe complet à sommets ne peut être partitionné en moins de graphes bipartis complets.
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 :
Théorème[1] — Pour tout réel et pour tout entier suffisamment grand :
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[6] 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
- ↑ a et b (en) F. R. K. Chung, P. Erdős et J. Spencer, « On the decomposition of graphs into complete bipartite subgraphs », dans Studies in Pure Mathematics: To the Memory of Paul Turán, Birkhäuser, (ISBN 978-3-0348-5438-2, DOI 10.1007/978-3-0348-5438-2_10, lire en ligne), p. 95–101
- ↑ M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman. 1983. (ISBN 0-7167-1045-5).
- ↑ a et b Jean-Claude Bermond, « Couverture des arêtes d'un graphe par des graphes bipartis complets », [Rapport de recherche] 10, LRI - CNRS, University Paris-Sud, (lire en ligne)
- ↑ Martin Aigner et Günter M. Ziegler, Proofs from THE BOOK, Springer, , 6e éd. (ISBN 978-3-662-57265-8, DOI 10.1007/978-3-662-57265-8), p. 79–80
- ↑ a et b (en) Zsolt Tuza, « Covering of graphs by complete bipartite subgraphs; Complexity of 0–1 matrices », Combinatorica, vol. 4, no 1, , p. 111–116 (ISSN 1439-6912, DOI 10.1007/BF02579163, lire en ligne, consulté le )
- ↑ (en) « Covering a graph by complete bipartite graphs », Discrete Mathematics, vol. 170, nos 1-3, , p. 249–251 (ISSN 0012-365X, DOI 10.1016/S0012-365X(96)00124-0, lire en ligne, consulté le )
Portail de l'informatique théorique