title: Graphe biparti complet
text: # 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.
  
  