Graphe biparti complet

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Graphe biparti complet
Image illustrative de l'article Graphe biparti complet
K_{3,2}

Notation K_{m,n}
Nombre de sommets m+n
Nombre d'arêtes mn
Distribution des degrés m sommets de degré n
n sommet de degré m
Diamètre 2

En théorie des graphes, un graphe est dit biparti complet (ou encore est appelé une biclique) s'il est biparti et contient le nombre maximal d'arêtes.

En d'autres termes, 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 U est de cardinal m et V est de cardinal n le graphe biparti complet est noté K_{m,n}.

Propriétés[modifier | modifier le code]

  • É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.
  • Un graphe planaire ne peut pas contenir K_{3,3} comme mineur.
  • 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 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 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.

Exemples[modifier | modifier le code]

Si m=1 le graphe complet biparti Km,n est un arbre et est appelé une étoile. En tant qu'étoile, K1,n est notée S_n. Tous les graphes bipartis complets qui sont des arbres sont des étoiles.

Le graphe K3,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. C'est lui qui réside derrière l'énigme des trois maisons.

Les étoiles S3, S4, S5 et S6.