Graphe biparti

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Exemple de graphe biparti quelconque

En théorie des graphes, un graphe est dit biparti s'il existe une partition de son ensemble de sommets en deux sous-ensembles et telle que chaque arête ait une extrémité dans et l'autre dans .

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

Caractérisation[modifier | modifier le code]

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 | modifier le code]

Exemple de graphe biparti complet

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

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 | modifier le code]

  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, (ISBN 9780521458979, lire en ligne), p. 53.

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]