Graphe biparti complet

En théorie des graphes, un graphe est dit biparti complet (ou encore est appelé une biclique) s'il est biparti et chaque sommet du premier ensemble est relié à tous les sommets du second ensemble. Plus précisément, il existe une partition de son ensemble de sommets en deux sous-ensembles $U$ et $V$ telle que chaque sommet de $U$ est relié à chaque sommet de $V$Modèle:Référence nécessaire.

Si le premier ensemble $U$ est de cardinal m et le second ensemble $V$ est de cardinal n, le graphe biparti complet est noté $K_{m,n}$.

Exemples

Étoiles

Si m = 1, le graphe complet biparti K_1,n est une étoile et est noté $S_n$Modèle:Référence nécessaire.

Les étoiles S₃, S₄, S₅ et S₆.

En particulier, les étoiles sont des arbres. D'ailleurs, tous les graphes bipartis complets qui sont des arbres sont des étoilesModèle:Référence nécessaire.

Autres exemples

Voici des exemples pour m = 3.

• 
  K_3,1
• 
  K_3,2
• 
  K_3,3

Le graphe K_3,3 est le plus petit graphe cubique non planaireModèle:Référence nécessaire. Il sert dans les caractérisation des graphes planaires de Kazimierz Kuratowski et de Klaus WagnerModèle:Référence nécessaire. C'est lui qui réside derrière l'énigme des trois maisons.

Propriétés

Inclusions de famille de graphe

• Le graphe biparti complet $K_{n,n}$ est un graphe de Moore et une $(n,4)$-cageModèle:Référence nécessaire.
• Les graphes bipartis complets $K_{n,n}$ et $K_{n,n+1}$ sont des graphes de TuránModèle:Référence nécessaire.
• Le graphe biparti complet $K_{n,n}$ est un graphe symétrique : il est arête-transitif, sommet-transitif et arc-transitifModèle:Référence nécessaire.
• Le nombre d'arbres couvrants du graphe biparti complet $K_{m,n}$ est $m^{n-1}{n}^{m-1}$ .

Invariants

Le polynôme caractéristique du graphe biparti complet $K_{m,n}$ est : $x^{m+n-2}(x^2-mn)$Modèle:Référence nécessaire. Ce polynôme caractéristique n'admet que des racines entières si, et seulement si, mn est un carré parfait. Le graphe biparti complet n'est donc un graphe intégral que dans ce cas.

Utilisations

Le théorème de Kuratowski qui caractérise les graphes planaires utilise le graphe $K_{3,3}$Modèle:,.

Conjecture

On note $\mathrm{c}\mathrm{r}(G)$ le nombre de croisements du graphe $G$, le nombre minimal de croisements parmi les tracés possibles de $G$. Kazimierz Zarankiewicz, voulant résoudre le problème de l'usine de briques de Pál Turán, a établi la majoration suivante :

$\text{cr}(K_{m,n})\le \lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{m}{2}\rfloor \lfloor \frac{m-1}{2}\rfloor$

Cette inégalité est conjecturée être une égalité.

Aspects algorithmiques et applications

Étant donné un graphe G, trouver le sous-graphe induit biparti complet $K_{m,n}$ de G avec le plus possible d'arêtes (donc avec $mn$ maximal) est un problème NP-completModèle:Référence nécessaire.

Article connexe

Théorème de Graham-Pollak