Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphe biparti complet
Résumé
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 .
Si le premier ensemble est de cardinal m et le second ensemble est de cardinal n, le graphe biparti complet est noté .
Si m = 1, le graphe complet biparti K1,n est une étoile et est noté .
upright=2.63|thumb|center|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.
Voici des exemples pour m = 3.
Image:Complete bipartite graph K3,1.svg|''K''3,1
Image:Complete bipartite graph K3,2.svg|''K''3,2
Image:Complete bipartite graph K3,3.svg|''K''3,3
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.
Le graphe biparti complet est un graphe de Moore et une -cage.
Les graphes bipartis complets et sont des graphes de Turán.
Le graphe biparti complet est un graphe symétrique : il est arête-transitif, sommet-transitif et arc-transitif.
Le nombre d'arbres couvrants du graphe biparti complet est .
Le polynôme caractéristique du graphe biparti complet est : . 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.
Le théorème de Kuratowski qui caractérise les graphes planaires utilise le graphe .
On note le nombre de croisements du graphe , le nombre minimal de croisements parmi les tracés possibles de . Kazimierz Zarankiewicz, 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é.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.