Graphe biparti
# Graphe biparti

En théorie des graphes, un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints $U$ et $V$ tels que chaque arête ait une extrémité dans $U$ et l'autre dans $V$.

Un graphe biparti permet notamment de représenter une relation binaire.

## Caractérisation

Il existe plusieurs façons de caractériser un graphe biparti.

### Par le nombre chromatique

    Les graphes bipartis sont les graphes dont le nombre chromatique est inférieur ou égal à 2.

### Par la longueur des cycles

    Un graphe est biparti si et seulement s'il ne contient pas de cycle impair.

Supposons qu'un graphe est décomposé en deux partitions $U$ et $V$ telles que toute arête relie un sommet de $U$ à un sommet de $V$. Considérons un cycle quelconque. Ce cycle passe alternativement par les deux parties $U$ et $V$ avant de rejoindre le sommet de départ et a donc une longueur paire.

La réciproque est quelque peu plus dure à démontrer. Supposons que l'on ait un graphe $G$ qui ne comporte que des cycles de longueur paire. Pour simplifier, supposons également que $G$ est connexe (si jamais il ne l'était pas, on pourrait raisonner individuellement sur chaque composante connexe).

Comme $G$ est connexe, il possède un arbre couvrant $T$. Notons $r$ une racine de cet arbre. Créons deux ensembles de sommets $U$ et $V$ de la manière suivante :

* $U$ contient $r$ et tous les sommets de $T$ se trouvant à un nombre pair d'arêtes de $r$ ;
* $V$ contient les sommets de $T$ se trouvant à un nombre impair d'arêtes de $r$.

Les ensembles de sommets $U$ et $V$ sont disjoints et contiennent tous les sommets de $G$. Cela ne suffit cependant pas à montrer que $G$ est biparti : en effet, rien ne garantit a priori que l'on n'ait pas une arête « en trop » de $G$ qui relie deux sommets de $U$, par exemple.

Considérons deux sommets $x$ et $y$ de $G$ dans une même partie ($U$ ou $V$) et reliés par une arête $e$. Le chemin qui relie $x$ à $y$ dans $T$ est forcément de longueur paire, par construction de $U$ et de $V$. Si l'on ajoute l'arête $e$, on obtient un cycle de longueur impaire, ce qui est interdit par hypothèse.

Il n'est donc pas possible d'avoir de tels sommets $x$ et $y$ reliés en « court-circuit ». Toutes les arêtes du graphe relient des sommets de $U$ à des sommets de $V$, ce qui achève de montrer que $G$ est biparti.

### Par le spectre

    Si un graphe est biparti, alors son spectre vérifie la propriété suivante :
    Si $\lambda$ est une valeur propre de la matrice d'adjacence du graphe, alors $-\lambda$ en est aussi une, avec la même multiplicité que celle de $\lambda$.

### Par les polyèdres

    Un graphe est biparti si et seulement si son polytope des stables est décrit par les contraintes de clique de taille 2.

## Graphes bipartis particuliers

Les graphes suivants sont bipartis : le graphe vide, les arbres, les cycles de longueurs paires, les hypercubes et les grilles.

De plus, on définit les graphes bipartis suivants :

* Un graphe biparti est dit biparti complet (ou encore est appelé une biclique) si chaque sommet de $U$ est relié à chaque sommet de $V$.
* Un graphe biparti est dit birégulier si tous les sommets de $U$ ont le même degré, et si tous les sommets de $V$ ont le même degré.
* Les graphes bipartis de Kneser sont une famille de graphes bipartis permettant de décrire des relations d'inclusion entre ensembles.
* 110-graphe de Iofinova-Ivanov
