Dimension bipartie

Dans le domaine mathématique de la théorie des graphes et de l'optimisation combinatoire, la dimension bipartie d'un graphe G = (V, E) non orienté est le nombre minimum de sous-graphes bipartis complets nécessaires pour couvrir toutes les arêtes de E. Un ensemble de sous-graphes bipartis complets couvrant toutes les arêtes de G est appelé une couverture par sous-graphes bipartis complets, ou couverture biclique. La dimension bipartie d'un graphe G est souvent notée d(G). Considérons un graphe G = (V, E) qui s'avère être biparti. Voici un exemple de couverture sous-graphes bipartis complets de G : Fichier:Bipartite-dimension-bipartite-graph.svg|Un graphe G biparti Fichier:Bipartite-dimension-biclique-cover.svg|... et une couverture par quatre sous-graphes bipartis complets Fichier:Bipartite-dimension-red-biclique.svg|1. Le sous-graphe biparti complet rouge Fichier:Bipartite-dimension-blue-biclique.svg|2. Le sous-graphe biparti complet bleu Fichier:Bipartite-dimension-green-biclique.svg|3. Le sous-graphe biparti complet vert Fichier:Bipartite-dimension-black-biclique.svg|4. Le sous-graphe biparti complet noir La dimension bipartie d'un graphe complet est . La dimension bipartie d'un graphe couronne à 2n sommets est , où: La dimension bipartie d'un graphe grille de taille est si est pair et pour deux entiers et est sinon. La dimension bipartie de nombreux graphes particuliers a déjà été déterminée : par exemple, pour le chemin , et pour le cycle , . Le calcul de la dimension bipartie d'un graphe G donné est un problème d'optimisation. Le problème de décision associé à la dimension bipartie peut être formulé ainsi : Entrée : Un graphe non orienté et un entier positif . Sortie : Oui, s'il existe une couverture de G par sous-graphes bipartis complets de cardinal inférieur à ; non sinon. Ce problème est appelé problème GT18 dans le livre de Garey et Johnson sur les problèmes NP-complets, et est une reformulation d'un autre problème sur les familles d'ensembles finis, le problème Set Basis nommé SP7.