En théorie des graphes, une branche des mathématiques, les graphes bipartis de Kneser forment une famille de graphes non orientés définie comme suit :
Soient E un ensemble à n éléments et k un entier inférieur à n. Les sommets du graphe représentent les sous-ensembles de E à k éléments ou à n − k éléments. Deux sommets sont reliés par une arête lorsque l'un des sous-ensembles qu'ils représentent est inclus dans l'autre..
Exemples Le graphe biparti de Kneser est le graphe de Desargues (figure).
Les graphes bipartis de Kneser sont les graphes couronnes.
Propriétés Le graphe biparti de Kneser a sommets. Il est régulier de degré .
Comme le Graphe de Kneser, il est sommet-transitif.
Le graphe biparti de Kneser peut être formé comme une du graphe de Kneser en dupliquant chaque sommet et en remplaçant chaque arête par une paire d'arêtes reliant les paires correspondantes de sommets..
Voir aussi Références
Lien externe
Catégorie:Famille de graphes
en:Kneser graph#Related graphs