Graphe biparti complet
# 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$.

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}$.

En particulier, les étoiles sont des arbres. D'ailleurs, tous les graphes bipartis complets qui sont des arbres sont des étoiles.

### 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 planaire. Il sert dans les caractérisation des graphes planaires de Kazimierz Kuratowski et de [[Klaus Wagner|Klaus Wagner]]. 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)$-cage.
* Les graphes bipartis complets $K_{n,n}$ et $K_{n,n+1}$ sont des [[Graphe de Turán|graphes de Turán]].
* Le graphe biparti complet $K_{n,n}$ est un graphe symétrique : il est arête-transitif, sommet-transitif et arc-transitif.
* 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)$. 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}$$^,.$

### Conjecture

On note $\mathrm {cr} (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 :

    ${\textrm {cr}}(K_{m,n})\leq \left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {m}{2}}\right\rfloor \left\lfloor {\frac {m-1}{2}}\right\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-complet.

