Couverture par sous-graphes bipartis complets

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.

Exemple de couverture d'un graphe biparti par quatre graphes bipartis complets (chaque couleur représente un sous-graphes).

Le problème de décision associé au problème d'optimisation de couverture par au plus $k$ sous-graphes bipartis complets est NP-complet, et ce même si l'on se restreint à la couverture de graphes bipartis.

Couverture par sous-graphes bipartis complets

Définition

Une couverture par sous-graphes bipartis complets d'un graphe $G=(V,E)$ est un ensemble $\lbrace G_{k}=(V_{k},E_{k})|1\leqslant k\leqslant n,V_{k}\subseteq V,E_{k}\subseteq E\rbrace$ de sous-graphes bipartis complets de $G$ tel que pour toute arête $e$ de $G$, il existe un entier $k\in [\![1,n]\!]$ tel que $e\in E_{k}$ (ces sous-graphes ne sont pas nécessairement deux à deux disjoints).

Propriétés combinatoires

Nombre minimal de sous-graphes couvrants

Exemples de graphes à respectivement 4 et 5 sommets où l'égalité $b(n)=b(G)$ est réalisée. Chaque couleur indique un sous-graphe biclique.
On remarque que dans le graphe de gauche, les sous-graphes ne sont pas disjoints.

Étant donné un graphe $G$, on note $b(G)$ le nombre minimum de graphes bipartis complets couvrant les arêtes de $G$ (aussi appelé dimension bipartie). Pour un entier naturel $n$, si $G$ est un graphe à $n$ sommets, on a $b(G)\leqslant n-1$, car on obtient une couverture à au plus $n-1$ sous-graphes bipartis complets en prenant les sous graphes étoiles de $G$.

On peut donc noter $b(n)$ la valeur maximale des $b(G)$, où $G$ est un graphe à $n$ sommets. Les $10$ premières valeurs de $b(n)$ sont données par le tableau suivant (on observe bien que $b(n)$ est majoré par $(n-1)$ :

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 $b(n)$ en étudiant systématiquement les graphes à $n$ sommets.
Pour $n$ plus grand, on peut utiliser les propriétés suivantes :

• $b(n)\leqslant b(n+1)\leqslant b(n)+1$
• Si $G$ est un graphe possédant deux sous-graphes de sommets disjoints $G_{1}$ et $G_{2}$, reliés par au plus une arête, alors : $b(G_{1})+b(G_{2})\leqslant b(G)$
  • Si $n_{1}+n_{2}=n$, alors $b(n_{1})+b(n_{2})\leqslant b(n)$
  • En particulier, si pour un certain $n\in \mathbb {N}$ et $a>0$, $b(n)=an$, alors pour tout entier $k$, $akn\leqslant b(kn)$, et donc $a\leqslant \lim _{n\to +\infty }{\frac {b(n)}{n}}$. Ce comportement et les premières valeurs de $b(n)$ amènent à conjecturer que $\lim _{n\to +\infty }{\frac {b(n)}{n}}=1$, ce qui est en fait vrai.

Théorème — Pour un nombre entier naturel $n$, le nombre $b(n)$ est équivalent, lorsque $n$ tend vers $+\infty$, à $n$. Soit :

$b(n){\underset {n\to +\infty }{\sim }}n$

Plus précisément, il a été démontré par Zsolt Tuza que l'on avait : $b(n)\leqslant n-[\log _{2}(n)]+1$.

Nombre minimal de sommets couverts

Pour un graphe $G$, on note $\beta (G)$ la valeur minimale de $\sum _{i=1}^{m}|V_{k}|$, où $G_{1}=(E_{1},V_{1}),\ldots ,G_{m}=(E_{m},V_{m})$ est une couverture biclique de $G$. En d'autres termes, $\beta (G)$ désigne le nombre minimal de sommets d'une couverture biclique de $G$, comptés avec multiplicités. Si $n$ est un entier fixé, on note $\beta (n)$ la valeur maximale de $\beta (G)$ pour les graphes à $n$ sommets. Zsolt Tuza a donné une minoration optimale de la valeur de $\beta (n)$ :

Théorème — Il existe une constante $c>0$ telle que pour tout entier $n$ suffisamment grand :

$c{\frac {n^{2}}{\log(n)}}<\beta (n)$

Et cette minoration est optimale, à la constante $c$ 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 à $n$ sommets ne peut être partitionné en moins de $n-1$ graphes bipartis complets.

Nombre minimal de sommets couverts

De la même manière que pour la couverture biclique, on peut définir $\alpha (G)$ le nombre minimal de sommets d'une partition biclique d'un graphe $G$, toujours comptés avec multiplicités. Pour un entier $n$ fixé, on note $\alpha (n)$ la valeur maximale de $\alpha (G)$ pour les graphes à $n$ sommets. Un premier résultat démontré par Fan Chung, Paul Erdős et J. Spencer donne un encadrement des valeurs de $\alpha (n)$ et $\beta (n)$ :

Théorème — Pour tout réel $\varepsilon >0$ et pour tout entier $n$ suffisamment grand :

$(1-\varepsilon ){\frac {n^{2}}{2e\log(n)}}<\alpha (n)\leqslant \beta (n)<(1+\varepsilon ){\frac {n^{2}}{2\log(n)}}$

Ce résultat montre en particulier que la minoration de $\beta (n)$ 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 $c$ telle que pour tout entier $n$ suffisamment grand, tout graphe $G=(V,E)$ à $n$ sommets admet une partition biclique pour laquelle tout sommet de $G$ est contenu dans au plus $c(n/\log(n))$ sous-graphes de la partition.

Articles connexes

• Graphe biparti complet
• Théorème de Graham-Pollak
• Dimension bipartie
• Liste de problèmes NP-complets