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

Exemple de graphe biparti quelconque

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

Caractérisation

modifier

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[1].
Par le spectre
Si un graphe est biparti, alors son spectre vérifie la propriété suivante[2] :
Si   est une valeur propre de la matrice d'adjacence du graphe, alors   en est aussi une, avec la même multiplicité que celle de  .
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

modifier
 
Exemple de graphe biparti complet

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   est relié à chaque sommet de  .
  • Un graphe biparti est dit birégulier si tous les sommets de   ont le même degré, et si tous les sommets de   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

Notes et références

modifier
  1. (en) Armen S. Asratian, Tristan M. J. Denley et Roland Häggkvist, « Bipartite Graphs and their Applications », Cambridge Tracts in Mathematics, Cambridge University Press, vol. 131,‎ (ISBN 9780521593458), Théorème 2.1.3, p. 8. Les auteurs attribuent cette caractérisation à Dénes Kőnig dans un article de 1916.
  2. (en) Norman Biggs, Algebraic Graph Theory, Cambridge University Press, , 2e éd., 205 p. (ISBN 978-0-521-45897-9, lire en ligne), p. 53.

Voir aussi

modifier

Articles connexes

modifier