Graphe biparti complet

graphe biparti qui contient le nombre maximal d'arêtes

Graphe biparti complet
Image illustrative de l’article Graphe biparti complet

Notation
Nombre de sommets
Nombre d'arêtes
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 chaque sommet du premier ensemble est relié à tous les sommets du second ensemble. Plus précisément, il existe une partition de son ensemble de sommets en deux sous-ensembles et telle que chaque sommet de est relié à chaque sommet de [réf. nécessaire].

Si le premier ensemble est de cardinal m et le second ensemble est de cardinal n, le graphe biparti complet est noté .

ExemplesModifier

ÉtoilesModifier

Si m = 1, le graphe complet biparti K1,n est une étoile et est noté  [réf. nécessaire].

 
Les étoiles S3, S4, S5 et S6.

En particulier, les étoiles sont des arbres. D'ailleurs, tous les graphes bipartis complets qui sont des arbres sont des étoiles[réf. nécessaire].

Autres exemplesModifier

Voici des exemples pour m = 3.

Le graphe K3,3 est le plus petit graphe cubique non planaire[réf. nécessaire]. Il sert dans les caractérisation des graphes planaires de Kazimierz Kuratowski et de [[Klaus Wagner|Klaus Wagner[réf. nécessaire]]]. C'est lui qui réside derrière l'énigme des trois maisons.

PropriétésModifier

Inclusions de famille de grapheModifier

  • Le graphe biparti complet   est un graphe de Moore et une  -cage[réf. nécessaire].
  • Les graphes bipartis complets   et   sont des [[Graphe de Turán|graphes de Turán[réf. nécessaire]]].
  • Le graphe biparti complet   est un graphe symétrique : il est arête-transitif, sommet-transitif et arc-transitif[réf. nécessaire].
  • Le nombre d'arbres couvrants du graphe biparti complet   est   [1].

InvariantsModifier

Le polynôme caractéristique du graphe biparti complet   est :  [réf. nécessaire]. 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.

UtilisationsModifier

Le théorème de Kuratowski qui caractérise les graphes planaires utilise le graphe  [2],[3].

ConjectureModifier

On note   le nombre de croisements du graphe  , le nombre minimal de croisements parmi les tracés possibles de  . Kazimierz Zarankiewicz[4], voulant résoudre le problème de l'usine de briques de Pál Turán, a établi la majoration suivante :

 

Cette inégalité est conjecturée être une égalité[5].

Aspects algorithmiques et applicationsModifier

Étant donné un graphe G, trouver le sous-graphe induit biparti complet   de G avec le plus possible d'arêtes (donc avec   maximal) est un problème NP-complet[réf. nécessaire].

Notes et référencesModifier

  1. (en) Steven Klee et Matthew T. Stamps, « Linear algebraic techniques for spanning tree enumeration », Amer. Math. Monthly, vol. 127, no 4,‎ , p. 297-307 (DOI 10.1080/00029890.2020.1708171).
  2. Pour plus de détails voir l'article graphe planaire.
  3. Article original : Kazimierz Kuratowski, « Sur le problème des courbes gauches en topologie », Fund. Math., vol. 15,‎ , p. 271-283 (lire en ligne). Voir aussi : (en) Carsten Thomassen, « Kuratowski's theorem », Journal of Graph Theory, vol. 5,, no 3,‎ , p. 225-241 (DOI 10.1002/jgt.3190050304, Math Reviews 625064).
  4. (en) K. Zarankiewicz, « On a problem of P. Turán concerning graphs », Fund. Math., vol. 41,‎ , p. 137–145.
  5. Richard K. Guy, Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, New York, (Math Reviews 0253931), p. 63-69.

Article connexeModifier

Théorème de Graham-Pollak