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 U et V telle 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.

Graphes bipartis particuliers[modifier | modifier le code]

Exemple de graphe biparti complet

Quelques graphes particuliers sont toujours bipartis :

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.

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 \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.

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

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]